探索木の種類

探索木は、キーの大小関係や階層的な索引規則に従って要素を配置し、探索・挿入・削除を効率化する木構造です。

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

• 二分探索木は各ノードの左部分木を小さいキー、右部分木を大きいキーとし、中間順走査で昇順になります。

• 偏ると高さが$n$となり探索が$O(n)$へ悪化するため、AVL木や赤黒木は回転等で高さを$O(\log n)$に保ちます。

• B木は一ノードに複数キーと子を持つ平衡多分木で、ディスクアクセス回数を減らすためDB・ファイル索引に使われます。

• B+木は実データへの参照を主に葉へ置き、葉同士を連結するため、範囲検索と順次走査に適します。

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

二分探索木の中間順走査は昇順、B+木の葉連結は範囲検索に有利です。平衡木は高さを対数程度に保つことで最悪探索を改善します。

例: キーを昇順に単純二分探索木へ入れると一列に偏りますが、AVL木なら回転して高さを抑えます。