問題
問3
ある2分探索木に新しい要素を追加する際、常に根ノードから比較を開始し、追加する要素が現在のノードの値より小さい場合は左の子へ、大きい場合は右の子へ進む。挿入すべき位置が見つかるまでこの操作を繰り返し、最終的に空いている場所に要素を挿入する。この操作を繰り返すことで、木構造が深くなり、探索効率が低下する可能性があるが、どのようなデータが連続して追加された場合に、このような構造になりやすいか。
- ランダムな順序のデータ
- 一部の値が重複するデータ
- 昇順または降順に並んだデータ
- 常に中間値を持つデータ
正解
正解は「ウ」です。
解説
この問題の正解は「昇順または降順に並んだデータ」です。2分探索木は、親ノードの左側には小さい値、右側には大きい値が来るようにデータを格納するデータ構造です。これにより、データを効率的に検索できます。しかし、例えば「10, 20, 30, 40, 50」のように昇順にソートされたデータを順番に追加していくと、常に右側の子ノードが追加されていくことになります。
具体的には、最初に10が根になり、次に20は10より大きいので右へ、30は20より大きいのでさらに右へ…と、片側にだけ枝が伸びていき、一直線に並んだリストのような形になってしまいます。これは降順のデータでも同様です。このような偏った木構造になると、探索する際に木の深さ分だけ比較が必要となり、2分探索木の長所である高速な探索効率が失われてしまいます。
ア(ランダムな順序のデータ):
ランダムな順序でデータを追加すると、左右にバランス良く枝が分かれやすく、効率的な木構造が形成されやすいです。
イ(一部の値が重複するデータ):
2分探索木のルールによりますが、通常、重複する値は許さないか、特定の方法で格納します。木の偏りの直接的な原因にはなりにくいです。
エ(常に中間値を持つデータ):
中間値から追加していくと、データが左右に均等に振り分けられ、最もバランスの良い木構造になりやすいです。
解法のポイント
この問題は、2分探索木の特性を理解しているかが問われます。ポイントは「左に小さい値、右に大きい値」というルールと、それがデータの追加順によってどのような木構造を形成するかをイメージすることです。特に、ソート済みのデータを順番に追加すると、木が一直線に偏ってしまうという最悪のケースは、2分探索木を学ぶ上で非常に重要な知識点です。実際に「1, 2, 3, 4」といった簡単な昇順データを紙に書きながら木を作成してみると、なぜ探索効率が低下するのか視覚的に理解できるため、おすすめです。
用語補足
2分探索木:
データを効率的に検索するためのデータ構造の一つです。各ノードが「左の子ノードの値 < 親ノードの値 < 右の子ノードの値」というルールに従って配置されています。
ノード:
木構造における個々の要素のことです。データそのものと、他のノードへの繋がり（ポインタ）を持っています。木の枝の分岐点や葉っぱをイメージすると分かりやすいです。
根（ルート）ノード:
木構造の最上位にある、全ての始まりとなるノードのことです。親を持たない唯一のノードです。
探索効率:
膨大なデータの中から目的のデータを見つけ出すまでの速さや手間のことです。効率が高いほど、短時間でデータを見つけられます。
