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

2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的にデータを探索することが可能になっています。

まず8をルートノード（根）とします。12＞8なのでそのまま右の部分木に追加します。5＜8なのでそのまま左の部分木に追加します。3＜8なので左の部分木なります。さらに3＜5のため節点5の左の部分木に追加します。10＞8なので右の部分木なります。さらに10＜12なので節点12の左の部分木に追加します。7＜8なので左の部分木なります。さらに7＞5なので節点5の右の部分木に追加します。6＜8なので左の部分木なります。続いて6＞5なので節点5の右の部分木になり、さらに6＜7なので節点7の左部分木に追加します。この過程を経て完成した2分探索木は「エ」と同じ構造になります。