平衡二分探索木のソースを表示

'''平衡二分探索木'''（へいこうにぶんたんさくぎ、{{lang-en-short|self-balancing binary search tree}}）とは、[[計算機科学]]において[[二分探索木]]のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（[[平衡木]]）である。平衡二分探索木は[[連想配列]]や[[集合]]その他の[[抽象データ型]]を実装する最も効率のよい[[データ構造]]の1つである。

==概要==

[[二分探索木]]上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の[[二分探索木]]の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として[[連結リスト]]同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつもできるわけではない。特に入力が一括して与えられることのない[[オンラインアルゴリズム]]([[:en:Online algorithm|online algorithm]])の場合はそうである。

平衡二分探索木は木に対する変換(例えば[[木の回転]])を木の高さを減らすために必要に応じて行うことでこの問題を解決する。いくらかのオーバーヘッドは要するものの、それは後述の操作のオーバーヘッドを長い目で見て劇的に減らすことで正当化される。

木の高さは常に最低でも<math>\lfloor\log n\rfloor</math>以上である。k段目にはせいぜい2<sup>''k''</sup>ノードしか存在しないからである。完全な2分木は丁度この高さになる。平衡二分探索木を常に最小の高さに保つのは高くつくので、いつも正確に平衡している必要はない。その代わり、高さをこの下界の定数倍以内に維持する。

''n''をノードの数とした場合の計算量は以下のとおり。
{| border="1" class="wikitable"
|-
!操作||[[ランダウの記号|Big-O]] 時間
|-
|参照||O(log ''n'')
|-
|挿入||O(log ''n'')
|-
|削除||O(log ''n'')
|-
|全ての要素に対する繰り返し||O(''n'')
|}
ある実装では上記の時間は最悪時のものであり、違う実装では[[償却解析]]([[:en:Amortized analysis|Amortized analysis]])した時間である。

== 実装 ==

平衡二分探索木を実装したデータ構造には以下のようなものが存在する。
{| class="wikitable"
|+ 
! 名称 !! 英語名 !! 発表年
|-
! [[AVL木]]
| [[:en:AVL tree|AVL tree]]
| 1962年
|-
! [[赤黒木]]
| [[:en:red-black tree|red-black tree]]
| 1972年
|-
! [[スプレー木]]
| [[:en:splay tree|splay tree]]
| 1985年
|-
! [[スケープゴート木]]
| [[:en:scapegoat tree|scapegoat tree]]
| 1989年
|-
! [[Treap]]
| [[:en:Treap|treap]]
| 1989年
|-
! [[AA木]]
| [[:en:AA tree|AA tree]]
| 1993年
|}
なお、2分ではない、平衡探索木としては[[B木]]、[[2-3木]]、[[2-3-4木]]などがある。木構造ではないが、同じような用途に使えるものとして[[スキップリスト]]がある。treapやスキップリストは[[乱択アルゴリズム]]。

== 応用 ==

平衡二分探索木は[[連想配列]]を構築する自然な方法として使用され、キーと値の組はキーのみに基づいた順番で挿入される。この能力において、[[ハッシュテーブル]]([[:en:hash table|hash table]])との比較で多くの利点と欠点を持つ。また、参照は同じキーが複数回使用できる場合はやや複雑である。

多くのアルゴリズムで最悪ケースでの性能を、ほんの少しの手間で良好にするために、平衡二分探索木を利用することができる。例えば、[[2分探索]]を平衡二分探索木で行った場合、最適な<math>\mathcal{O}(n \log n)</math>のソートアルゴリズムを簡単に記述することができる(実際には、このようなアルゴリズムはキャッシュ効率が悪いという問題を抱える)。また、[[計算幾何学]]の多くのアルゴリズムは平衡二分探索木のバリエーションを利用して[[線分の交差判定問題]]([[:en:line segment intersection|line segment intersection]])や[[点位置決定問題]]([[:en:point location problem|point location problem]])を効率よく解決している。

平衡二分探索木は柔軟なデータ構造で、追加情報を効率的に記録したり新しい操作を効率的に行うよう拡張するのは簡単である。例えば、それぞれの部分木のノードで特定の特性を持つものの数を記録する場合、<math>\mathcal{O}(\log n)</math> 時間で特定の範囲のキーでその特性を持つノードの数を数えることが可能である。これらの拡張はデータベースのクエリを最適化したり、他のリストを処理するアルゴリズムに対して利用できる。

== 関連項目 ==
* [[スキップリスト]]
* [[B木]]
* [[木構造 (データ構造)]]

{{データ構造}}

[[Category:二分木|へいこうにふんたんさくき]]