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

解説

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