---
title: "2分探索木とは？左右の大小関係と探索手順【基本情報技術者試験】"
description: "2分探索木の左右の大小関係、探索・挿入の流れ、2分木やヒープとの違いを整理し、基本情報技術者試験で選択肢を切る判断軸を解説します。"
last_modified_at: "2026-07-13"
canonical_url: "https://stemtazoo.github.io/fe/binary-search-tree/"
section: "fe"
---

## まず結論

2分探索木とは、**各節点の左側に小さい値、右側に大きい値を配置する木構造**です。

基本情報技術者試験では、次の判断ができれば十分です。

```text
左の子：親より小さい
右の子：親より大きい
```

この大小関係を使って、目的の値を効率よく探します。

## 直感的な説明

2分探索木は、数字を大小で振り分けながら枝分かれさせるイメージです。

たとえば、最初に `50` を置き、その後に `30` と `70` を入れるとします。

```text
      50
     /  \
   30    70
```

`30` は `50` より小さいので左、`70` は `50` より大きいので右に進みます。

探すときも同じです。

```text
探したい値が小さい → 左へ
探したい値が大きい → 右へ
```

## 定義・仕組み

2分探索木では、各節点について次の関係を保ちます。

- 左部分木の値は、その節点より小さい
- 右部分木の値は、その節点より大きい

たとえば、次の木を考えます。

```text
        50
       /  \
     30    70
    / \    / \
  20  40  60  80
```

`60` を探す場合は、次の順に進みます。

```text
60 > 50 → 右へ
60 < 70 → 左へ
60 = 60 → 発見
```

すべての値を順番に調べる必要がないため、木の形が偏っていなければ探索を効率化できます。

ただし、値の入れ方によって木が片側に偏ると、探索効率は下がります。

```text
10
 \
  20
   \
    30
```

このような形では、連結リストに近い探索になります。

## 科目Aでどう出る？

科目Aでは、2分探索木の特徴を問う問題が中心です。

判断キーワードは次の3つです。

```text
大小関係
左は小さい
右は大きい
```

次のように切り分けます。

| 用語 | 判断ポイント |
|---|---|
| 2分探索木 | 左が小、右が大 |
| 2分木 | 子の数が最大2個 |
| ヒープ | 親子間で大小関係を保つ |
| スタック | 後入れ先出し |
| キュー | 先入れ先出し |

単に「子が2個まで」と書かれているだけなら、2分探索木とは限りません。

## 科目Bでどう使う？

科目Bでは、値をどちらの枝へ入れるか、探索順をたどる問題に使われます。

たとえば、次の値を順番に挿入します。

```text
50, 30, 70, 20, 40
```

結果は次の形です。

```text
      50
     /  \
   30    70
  /  \
20   40
```

トレースするときは、現在の節点との大小比較を1回ずつ書くと安全です。

## よくある誤解・混同

### 誤解1：2分木と2分探索木は同じ

同じではありません。

2分木は、各節点の子が最大2個という構造です。

2分探索木は、それに加えて左右の大小関係を持ちます。

### 誤解2：必ず高速に探索できる

木が偏ると、探索効率は低下します。

「2分探索木なら常に高速」とは限りません。

### 誤解3：ヒープと同じ

ヒープは、親と子の間で大小関係を保つ構造です。

一方、2分探索木は、左部分木と右部分木全体に大小関係があります。

## まとめ（試験直前用）

- 2分探索木は、左が小さく右が大きい
- 大小関係を使って探索する
- 2分木は子が最大2個というだけ
- 木が偏ると探索効率は下がる
- ヒープとは大小関係の持ち方が違う