1.2.4. 木構造 | ITQ Techpedia

1. 概要

　木構造（Tree Structure）は、データ構造の一種であり、階層的な関係を表現するための非線形データ構造です。木構造は根（ルート）から始まり、枝（エッジ）によって複数の節（ノード）が接続され、最終的に葉（リーフ）と呼ばれる末端ノードに至ります。

　木構造はコンピュータサイエンスの基礎となる重要なデータ構造であり、ファイルシステム、データベースのインデックス、構文解析、検索アルゴリズムなど、多くの場面で応用されています。木構造を理解することは、効率的なアルゴリズムの設計や実装において不可欠です。

2. 詳細説明

2.1. 木構造の基本用語と概念

　木構造は以下の要素から構成されています：

根（ルート）：木の最上位に位置するノード
枝（エッジ）：ノード間を接続する線
葉（リーフ）：子ノードを持たない末端ノード
内部ノード：葉ではないノード（子を持つノード）
親ノード：あるノードに対して上位に接続されているノード
子ノード：あるノードから枝で接続された下位のノード
兄弟：同じ親を持つノード同士
深さ：根からあるノードまでの経路の長さ
高さ：木の最も深い部分の深さ

図1: 木構造の基本用語

2.2. 木構造の種類

2.2.1. 2分木（バイナリツリー）

　２分木（にぶんぎ）は、バイナリーツリー（binary tree）とも呼ばれます。
　各ノードが最大2つの子ノード（左の子と右の子）を持つ木構造です。2分木はシンプルな構造ながら、多くの応用があります。

2.2.2. 完全2分木（完全バイナリツリー）

　最下層を除くすべての層が完全に埋まっており、最下層は左から順に埋まっている2分木です。ヒープデータ構造の実装などで使用されます。

図2: 2分木と完全2分木の比較

２分木については以下をご参照ください。

2分木を理解する

2.2.3. バランス木

　すべての葉ノードの深さがほぼ同じになるように調整された木構造です。これにより検索や挿入、削除などの操作が効率的に行えます。代表的なバランス木にはAVL木や赤黒木などがあります。

図3: バランス木と非バランス木の比較

2.2.4. 赤黒木

　赤黒木は自己平衡型の2分探索木で、各ノードは赤または黒で色付けされています。次の性質を保持します：

各ノードは赤か黒
根ノードは黒
すべての葉（NILノード）は黒
赤ノードの子は黒（赤ノードが連続しない）
根から任意の葉までの黒ノードの数（黒高さ）は同じ

　これらの性質により、最悪の場合でも操作の時間計算量がO(log n)となります。

2.2.5. 順序木（ordered tree）

　各ノードの子ノードに順序が定義されている木構造です。子ノードの順番が意味を持ちます。

2.2.6. 多分木（n分木）

　各ノードが最大n個の子ノードを持つことができる木構造です。B木はこの一種であり、ディスクアクセスを最小化するために設計されたバランス探索木です。

2.2.7. 探索木

　データの検索を効率的に行うための木構造です。代表的なものに2分探索木があります。

2.2.8. 2分探索木（バイナリサーチツリー）

　次の性質を持つ2分木です：

左の子孫のすべての値 < 親ノードの値 < 右の子孫のすべての値

　この性質により、検索が効率的に行えます。

図4: 2分探索木の例

2.2.9. B木

　ディスクベースのデータベースやファイルシステムで使用される自己平衡型の探索木です。1つのノードに複数のキーと子ノードへの参照を格納でき、効率的なディスクI/Oを実現します。

図5: B木の構造

2.2.10. AVL木

　各ノードの左右の部分木の高さの差が1以下であることを保証するバランス2分探索木です。挿入や削除操作後に自動的にバランスを調整します。

図6: AVL木の回転操作

木構造の種類	特徴	長所	短所	主な応用
2分木	各ノードは最大2つの子を持つ	シンプルで実装が容易	バランスが保証されない	式の表現、基本的なデータ構造
完全2分木	最下層を除き完全に埋まっている	配列での実装が効率的	動的な挿入・削除が難しい	ヒープ、優先度付きキュー
2分探索木	左<親<右の順序関係を持つ	検索・挿入・削除がO(h)時間	偏りがあると性能劣化	辞書、シンボルテーブル
AVL木	自己平衡型2分探索木、高さ差≦1	常に平衡状態を保つ	回転操作のオーバーヘッド	データベース、メモリ管理
赤黒木	自己平衡型2分探索木、色による制約	AVL木より挿入・削除が高速	実装が複雑	多くの言語のマップ実装、Linux仮想メモリ
B木	多分木、ノードに複数キー	ディスクI/Oの最小化	メモリ使用量が多い	データベース、ファイルシステム
多分木	各ノードがn個以下の子を持つ	幅広いデータ構造の表現	メモリ効率が低い場合あり	ファイルシステム、XML/HTML DOM
順序木	兄弟間に順序関係がある	順序に意味を持たせられる	一般的な操作が複雑になる	構文解析、XMLツリー

表1: 主な木構造の特徴比較表

2.3. 木の巡回法

　木構造の全ノードを訪問する方法には、大きく分けて深さ優先探索と幅優先探索があります。

2.3.1. 深さ優先探索（DFS: Depth-First Search）

　深さ優先探索では、可能な限り深く進んでから戻るというアプローチを取ります。2分木の場合、以下の3種類の巡回順序があります：

先行順（前順、プレオーダー）：親 → 左の子 → 右の子
中間順（中順、インオーダー）：左の子 → 親 → 右の子
後行順（後順、ポストオーダー）：左の子 → 右の子 → 親

図7: 先行順巡回の図解

図8: 中間順巡回の図解

図9: 後行順巡回の図解

2.3.2. 幅優先探索（BFS: Breadth-First Search）

　幅優先探索では、同じ深さのノードをすべて訪問してから次の深さに進みます。レベル順（階層順）巡回とも呼ばれます。

図10: 幅優先探索の図解

2.4. 節の追加や削除

　木構造、特に2分探索木やバランス木では、データの追加や削除がよく行われる操作です。

2.4.1. 節の追加

　2分探索木への節の追加は、以下のステップで行います：

根から始め、追加する値と各ノードの値を比較
値が小さければ左へ、大きければ右へ移動
適切な位置（葉ノードの位置）に到達したら、新しいノードを追加

　バランス木（AVL木など）の場合は、追加後にバランスを保つための回転操作が必要になる場合があります。

図11: 節の追加の図解

2.4.2. 節の削除

　2分探索木からの節の削除は、次の場合分けで処理します：

削除するノードが葉の場合：単純に削除
削除するノードが1つの子を持つ場合：ノードを削除し、その子を親に接続
削除するノードが2つの子を持つ場合：ノードの中間順での後継ノード（右部分木の最小値）と値を交換し、後継ノードを削除

　バランス木の場合は、削除後にバランスを保つための回転操作が必要になる場合があります。

図12: 節の削除の図解

2.5. ヒープの再構成

　ヒープは完全2分木を用いて実装される優先度付きキューの一種です。ヒープには最小ヒープと最大ヒープがあります。

　ヒープの主な操作には以下があります：

挿入：
- 最後の位置（配列の末尾）に要素を追加
- ヒープ条件が満たされるまで上方向にバブルアップ（上昇）
最大値/最小値の削除：
- 根の値を取り出す
- 最後の要素を根に移動
- ヒープ条件が満たされるまで下方向にバブルダウン（下降）
ヒープの再構成（ヒープ化）：
- 任意の配列からヒープを構築するプロセス
- ボトムアップアプローチが効率的：最後の非葉ノードから始めて根に向かって各部分木をヒープ条件を満たすように調整

図13: ヒープの構造と操作

2.5.1. ヒープソート

　ヒープソートはヒープデータ構造を利用したソートアルゴリズムです。手順は以下の通りです：

配列をヒープに変換（ヒープ化）
最大ヒープから最大値（根）を取り出し、配列の末尾に配置
ヒープサイズを1減らし、ヒープを再構成
すべての要素がソートされるまで2-3を繰り返す

　ヒープソートの時間計算量はO(n log n)で、安定ではありませんが追加のメモリをほとんど必要としないという特徴があります。

3. 応用例

3.1. ファイルシステム

　コンピュータのファイルシステムは、ディレクトリとファイルの階層構造を表現するために木構造（具体的には多分木）を使用しています。これにより、ファイルやフォルダを効率的に整理・検索できます。

3.2. データベースインデックス

　B木やB+木はデータベース管理システムでインデックスとして広く使用されています。これらの木構造により、大量のデータから特定のレコードを高速に検索できます。

3.3. 構文解析

　プログラミング言語のコンパイラやインタプリタでは、ソースコードの構文を解析する際に構文木（パースツリー）が使用されます。これは順序木の一種です。

3.4. 圧縮アルゴリズム

　ハフマン符号化などのデータ圧縮アルゴリズムでは、文字の出現頻度に基づいて2分木（ハフマン木）を構築し、効率的な符号化を実現しています。

3.5. 人工知能

　決定木は機械学習の分類アルゴリズムとして使用されています。また、ゲームAIでのミニマックスアルゴリズムやアルファベータ剪定も木構造を利用しています。

応用例	使用される木構造	理由・特徴	具体例
ファイルシステム	多分木・B木	階層構造の表現、ディスクI/O最適化	Unix/Linuxファイルシステム、NTFS、ext4
データベースインデックス	B木・B+木	ブロックアクセスの最小化、範囲検索の効率化	MySQL(InnoDB)、PostgreSQL、Oracle
構文解析	順序木（構文木）	文法構造の階層的表現	コンパイラ、インタプリタ、JSON/XMLパーサー
データ圧縮	2分木（ハフマン木）	出現頻度に基づく可変長符号化	JPEG、MP3、ZIP、GZIP
ネットワークルーティング	トライ木（Trie）	IPアドレスの効率的な検索	ルーターのルーティングテーブル
機械学習	決定木	特徴に基づく分類の視覚化と判断	ランダムフォレスト、勾配ブースティング決定木
GUI要素	多分木	階層的なUIコンポーネントの表現	DOM、ウィジェットツリー
ゲームAI	ミニマックス木	ゲーム状態と可能手の探索	チェス、将棋、囲碁のAI
メモリ管理	AVL木・赤黒木	動的メモリブロック管理の効率化	メモリアロケータ、ガベージコレクタ
計算幾何学	kd木・四分木	多次元空間の効率的な分割と検索	近傍探索、衝突検出、3Dレンダリング

表2: 木構造の応用例とその特徴

4. 例題

例題1: 2分木の巡回

次の2分木について、先行順、中間順、後行順での巡回結果をそれぞれ示せ。

    A
   / \
  B   C
 / \   \
D   E   F

解答例

先行順: A, B, D, E, C, F
中間順: D, B, E, A, C, F
後行順: D, E, B, F, C, A

例題2: 2分探索木の構築

次の数値を順に2分探索木に挿入した場合の最終的な木の形を示せ。 50, 30, 70, 20, 40, 60, 80

解答例

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

例題3: ヒープの再構成

次の配列を最大ヒープに再構成する過程を示せ。 [4, 10, 3, 5, 1]

解答例

配列を完全2分木として表現:

最後の非葉ノードから根に向かってヒープ条件を適用:
- インデックス1（値10）は既にヒープ条件を満たしている
- インデックス0（値4）で比較: 4 < 10, 4 > 3 なので4と10を交換

さらに4を見ると、4 < 5 なので交換:

最終的な最大ヒープ: [10, 5, 3, 4, 1]

例題4: AVL木のバランス調整

次の操作を行った後のAVL木を示せ。空のAVL木に10, 20, 30, 40, 50の順に挿入する。

解答例

10を挿入: 10
20を挿入: 10 -> 20
30を挿入: バランス崩れるため左回転

   20
  /  \
 10   30

40を挿入: 20 -> 30 -> 40
50を挿入: バランス崩れるため左回転

      30
     /  \
    20   40
   /      \
  10       50

5. まとめ

　木構造は、階層的なデータを表現・操作するための基本的かつ強力なデータ構造です。本記事では、根、葉、枝などの基本要素から始まり、2分木、完全2分木、バランス木、順序木、多分木、探索木、2分探索木、B木、AVL木などの様々な種類の木構造について解説しました。

　また、深さ優先探索と幅優先探索という2つの基本的な巡回方法、および先行順、後行順、中間順という2分木特有の巡回順序についても説明しました。

　節の追加や削除、特に2分探索木とバランス木におけるそれらの操作と、ヒープデータ構造の再構成方法についても詳しく解説しました。

　木構造は理論的な概念にとどまらず、ファイルシステム、データベース、構文解析、人工知能など、情報処理のさまざまな分野で実際に応用されています。木構造の理解と適切な実装は、効率的なアルゴリズムの設計において不可欠な知識です。

参考文献

トーマス・H・コルメン他, “アルゴリズムイントロダクション第3版”, 近代科学社, 2013.（Amazonアソシエイトリンク）
石畑清, “アルゴリズムとデータ構造”, 岩波書店, 2016.（Amazonアソシエイトリンク）

※この記事にはAmazonアソシエイトのリンクが含まれています。購入された場合、収益の一部を得ることがあります。

2.1. 流れ図 >>