B木

1ノードに複数のキーと子ポインタを持つ多分木構造の平衡探索木。ディスクアクセスの回数を最小化するよう設計され、データベースのインデックスやファイルシステムで広く使用される。全葉が同じ深さにある。

ディスクベースのデータ構造で多分木の一種。すべての葉ノードが同じ深さにあり、各ノードに複数のキーを格納する。探索、挿入、削除がO(log n)で実行でき、DBMSのインデックス構造として広く利用される。

各ノードが最大2つの子ノードを持つ木構造。左の子と右の子に分かれる。2分探索木、ヒープ、式木など多くの応用がある。探索や整列の効率的な実装に使われる。

左の子ノードの値が親より小さく、右の子ノードの値が親より大きいという条件を満たす2分木。探索・挿入・削除の平均計算量がO(log n)で効率的。バランスが崩れるとO(n)に悪化する。

親ノードの値が子ノードの値以上（最大ヒープ）または以下（最小ヒープ）という条件を満たす完全2分木。最大値または最小値の取得がO(1)で可能。優先度付きキューやヒープソートの実装に使用される。

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

各ノードが最大2つの子ノードを持つ木構造。完全2分木は最下段以外の全階層が埋まった構造。2分探索木は左の子が親より小さく右の子が親より大きい性質を持ち、探索・挿入・削除をO(log n)で実行可能。

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