探索木の種類

探索木は、キーの大小に従ってデータを並べ、探索、挿入、削除を速くするための木構造です。

■ 試験で押さえるポイント

• 二分探索木は、左の部分木に小さいキー、右の部分木に大きいキーを置きます。

• AVL木などの平衡木は、木が偏らないよう調整して、探索を$O(\log n)$に保ちます。

• B木は一つの節点に複数のキーを持つ木で、データベースの索引に使われます。

■ 選択肢での判断ポイント

二分探索木を中間順でたどると、キーが昇順に並びます。偏った木は探索が遅くなります。

例: 昇順のデータをそのまま二分探索木に入れると一列に偏り、探索が線形探索と同じ$O(n)$になります。