平衡二分探索木
二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつもできるわけではない。特に入力が一括して与えられることのないオンラインアルゴリズム(online algorithm)の場合はそうである。
平衡二分探索木は木に対する変換(例えば木の回転)を木の高さを減らすために必要に応じて行うことでこの問題を解決する。いくらかのオーバーヘッドは要するものの、それは後述の操作のオーバーヘッドを長い目で見て劇的に減らすことで正当化される。
木の高さは常に最低でも ⌊ log  n ⌋ {\displaystyle \lfloor \log n\rfloor } 以上である。k段目にはせいぜい2ノードしか存在しないからである。完全な2分木は丁度この高さになる。平衡二分探索木を常に最小の高さに保つのは高くつくので、いつも正確に平衡している必要はない。その代わり、高さをこの下界の定数倍以内に維持する。
nをノードの数とした場合の計算量は以下のとおり。
ある実装では上記の時間は最悪時のものであり、違う実装では償却解析(Amortized analysis)した時間である。