平成23年特別試験問題 午前問5
広告
解説
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分探索木は「エ」と同じ構造になります。
まず8をルートノード(根)とします。
![05_1.png](/kakomon/23_toku/img/05_1.png)
![05_2.png](/kakomon/23_toku/img/05_2.png)
![05_3.png](/kakomon/23_toku/img/05_3.png)
![05_4.png](/kakomon/23_toku/img/05_4.png)
![05_5.png](/kakomon/23_toku/img/05_5.png)
![05_6.png](/kakomon/23_toku/img/05_6.png)
![05_7.png](/kakomon/23_toku/img/05_7.png)
広告