平衡二分探索木
平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。
概要
[編集]二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつもできるわけではない。特に入力が一括して与えられることのないオンラインアルゴリズム(online algorithm)の場合はそうである。
平衡二分探索木は木に対する変換(例えば木の回転)を木の高さを減らすために必要に応じて行うことでこの問題を解決する。いくらかのオーバーヘッドは要するものの、それは後述の操作のオーバーヘッドを長い目で見て劇的に減らすことで正当化される。
木の高さは常に最低でも以上である。k段目にはせいぜい2kノードしか存在しないからである。完全な2分木は丁度この高さになる。平衡二分探索木を常に最小の高さに保つのは高くつくので、いつも正確に平衡している必要はない。その代わり、高さをこの下界の定数倍以内に維持する。
nをノードの数とした場合の計算量は以下のとおり。
| 操作 | Big-O 時間 |
|---|---|
| 参照 | O(log n) |
| 挿入 | O(log n) |
| 削除 | O(log n) |
| 全ての要素に対する繰り返し | O(n) |
ある実装では上記の時間は最悪時のものであり、違う実装では償却解析(Amortized analysis)した時間である。
実装
[編集]平衡二分探索木を実装したデータ構造には以下のようなものが存在する。
| 名称 | 英語名 | 発表年 |
|---|---|---|
| AVL木 | AVL tree | 1962年 |
| 赤黒木 | red-black tree | 1972年 |
| スプレー木 | splay tree | 1985年 |
| スケープゴート木 | scapegoat tree | 1989年 |
| Treap | treap | 1989年 |
| AA木 | AA tree | 1993年 |
なお、2分ではない、平衡探索木としてはB木、2-3木、2-3-4木などがある。木構造ではないが、同じような用途に使えるものとしてスキップリストがある。treapやスキップリストは乱択アルゴリズム。
応用
[編集]平衡二分探索木は連想配列を構築する自然な方法として使用され、キーと値の組はキーのみに基づいた順番で挿入される。この能力において、ハッシュテーブル(hash table)との比較で多くの利点と欠点を持つ。また、参照は同じキーが複数回使用できる場合はやや複雑である。
多くのアルゴリズムで最悪ケースでの性能を、ほんの少しの手間で良好にするために、平衡二分探索木を利用することができる。例えば、2分探索を平衡二分探索木で行った場合、最適なのソートアルゴリズムを簡単に記述することができる(実際には、このようなアルゴリズムはキャッシュ効率が悪いという問題を抱える)。また、計算幾何学の多くのアルゴリズムは平衡二分探索木のバリエーションを利用して線分の交差判定問題(line segment intersection)や点位置決定問題(point location problem)を効率よく解決している。
平衡二分探索木は柔軟なデータ構造で、追加情報を効率的に記録したり新しい操作を効率的に行うよう拡張するのは簡単である。例えば、それぞれの部分木のノードで特定の特性を持つものの数を記録する場合、 時間で特定の範囲のキーでその特性を持つノードの数を数えることが可能である。これらの拡張はデータベースのクエリを最適化したり、他のリストを処理するアルゴリズムに対して利用できる。
