三元検索ツリーのバランス

Question

3成分の検索ツリーの「バランス」をどのように行いますか？ほとんどのTST実装は、バランスに対処するものではありませんが、最適な順序で挿入することをお勧めします（これは制御できません）。

Answer 1

ドブス博士の記事について 三元検索ツリー 言う：DD SleatorとRe Tarjanは、「自己調整バイナリ検索ツリー」の3成分検索ツリーの理論的バランスアルゴリズムを説明しています（Journal of the ACM、1985年7月）。お気に入りの検索エンジンを使用して、このペーパーのオンラインバージョンを見つけることができます。

Answer 2

簡単な最適化の1つは、最悪のシナリオを避けることができる赤黒の木にすることです。 TSTは、特定のノードの値が別のTSTであるバイナリツリーです。したがって、ノードの「中間」の子は、とにかく別の親に移動できないため、各レベルでバランスが取れているツリーの一部ではありません。

これにより、Trieの各層がログ（R）時間で通過することが保証されますが、各ノードのサブリーのサイズを考慮することでさらに良くなる可能性があります。それはもっと複雑に見えます！

Answer 3

バイナリ検索ツリーの一般化はです Bツリー, 、2つ以上のファンアウトで機能します。それがそれを行う唯一の方法ではありませんが、それは一般的な方法です。

大まかに機能する方法は、挿入または削除がツリーをバランスから外すと、隣接するノードから要素またはスペースを盗むことです。それでさえ木のバランスを保つのに十分でない場合、その高さは部屋を作るために変更されます。

Answer 4

この記事を読む：

「Ghada Hany Badr ∗およびB. John Oommen†」による、条件付き回転とランダム化ヒューリスティックを使用して、三元検索の自己調整試行†」

それはあなたが自己調整とTSTのバランスをとることを理解するのに役立ちます。