木構造とは？二分木・二分探索木・バランス木・木の走査を基礎から理解しよう

はじめに

これまで、

リスト
↓
スタック・キュー

という線形的なデータ構造を学んできました。

今回扱うのは**木構造（Tree Structure）**です。

木構造は、

データ同士の階層関係を表現するデータ構造

です。

例えば、コンピュータのフォルダ構成を考えてみましょう。

Documents
├── Work
│   ├── report.docx
│   └── data.xlsx
│
└── Private
    ├── photo.jpg
    └── memo.txt

このような、

上
↓
枝分かれ
↓
さらに枝分かれ

という構造が木構造です。

この記事では、

木構造
↓
基本用語
↓
二分木
↓
完全二分木
↓
二分探索木
↓
バランス木
↓
木の走査

という順番で見ていきます。

1. 木構造とは

**木構造（Tree Structure）**とは、ノード同士を階層的につないだデータ構造です。

例えば、

という構造を考えます。

AからBとCへ枝分かれし、さらにBからDとEへ枝分かれしています。

リストでは、

A → B → C → D

のように基本的に一列につながっていました。

一方、木構造では、

        A
       / \
      B   C

のように複数方向へ枝分かれできます。

2. 木構造の基本用語

木構造を理解するためには、いくつかの用語を覚える必要があります。

次の木を使って確認してみましょう。

ノード

木を構成する一つ一つの要素を**ノード（Node）**と呼びます。

この木では、

A
B
C
D
E

がノードです。

ノード同士を結ぶ線は**エッジ（Edge）**または枝と呼びます。

根

木の一番上にあるノードを**根（Root）または根ノード（Root Node）**と呼びます。

        A ← Root
       / \
      B   C

この場合、

Root = A

です。

親と子

上下につながっているノードには親子関係があります。

        A
       / \
      B   C

Aから見ればBとCが子ノードです。

BやCから見ればAが親ノードです。

兄弟

同じ親を持つノードを**兄弟ノード（Sibling）**と呼びます。

        A
       / \
      B   C

BとCはどちらもAを親としているため、兄弟ノードです。

葉

子ノードを持たないノードを**葉（Leaf）または葉ノード（Leaf Node）**と呼びます。

この場合、

C
D
E

が葉ノードです。

内部ノード

葉ではなく、子を持っているノードを**内部ノード（Internal Node）**と呼ぶことがあります。

先ほどの木なら、

A
B

が内部ノードです。

3. 部分木とは

あるノードを根として、その下に続く木を**部分木（Subtree）**と呼びます。

例えば、

でBに注目すると、

      B
     / \
    D   E

が一つの部分木です。

二分木では、

左部分木
右部分木

という言葉が頻繁に登場します。

4. ノードの次数

あるノードが持っている子ノードの数を、そのノードの**次数（Degree）**と呼びます。

例えば、

        A
       / \
      B   C

Aには子が2つあるため、

Aの次数 = 2

です。

子を持たない葉ノードの次数は0です。

5. 深さと高さ

**深さ（Depth）**は、根からそのノードまでの距離を表します。

根の深さを0とする場合、

        A          深さ0
       / \
      B   C        深さ1
     / \
    D   E          深さ2

となります。

一方、木の**高さ（Height）**は、根から最も深い葉までの距離などで表されます。

なら、

A → B → D

と2本のエッジを通るため、エッジ数で数える定義では高さは2です。

ただし、深さや高さの数え方は問題によって定義が異なる場合があります。

試験では問題文の定義を確認することが重要です。

6. 二分木とは

**二分木（Binary Tree）**とは、

各ノードが最大2つの子ノードを持つ木

です。

例えば、

は二分木です。

各ノードの子は、

左の子
右の子

として区別されます。

7. 二分木をリストで表現する

前回のリストの記事でも触れましたが、二分木はポインタを使って表現できます。

単方向リストでは、

┌────────┬────────┐
│ データ │ 次     │
└────────┴────────┘

でした。

二分木では、

┌────────┬────────┬────────┐
│ 左     │ データ │ 右     │
└────────┴────────┴────────┘

とします。

例えば、

        A
       / \
      B   C

ならAは、

左 → B
右 → C

という2つの参照情報を持ちます。

子が存在しない場合は、

NULL

を設定できます。

8. 完全二分木とは

**完全二分木（Complete Binary Tree）**とは、

最下段以外はすべてノードが埋まり、最下段は左から順番に詰められている二分木

です。

例えば、

は完全二分木です。

一方、

は、最下段の左側が空いているのに右側へDが配置されているため、完全二分木ではありません。

🍯 完全二分木 = 下の段を左から詰める

と覚えると分かりやすいです。

9. 完全二分木と配列

完全二分木は配列を使って表現しやすい特徴があります。

例えば、

        A
       / \
      B   C
     / \ / \
    D  E F  G

を上から左順に配列へ入れると、

添字
0   1   2   3   4   5   6

[A][B][C][D][E][F][G]

となります。

添字を0から始める場合、ノードiの子は、

左の子
2i + 1

右の子
2i + 2

で求められます。

また、i > 0のノードの親は、

floor((i - 1) / 2)

で求められます。

この特徴は**ヒープ（Heap）**を理解するときにも重要になります。

10. 二分探索木とは

**二分探索木（Binary Search Tree：BST）**とは、データの大小関係を利用して構成する二分木です。

基本的には各ノードについて、

左部分木
<
親
<
右部分木

となるようにデータを配置します。

例えば、

という構造です。

8より小さい値は左側、

2
4
6

8より大きい値は右側、

10
12
14

にあります。

※同じ値をどのように扱うかは実装によって異なります。

11. 二分探索木でデータを探す

先ほどの木から10を探してみます。

まず8と比較します。

10 > 8

なので右へ進みます。

次に12と比較します。

10 < 12

なので左へ進みます。

すると10が見つかります。

8
↓ 右
12
↓ 左
10

このように大小関係を利用して探索する方向を絞り込めます。

12. 二分探索木の計算量

二分探索木がバランスよく構成されている場合、探索に必要な時間はおおよそ、

O(log n)

となります。

これは、

全体
↓
左右どちらか
↓
さらに左右どちらか
↓
さらに左右どちらか

と探索範囲を絞っていけるからです。

13. 二分探索木が偏る問題

二分探索木だからといって、必ず高速とは限りません。

例えば、

のような木を考えます。

ほとんど、

1 → 2 → 3 → 4 → 5

という連結リストと同じ状態です。

5を探す場合、

1
↓
2
↓
3
↓
4
↓
5

と順番に調べることになります。

このように木が偏ってしまうと、探索の計算量は最悪、

O(n)

となります。

そこで登場するのがバランス木です。

14. バランス木とは

**バランス木（Balanced Tree）**とは、

木が一方向へ極端に偏らないように、高さを抑える仕組みを持った木

です。

例えば、

のような木は大きく偏っています。

一方、

のように左右へデータが分散していれば、木の高さを小さくできます。

さらにバランスがよければ、

のような形になります。

重要なのは、左右を完全に同じ形にすることではありません。

探索性能が大きく低下するほど木が偏らないようにする

という考え方です。

15. なぜバランスが重要なの？

例えば、15個のデータが一方向に並んでしまった場合、

最悪の場合、目的の値を探すために多くのノードを調べる必要があります。

一方、バランスよく配置されていれば、

            8
         /     \
        4       12
      /  \     /  \
     2    6   10   14
    / \  / \  / \  / \
   1  3 5  7 9 11 13 15

のようにできます。

15を探す場合でも、

と少ない比較回数で到達できます。

つまり、

木が偏る
↓
木が高くなる
↓
探索に時間がかかる

のに対して、

バランスを保つ
↓
木の高さを抑える
↓
探索を効率よく行える

という関係があります。

16. 平衡二分探索木

二分探索木の性質を持ちながら、木が極端に偏らないように調整するものを平衡二分探索木と呼びます。

代表的なものには、

AVL木
赤黒木

などがあります。

これらは、

左 < 親 < 右

という二分探索木の性質を維持しながら、木の高さが大きくなりすぎないように調整します。

その結果、探索だけでなく、挿入や削除も効率よく行えるようにします。

17. AVL木とは

代表的なバランス木が**AVL木（AVL Tree）**です。

AVL木は、

各ノードについて、左部分木と右部分木の高さの差が大きくならないように調整する二分探索木

です。

具体的には、各ノードについて左右の部分木の高さの差が、

-1
0
+1

の範囲になるように保ちます。

例えば、

は左右の高さがバランスよく保たれています。

18. 平衡係数とは

AVL木では、左右の部分木の高さの差を**平衡係数（Balance Factor）**として扱います。

例えば、

平衡係数
=
左部分木の高さ - 右部分木の高さ

と定義する場合、

-1
0
+1

であればAVL木としてバランスが保たれています。

例えば、

        A
       / \
      B   C

で左右の高さが同じなら、

平衡係数 = 0

です。

なお、資料によっては右から左を引く定義もあります。

重要なのは符号そのものではなく、

左右の高さの差の絶対値が1以下

であることです。

19. AVL木にデータを追加すると？

例えば、

1
 \
  2

というAVL木へ3を追加したとします。

そのまま二分探索木のルールで追加すると、

となります。

これでは根である1の左右の高さの差が大きくなってしまいます。

そこでAVL木では、木の形を調整します。

この調整に利用されるのが**回転（Rotation）**です。

20. 木の回転とは

先ほどの、

を考えます。

この木を左方向へ回転させると、

    2
   / \
  1   3

となります。

大小関係を確認すると、

1 < 2 < 3

なので、二分探索木としての性質は維持されています。

それと同時に、木の高さも小さくなっています。

つまり回転とは、

二分探索木としての順序関係を維持しながら、木の形を組み替える操作

です。

21. 回転には複数のパターンがある

AVL木の回転には、偏り方によって複数のパターンがあります。

代表的には、

LL型
RR型
LR型
RL型

があります。

LL型

左の子のさらに左側へ偏った場合です。

右回転すると、

    2
   / \
  1   3

となります。

RR型

右の子のさらに右側へ偏った場合です。

左回転すると、

    2
   / \
  1   3

となります。

22. 二重回転

単純な1回の回転では調整できない場合もあります。

例えばLR型です。

この場合、

① 左側の部分を左回転
② 全体を右回転

という2段階の調整を行います。

結果、

    2
   / \
  1   3

となります。

RL型では逆方向に同様の操作を行います。

応用情報では、まず、

AVL木では挿入・削除によってバランスが崩れた場合、回転によって調整する

という仕組みを理解しておきましょう。

23. バランス木の計算量

バランスを保った二分探索木では、木の高さをおおよそ、

O(log n)

に抑えることができます。

そのため、

探索
挿入
削除

を一般に、

O(log n)

で行えるように設計されています。

通常の二分探索木では、偏ると最悪、

O(n)

でした。

整理すると、

構造	探索
バランスのよい二分探索木	O(log n)
偏った二分探索木	最悪O(n)
AVL木	O(log n)

となります。

24. 赤黒木とは

もう一つ代表的な平衡二分探索木として**赤黒木（Red-Black Tree）**があります。

各ノードに、

赤
黒

という情報を持たせ、一定の規則を守ることで木の高さが極端に大きくならないようにします。

AVL木と同じく、

探索
挿入
削除

を効率よく行うためのデータ構造です。

応用情報の学習では、まず、

AVL木
→ 左右部分木の高さを意識して調整

赤黒木
→ ノードの色とルールを利用して調整

という違いを押さえておけば、全体像を理解しやすくなります。

25. バランス木と完全二分木は違う

ここは混同しやすいポイントです。

完全二分木とバランス木は同じ意味ではありません。

完全二分木は、

最下段以外を埋める
+
最下段を左から詰める

というノードの配置についての条件です。

一方、バランス木は、

木が極端に偏らない
↓
高さを抑える

ことを目的としています。

つまり、

完全二分木
→ ノードの配置に関する特徴

バランス木
→ 木の高さ・偏りを抑える考え方

です。

🍯 「完全」と「バランス」は別物

と覚えておきましょう。

26. 木を走査する

木のすべてのノードを順番に処理することを**木の走査（Tree Traversal）**と呼びます。

二分木では代表的に、

前順
間順
後順

があります。

英語では、

Preorder
Inorder
Postorder

です。

27. 前順走査

**前順走査（Preorder Traversal）**では、

① 根
② 左部分木
③ 右部分木

の順番で処理します。

つまり、

根 → 左 → 右

です。

例えば、

なら、

A → B → D → E → C

となります。

28. 間順走査

**間順走査（Inorder Traversal）**では、

① 左部分木
② 根
③ 右部分木

の順番で処理します。

つまり、

左 → 根 → 右

です。

先ほどの木なら、

D → B → E → A → C

となります。

29. 二分探索木と間順走査

間順走査には重要な特徴があります。

二分探索木、

を間順走査すると、

2 → 4 → 6 → 8 → 10 → 12 → 14

となります。

つまり、二分探索木を間順走査すると、データを昇順に取り出せます。

🍯 二分探索木＋間順走査 = 昇順

は覚えておきたいポイントです。

30. 後順走査

**後順走査（Postorder Traversal）**では、

① 左部分木
② 右部分木
③ 根

の順番で処理します。

つまり、

左 → 右 → 根

です。

例えば、

なら、

D → E → B → C → A

となります。

31. 3つの走査方法を比較する

同じ木、

で比較すると、

走査	順番	結果
前順	根 → 左 → 右	A → B → D → E → C
間順	左 → 根 → 右	D → B → E → A → C
後順	左 → 右 → 根	D → E → B → C → A

覚え方は、

前順
→ 根が前

間順
→ 根が真ん中

後順
→ 根が後ろ

です。

32. 木の走査と再帰

木構造の走査は再帰処理と非常に相性がよいです。

例えば前順走査なら、

前順走査(ノード)
    ノードを処理
    左部分木を前順走査
    右部分木を前順走査

と考えられます。

木構造は、

大きな木
↓
左側にも木
右側にも木

という再帰的な構造を持っているためです。

再帰処理ではスタックが利用されるため、

スタック
↓
再帰
↓
木の走査

と、これまで学んできた内容がつながります。

33. 深さ優先探索

木の枝をできるだけ深く進んでから戻る方法を**深さ優先探索（Depth-First Search：DFS）**と呼びます。

例えば、

なら、

A
↓
B
↓
D

と深い方向へ進み、行き止まりになったら戻ります。

DFSは、

再帰

または、

スタック

を利用して実装できます。

34. 幅優先探索

同じ深さのノードを順番に処理する方法を**幅優先探索（Breadth-First Search：BFS）**と呼びます。

例えば、

        A
       / \
      B   C
     / \ / \
    D  E F  G

なら、

A
↓
B → C
↓
D → E → F → G

という順番です。

幅優先探索ではキューを利用できます。

つまり、

DFS
→ スタック・再帰

BFS
→ キュー

という関係です。

35. 木構造はどこで使われる？

木構造はさまざまな場面で利用されます。

代表的なのがファイルシステムです。

/
├── home
│   ├── user1
│   └── user2
│
└── var
    └── log

ほかにも、

HTML/XMLなどの階層構造
組織図
データベースの索引
検索処理
構文木

などで木構造の考え方が利用されます。

36. 応用情報で押さえたいポイント

木構造については、まず、

根
親
子
兄弟
葉
部分木
深さ
高さ

という基本用語を理解します。

二分木では、

1ノードにつき最大2つの子

です。

完全二分木は、

最下段以外を埋める
+
最下段を左から詰める

です。

二分探索木は、

左 < 親 < 右

という大小関係を利用します。

ただし、普通の二分探索木は、

木が偏る
↓
探索が最悪O(n)

となる可能性があります。

そこで、

バランス木
↓
木の高さを抑える
↓
探索などを効率化

という考え方が登場します。

代表例が、

AVL木
赤黒木

です。

AVL木ではバランスが崩れた場合、

回転

によって木の形を調整します。

木の走査は、

前順
根 → 左 → 右

間順
左 → 根 → 右

後順
左 → 右 → 根

です。

探索方法については、

DFS
→ スタック・再帰

BFS
→ キュー

も押さえておきましょう。

37. まとめ

木構造は、

データ同士の階層関係を表現するデータ構造

です。

基本的には、

という構造を持ちます。

二分木では、一つのノードが最大2つの子を持ちます。

ノード
├─ 左の子
└─ 右の子

二分探索木では、

左 < 親 < 右

という大小関係を利用して探索します。

ただし木が偏ると、

O(log n)
↓
最悪 O(n)

まで探索性能が低下する可能性があります。

そこでバランス木では、木の高さを抑えることで効率的な探索を実現します。

この記事で覚えること

木構造は階層的なデータ構造
一番上のノードを根という
子を持たないノードを葉という
親・子・兄弟・部分木という関係がある
二分木は一つのノードが最大2つの子を持つ
完全二分木は最下段を左から詰める
完全二分木は配列で表現しやすい
二分探索木では「左 < 親 < 右」の関係を利用する
バランスのよい二分探索木では探索を効率化できる
偏った二分探索木では探索が最悪O(n)になる
バランス木は木の高さが極端に大きくならないようにする
AVL木は代表的な平衡二分探索木
AVL木では左右部分木の高さの差を小さく保つ
バランスが崩れた場合は回転によって調整する
AVL木の回転にはLL・RR・LR・RL型がある
赤黒木も代表的な平衡二分探索木
完全二分木とバランス木は別の概念
前順は「根 → 左 → 右」
間順は「左 → 根 → 右」
後順は「左 → 右 → 根」
二分探索木を間順走査すると昇順に取り出せる
DFSはスタック・再帰と相性がよい
BFSはキューと相性がよい

🍯 はちみつメモ

二分探索木は「左は小さい、右は大きい」で探しやすくする。でも木が一本道になったら、その強みがなくなる。そこで木の高さを抑えるのがバランス木。AVL木では、偏ってきたら「回転」して木を立て直す。