基本情報技術者 予想問題｜A 第17問

解説

二分探索木は、すべてのノードで「左部分木の全ノードの値 < 親の値 < 右部分木の全ノードの値」という大小関係を満たす木構造であり、「左部分木の全ノードの値は親より小さく、右部分木は親より大きい」が正解である。この性質により、探索値と親の値を比較して左右どちらか一方の部分木だけをたどればよく、木が平衡していれば平均O(log n)で探索できる。「左部分木の全ノードの値は親より大きい」と「右部分木の全ノードの値は親より小さい」は左右の大小関係が逆になっており誤りである。「左右の部分木の値に規則はない」のように規則がなければ全ノードを調べる必要が生じ、二分探索木の利点が失われる。中順（通りがけ順）で走査すると値が昇順に取り出せる性質も重要で、先行順・中順・後行順の走査結果や、偏った木では探索がO(n)に劣化する点も併せて頻出である。