問題
二分探索木に関する記述として正しいものはどれか。
選択肢
- 1任意のノードの左部分木の値は、そのノードの値より大きい
- 2探索の平均計算量はO(log n)、最悪計算量はO(n)である
- 3挿入順序に依存せず、常に平衡が保たれる
- 4中間順走査（inorder）すると、値が降順に並ぶ
正解
2. 探索の平均計算量はO(log n)、最悪計算量はO(n)である
詳しい解説を見る解説を閉じる
解説
二分探索木（BST）は、左部分木の値＜親＜右部分木の値という制約を持つ木構造。平均O(log n)で探索可能だが、偏った挿入では片側に長い線形構造となり最悪O(n)。平衡性はAVL木や赤黒木で保証する。中間順走査では値が昇順に並ぶ。
一問一答
全400問を繰り返し学習