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

Question

三元検索ツリーの「バランスを取る」方法は？ほとんどのtst実装ではバランス調整は扱われていませんが、最適な順序で挿入することをお勧めします（制御できません）。

Answer 1

ドブス博士の記事Ternary Search Treesについて：D.D. Sleator and R.E. Tarjanは、「自己調整バイナリ検索木」（ACMのジャーナル、1985年7月）の三元探索木のための理論的な平衡化アルゴリズムを記載している。このペーパーのオンライン版は、お気に入りの検索エンジンで見つけることができます。

Answer 2

バイナリ検索ツリーの一般化はB-Treeです。それはそれを行う唯一の方法ではありませんが、一般的な方法です。

挿入または削除がツリーのバランスを崩してしまう場合、それは、要素またはスペースを隣接ノードから盗みます。それでも木をバランスよく保つには足りない場合は、その高さを変更して部屋を作る。

Answer 3

この記事をお読みください。

によって

を「ガーダハニーバドル*およびB.ジョン・オオメン†」を 「3分探索の自己調整は、条件付きのローテーションおよびランダム化ヒューリスティックを使用しようとします」それがお手伝いします自己調整とバランスのとれたTSTを理解することになります。