[0025] 二分検索木

平成11年度秋期 (旧)第2情報処理技術者試験より
 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで 2分探索木を再構成するには、削除された節点の位置にどの要素を移動すればよいか。

9
10
13
14

正解

解説

 データ構造に関する問題です。

 2分探索木とは、データを階層構造で表したもので、検索用のデータ構造に用いられます。

[2分探索木とは?]



 2分探索木の一番上にあるデータを、「根」といいます。別名「ルート」ともいいます。その根からは、2本以内の「枝」が伸びており、その枝の先には「節点」があります。この問題では、節点のことを「要素」と呼んでいます。また、全体の2分探索木の一部分の節点、枝を「部分木」といいます。全体を見ると、根から枝葉があって、樹木をひっくり返したような構造になっているのが分かると思います。根の部分からはじまって、数多くの枝葉が伸びていることから、部分木において、上の階層にある節点を「親」、そこから伸びる節点を「子」と呼ぶ場合もあります。

 「2分探索木」と呼ばれるのは、節点から伸びる枝が必ず2本以内であるためで、3本以上の枝がある場合は、「多分木」とよばれます。

 こうしたデータ構造は、一般的に「木構造」や「ツリー構造」といいますが、2分探索木では、次のような特徴をもっています。
  • 親のデータ > 左側の子のデータ
  • 親のデータ < 右側の子のデータ
    (※大小関係が逆になっている場合もあります)
 この問題の2分探索木も、この特徴をもっているのが分かると思います。


[実際の2分探索木データの扱い方]
 2分探索木のデータ構造は、枝の部分がポインタとなっています。つまり、親の節点は、子の節点がどこにあるか分かっているのです。(下の図では、そのまま子の値を表記していますが、実際はポインタ、すなわち、子の節点の保管場所を持っています)


この問題で、「7」というデータを検索するとしましょう。以下手順を挙げてみます。

(1)
2分探索木のルートのデータをみます。ルートは「6」なので、2分探索木の特徴より、求める「7」は右側の節点にあると判断し、ルートのポインタから、右側の節点のアドレスを取得します。

(2)
次の節点のデータをみます。データは「8」なので、求める「7」は左側の節点にあると判断し、左側の節点のアドレスを取得します。

(3)
次の節点のデータをみます。データは「7」です。求める値にたどり着きました。


わずか3回の手順で、目的のデータにたどり着くことができました。データを1から順に調べていく方法では、7回目でようやくたどりつくことになります。


 前置きが長くなりましたが、問題の解説に入ります。

先程、2分探索木の特徴を述べました。2分探索木は、親より小さいデータと、親より大きいデータで、2つの枝より下の節点のデータを分けることで、効率よい検索を提供しています。この問題では、2分探索木の途中の節点である「12」のデータを削除するので、「12」の部分に何らかのデータを補わなければなりません。
 「12」の枝の下にある節点のデータは、左側で最大のものは「11」、右側で最小のものは「13」です。したがって「11」か「13」の節点を、「12」の節点のところへもっていけば、1回の変更のみで2分探索木を更新できます。



 選択肢では「11」がないので、「13」のウが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題