AVL木
通常の二分探索木は入力されるデータの順番によって木の構成が変わるため、探索効率が安定しない。例えば、データがソートされた状態で順に入力されると、木は線形リストと等価な構造になるため、探索の計算量は最悪の O ( n ) {\displaystyle O\left(n\right)} になってしまう。木が完全二分木であれば計算量は最良の O ( log  n ) {\displaystyle O\left(\log n\right)} になるが、完全二分木でなくとも木全体の高さがより小さくバランスが取れている状態、すなわち平衡な状態であれば木の性能は十分発揮できる。AVL木は「どのノードの左右部分木の高さの差も1以下」であることを平衡の条件としており、これを常に満たすので、探索の計算量は常に O ( log  n ) {\displaystyle O\left(\log n\right)} 程度になる。