基本情報技術者 一問一答｜A 第54問

解説

二分探索木は、各節点（ノード）について「左部分木のすべての値＜親の値＜右部分木のすべての値」という大小関係が成り立つ2分木である。この性質により、根から大小比較を繰り返すだけで目的の値にたどり着け、木のバランスが取れていればO(log n)で探索・挿入・削除が行える。また、通りがけ順（中間順）で走査すると昇順に整列された結果が得られる。左部分木が親より大きいとする肢は大小関係が逆であり誤り。順序なしでは探索木として機能せず、「常にバランス」も保証されない（挿入順によって偏ると探索はO(n)に劣化し、これを防ぐのがAVL木などの平衡木である）。基本情報技術者試験では与えられた木が二分探索木かを判定する問題や、走査順序との関係が頻出である。