2分探索木とは？にぶんたんさくぎ
2分探索木とは、どの節点でも「左の部分木の値＜自分の値＜右の部分木の値」が成り立つ2分木。探したい値と節点の値を比べるだけで進む向きが決まり、1回の比較で候補が半分に減る。左右の高さが釣り合っていれば、探索・挿入・削除のいずれも、要素数が2倍になっても比較が1回増えるだけで済む。
最終更新：2026-10-09
この語が出る過去問を解く →背景
配列は整列してあれば2分探索できるが、途中に1件足すだけで後ろを全部ずらすことになる。連結リストは挿入が速い代わりに先頭から順に見るしかない。「大小の関係を木の形として持たせる」ことで、探す速さと入れ替えのしやすさを両立させたのがこの構造である。
具体例
1から1,023までの値が均等に入った木なら、どの値でも10回程度の比較でたどり着ける。根が40の木で65を探すなら、65は40より大きいので右へ進み、以後も比較のたびに探す範囲が半分になる。挿入も同じ経路をたどり、行き止まりになった位置に新しい節点を付ける。
試験での引っ掛け
「いつでも速く探せる」わけではない点が狙われる。昇順に整列済みのデータを先頭から順に挿入すると、木が片側へ一直線に伸びて連結リスト（要素を1本の鎖のようにつないだ列）と同じ形になり、探索の比較回数が要素数に比例するまで悪化する。親と子の大小だけを決め、左右の子どうしの大小は決めないヒープとの取り違えにも注意。
関連用語
出た過去問
問題文で直接問われたものと、解説の中で触れられたものが含まれます。
出典：平成28年度 秋期 基本情報技術者試験 午前 問6（IPA）
2分探索木になっている2分木はどれか。
正解：根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。
要点：2分探索木は左部分木＜節点＜右部分木が全節点で成立
2分探索木は、任意の節点について左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きいという条件を満たす木である。根17に対し左側が10・14・16、右側が18・19となり、さらに14の左が10・右が16、19の左が18と、どの節点でも条件が崩れていない木が正解となる。
出典：平成28年度 春期 基本情報技術者試験 午前 問5（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となる。
出典：平成31年度 春期 基本情報技術者試験 午前 問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と、どのノードでも条件が崩れていない。
出典：令和4年度 公開問題 基本情報技術者試験 科目A 問5（IPA）
2分探索木になっている2分木はどれか。
正解：イ：根17、左の子14（さらに左10・右16）、右の子19（さらに左18）
要点：2分探索木は全節点で左部分木＜節点＜右部分木が成立する
2分探索木は、任意の節点について左部分木の全要素がその節点より小さく、右部分木の全要素が大きいという条件を満たす木である。各木で節点ごとにこの大小関係を確認すると、条件を崩す節点が無いものは1つだけである。根より小さい値が右側にある、あるいは左の子より大きい値が左部分木にあるといった違反があれば2分探索木ではない。
出典：令和7年度 公開問題 基本情報技術者試験 科目A 問3（IPA）
図の木構造は2分探索木である。a〜gの値の大小関係として，適切なものはどれか。ここで，a〜gの値は重複しないものとする。
正解：d＜b＜e＜a＜f＜c＜g
要点：2分探索木は通りがけ順にたどると値が昇順に並ぶ
2分探索木は、ある節点の左部分木には自分より小さい値、右部分木には自分より大きい値だけが入るという性質をもつ。したがって節点を通りがけ順（左・自分・右）にたどると値が昇順に並ぶ。この木を通りがけ順にたどるとd、b、e、a、f、c、gの順になり、これがそのまま大小関係になる。
出典・参考
公式シラバスの1 基礎理論 ＞ 1. データ構造 ＞ (2) データ構造の種類に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。