基本情報技術者平成23年特別 午前問5

午前問5

空の2分探索木に,8,12,5,3,10,7,6の順にデータを与えたときにできる2分探索木はどれか。

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

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

まず8をルートノード(根)とします。
05_1.gif/image-size:36×80
12>8なのでそのまま右の部分木に追加します。
05_2.gif/image-size:88×80
5<8なのでそのまま左の部分木に追加します。
05_3.gif/image-size:140×80
3<8なので左の部分木なります。さらに3<5のため節点5の左の部分木に追加します。
05_4.gif/image-size:165×120
10>8なので右の部分木なります。さらに10<12なので節点12の左の部分木に追加します。
05_5.gif/image-size:165×172
7<8なので左の部分木なります。さらに7>5なので節点5の右の部分木に追加します。
05_6.gif/image-size:165×120
6<8なので左の部分木なります。続いて6>5なので節点5の右の部分木になり、さらに6<7なので節点7の左部分木に追加します。
05_7.gif/image-size:165×172
この過程を経て完成した2分探索木は「エ」と同じ構造になります。
© 2010-2022 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop