algorithm - 三分探索木のバランスをとる

Question

三分探索木の「バランスをとる」にはどうすればよいでしょうか。ほとんどのtst実装はバランシングに対応していませんが、最適な順序で挿入することをお勧めします（これは制御できません）。

Answer 1

Dr. Dobbs のTernary Search Treesに関する記事には、次のように記載されています。このペーパーのオンライン版は、お気に入りの検索エンジンで見つけることができます。

Answer 2

二分探索木の一般化はBツリーであり、2以上のファンアウトに対して機能します。それを行う唯一の方法ではありませんが、それは一般的な方法です。

大まかに言うと、挿入または削除によってツリーのバランスが崩れる場合、隣接するノードから要素またはスペースが盗まれます。それでも木のバランスを保つのに十分でない場合は、スペースを空けるために高さを変更します。

Answer 3

この記事を読んでください：

「Ghada Hany Badr* and B. John Oommen †」による「条件付きローテーションとランダム化されたヒューリスティックを使用した三項探索試行の自己調整」

TSTの自己調整とバランスを理解するのに役立ちます。