最終更新日：2026年7月13日
fe fe-technology data-structure algorithm
まず結論
2分探索木とは、各節点の左側に小さい値、右側に大きい値を配置する木構造です。
基本情報技術者試験では、次の判断ができれば十分です。
左の子：親より小さい
右の子：親より大きい
この大小関係を使って、目的の値を効率よく探します。
直感的な説明
2分探索木は、数字を大小で振り分けながら枝分かれさせるイメージです。
たとえば、最初に 50 を置き、その後に 30 と 70 を入れるとします。
50
/ \
30 70
30 は 50 より小さいので左、70 は 50 より大きいので右に進みます。
探すときも同じです。
探したい値が小さい → 左へ
探したい値が大きい → 右へ
定義・仕組み
2分探索木では、各節点について次の関係を保ちます。
- 左部分木の値は、その節点より小さい
- 右部分木の値は、その節点より大きい
たとえば、次の木を考えます。
50
/ \
30 70
/ \ / \
20 40 60 80
60 を探す場合は、次の順に進みます。
60 > 50 → 右へ
60 < 70 → 左へ
60 = 60 → 発見
すべての値を順番に調べる必要がないため、木の形が偏っていなければ探索を効率化できます。
ただし、値の入れ方によって木が片側に偏ると、探索効率は下がります。
10
\
20
\
30
このような形では、連結リストに近い探索になります。
科目Aでどう出る？
科目Aでは、2分探索木の特徴を問う問題が中心です。
判断キーワードは次の3つです。
大小関係
左は小さい
右は大きい
次のように切り分けます。
| 用語 | 判断ポイント |
|---|---|
| 2分探索木 | 左が小、右が大 |
| 2分木 | 子の数が最大2個 |
| ヒープ | 親子間で大小関係を保つ |
| スタック | 後入れ先出し |
| キュー | 先入れ先出し |
単に「子が2個まで」と書かれているだけなら、2分探索木とは限りません。
科目Bでどう使う？
科目Bでは、値をどちらの枝へ入れるか、探索順をたどる問題に使われます。
たとえば、次の値を順番に挿入します。
50, 30, 70, 20, 40
結果は次の形です。
50
/ \
30 70
/ \
20 40
トレースするときは、現在の節点との大小比較を1回ずつ書くと安全です。
よくある誤解・混同
誤解1：2分木と2分探索木は同じ
同じではありません。
2分木は、各節点の子が最大2個という構造です。
2分探索木は、それに加えて左右の大小関係を持ちます。
誤解2：必ず高速に探索できる
木が偏ると、探索効率は低下します。
「2分探索木なら常に高速」とは限りません。
誤解3：ヒープと同じ
ヒープは、親と子の間で大小関係を保つ構造です。
一方、2分探索木は、左部分木と右部分木全体に大小関係があります。
まとめ（試験直前用）
- 2分探索木は、左が小さく右が大きい
- 大小関係を使って探索する
- 2分木は子が最大2個というだけ
- 木が偏ると探索効率は下がる
- ヒープとは大小関係の持ち方が違う