2分探索木とは？

2分探索木の意味

どの節についても「左部分木の値＜自分の値＜右部分木の値」が成り立つ2分木。探すべき値と節の値を比べるだけで進む方向が決まるため、平衡が保たれていれば要素数の対数に比例する時間で探索・挿入・削除ができる。

2分探索木の具体例

根が50で30を探すなら、30＜50なので左へ進む。以後も比較のたびに探索範囲が半分になるので、1000件でも10回程度の比較で到達できる。挿入も同じ経路をたどって葉の位置に付ける。

2分探索木は試験でどう引っ掛けられる？

昇順に整列済みのデータを順に挿入すると、木が一直線に伸びて連結リストと同じ形になり、探索が要素数に比例する時間へ悪化する。「常に対数時間」ではない点が狙われる。

2分探索木と関連する用語

• 2分木
• 2分探索
• ハッシュ表（ハッシュ法）

2分探索木が出た過去問

• 2分探索木になっている2分木はどれか。

  正解：根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。

  要点：2分探索木は左部分木＜節点＜右部分木が全節点で成立

  2分探索木は、任意の節点について左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きいという条件を満たす木である。根17に対し左側が10・14・16、右側が18・19となり、さらに14の左が10・右が16、19の左が18と、どの節点でも条件が崩れていない木が正解となる。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問6（IPA）

• 10個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振…

  正解：a＝6，b＝7

  要点：2分探索木は左→節→右の順に走査すると値が昇順に並ぶ

  この条件は2分探索木の性質そのもので、木を左から順に（左部分木→自分→右部分木の順に）たどると値が1から10まで昇順に並ぶ。根が5なので左部分木の4個の節に1〜4、右部分木の5個の節に6〜10が入る。右部分木はaに左の子が無く右の子をもつ形なので、その順序ではaが最初に来て6、次にaの右の子の左の子であるbが7となる。

  出典：平成28年度 春期 基本情報技術者試験 午前 問5（IPA）

• 2分探索木として適切なものはどれか。ここで、数字1〜9は、各ノード（節）の値を表す。

  正解：イ：根が4、左の子が2（さらに左の子1・右の子3）、右の子が8（さらに左の子6・右の子9、6の左の子5・右の子7）の木

  要点：2分探索木は全ノードで左＜自分＜右が成り立つ木

  2分探索木は、任意のノードについて左部分木の全値がそのノードより小さく、右部分木の全値が大きいという条件を満たす木である。イは根が4で、左部分木が1・2・3のみ、右部分木が5〜9のみとなっている。さらに部分木の内部でも、2の左が1・右が3、8の左が6（その左5・右7）・右が9と、どのノードでも条件が崩れていない。

  出典：令和1年度 春期 基本情報技術者試験 午前 問5（IPA）

• 2分探索木になっている2分木はどれか。

  正解：イ：根17、左の子14（さらに左10・右16）、右の子19（さらに左18）

  要点：2分探索木は全節点で左部分木＜節点＜右部分木が成立する

  2分探索木は、任意の節点について左部分木の全要素がその節点より小さく、右部分木の全要素が大きいという条件を満たす木である。各木で節点ごとにこの大小関係を確認すると、条件を崩す節点が無いものは1つだけである。根より小さい値が右側にある、あるいは左の子より大きい値が左部分木にあるといった違反があれば2分探索木ではない。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問5（IPA）

• 図の木構造は2分探索木である。a〜gの値の大小関係として，適切なものはどれか。ここで，a〜gの値は重複しないものとする。

  正解：d＜b＜e＜a＜f＜c＜g

  要点：2分探索木は通りがけ順にたどると値が昇順に並ぶ

  2分探索木は、ある節点の左部分木には自分より小さい値、右部分木には自分より大きい値だけが入るという性質をもつ。したがって節点を通りがけ順（左・自分・右）にたどると値が昇順に並ぶ。この木を通りがけ順にたどるとd、b、e、a、f、c、gの順になり、これがそのまま大小関係になる。

  出典：令和7年度 （公開問題） 基本情報技術者試験 kamokuA 問3（IPA）