AVL木

任意のノードにおいて左右の部分木の高さの差が1以下であることを保証する自己平衡2分探索木。挿入・削除時に回転操作でバランスを保つため、最悪でもO(log n)の探索性能を維持する。

各ノードの左右部分木の高さの差が1以下に保たれる平衡2分探索木。挿入・削除時に回転操作（単回転・二重回転）でバランスを維持し、最悪ケースでもO(log n)の探索時間を保証する。

B木を改良したデータ構造で、データ（またはその所在）は葉にだけ格納し、内部の節は探索のためのキーだけを持つ。葉どうしがポインタで順につながっているため、範囲を指定した検索や順次の読出しが速く、データベースの索引に広く使われる。

1つの節に複数のキーと子へのポインタを持ち、すべての葉が同じ深さになるように保たれる多分木のバランス木。1つの節を補助記憶の1ブロックに対応させるとアクセスの回数を少なくできるため、データベースやファイルシステムの索引に使われる。

2分木のすべての節をたどる方法（走査）の一つで、左部分木、節、右部分木の順に訪問する。2分探索木を中間順でたどると、キーを小さい順に取り出せる。

キーの大小関係に従って節点を配置し、根から比較しながらたどることで目的のキーを効率よく探せるようにした木。各節点で左の部分木に小さいキー、右に大きいキーを置く2分探索木が基本で、平均O(log n)で探索・挿入・削除ができる。偏った順にデータを入れると高さが増してO(n)に悪化するので、AVL木や赤黒木、B木のように高さを自動的に保つ平衡木が使われる。