問題
二分探索木に関する記述として、適切なものはどれか。
ア）二分探索木は、常に左右の部分木の高さが等しくなるように自動的に維持される構造である。
イ）平衡が取れた（バランスの良い）二分探索木における探索の計算量は、一般に O(log n) である。
ウ）データを昇順または降順に偏った順序で挿入しても、二分探索木の探索性能は常に O(log n) が保証される。
エ）二分探索木は、探索専用の構造であり、要素の挿入や削除には対応していない。
解答・解説を見る
正解： イ）
解説：
- ア）単純な二分探索木は、挿入順序によって左右の部分木の高さが偏ることがあり、「常に等しくなるように自動的に維持される」わけではありません。この自動維持を行うのはAVL木や赤黒木などの平衡二分探索木です。誤りです。
- イ）左右の部分木の高さがバランスしている（平衡が取れている）場合、木の高さは要素数nに対しておおよそ log n となり、探索の計算量は O(log n) になります。正解です。
- ウ）データを昇順や降順など偏った順序で挿入すると、木が一方向に伸びた線形リストに近い形（最悪の場合、高さがnになる）になり、探索の計算量は最悪 O(n) に悪化します。「常にO(log n)が保証される」は誤りです。
- エ）二分探索木は探索だけでなく、要素の挿入・削除にも対応するデータ構造です。「探索専用」という記述は誤りです。
重要キーワード
| 用語 | 説明 |
|---|---|
| 二分探索木 | 各ノードの左部分木が小さい値、右部分木が大きい値を持つ木構造 |
| 平衡二分探索木 | 左右の高さのバランスを自動維持する二分探索木（AVL木等） |
| 計算量 O(log n) | 平衡が取れた木における探索の期待計算量 |
| 最悪計算量 O(n) | 偏った挿入によって木が線形化した場合の計算量 |