基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

2分探索木は、2分木（各節からでる枝の数が2本以下になっている木）の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があります。

要するに、どの部分を見ても「左＜中＜右」の関係を満たしていれば2分探索木といえるということです。最も簡単に見分ける方法は、図示されている木構造の各節点を左から順にならべて昇順になっているか否かを確認することです。

• 左から順に 10、15、14、16、19 となり、2分探索木の条件を満たすためには15と14の位置が逆だとわかります。
• 左から順に 10、14、16、17、18、19 となり、昇順に整列されているため2分探索木だとわかります。
• 左から順に 15、16、14、18、19、20 となり、15、16、14の順番が昇順になっていません。
• 左から順に 10、18、14、20、15、19、16 となり、昇順ではありません。なお、この木構造は2分探索木ではありませんが、全ての葉が同じ「深さ」を持っているため完全2分木という形状になっています。