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