1.2.4. 木構造

1. 概要

　木構造は、データを階層的に整理・管理するための基本的なデータ構造の一つです。木構造は、データ間の親子関係を表現しやすく、効率的なデータの検索や挿入、削除が可能となります。特に、ファイルシステムやデータベース、人工知能のアルゴリズムなど、さまざまな分野で広く応用されています。木構造を理解することで、効率的なアルゴリズム設計やデータ管理が可能となり、情報処理技術者試験においても重要な知識となります。

2. 詳細説明

2.1. 木構造の基本要素

根（ルート）: 木構造の最上位に位置するノードで、親を持たない唯一のノードです。
葉（リーフ）: 子を持たないノードのことを指します。データの終端を表します。
枝（エッジ）: ノード間を繋ぐリンクや接続を表します。親子関係を示します。

2.2. 木構造の種類

2.2.1. 2分木

　2分木は、各ノードが最大で2つの子ノードを持つことができる木構造です。子ノードは左部分木と右部分木として区別されます。

2.2.2. 完全2分木

　完全2分木は、2分木の特殊な形で、最下層を除くすべての層が完全に埋まっており、最下層のノードも左から順に詰められている構造です。この構造は配列で効率的に表現することができます。

2.2.3. バランス木

　バランス木は、各ノードの左右部分木の高さ差が一定範囲内に保たれるように構成された木構造です。これにより、データの検索や挿入、削除操作の効率を最適化します。代表的なバランス木としてAVL木や赤黒木があります。

2.2.4. 順序木

　順序木は、各ノードの子ノード間に順序が定義されている木構造です。子ノードの順序がアルゴリズムやデータ処理に影響を与える場合に使用されます。

2.2.5. 多分木

　多分木は、各ノードが2つ以上の子ノードを持つことができる木構造です。具体的には、B木やトライ木などが多分木の例として挙げられます。

2.2.6. 探索木と2分探索木

　探索木は、特定の規則に従ってノードが配置され、効率的なデータ検索を可能にする木構造です。

　2分探索木は、2分木の一種で、以下の特性を持ちます：

左部分木のすべてのノードの値は、親ノードの値よりも小さい。
右部分木のすべてのノードの値は、親ノードの値よりも大きい。

　この特性により、データの検索や挿入、削除が効率的に行えます。

2.3. 木の巡回法

　木構造内のすべてのノードを訪問する方法を木の巡回法と呼びます。主な巡回法には以下の3つがあります。

2.3.1. 先行順（Preorder）

現在のノードを訪問する。
左部分木を先行順で巡回する。
右部分木を先行順で巡回する。

用途: コピー操作や構造の再構築に適しています。

2.3.2. 中間順（Inorder）

左部分木を中間順で巡回する。
現在のノードを訪問する。
右部分木を中間順で巡回する。

用途: 2分探索木において、ノードの値を昇順（または降順）に取得する際に使用されます。

2.3.3. 後行順（Postorder）

左部分木を後行順で巡回する。
右部分木を後行順で巡回する。
現在のノードを訪問する。

用途: ノードの削除操作や評価式の計算に適しています。

2.3.4. 幅優先探索（Breadth-First Search）

　幅優先探索は、木の深さに沿って水平にノードを巡回します。具体的には、根から始めて、同じ深さのノードを左から右へ順に訪問し、次の深さへと移ります。

用途: 最短経路の探索やレベルごとのデータ処理に適しています。

2.3.5. 深さ優先探索（Depth-First Search）

　深さ優先探索は、可能な限り深くノードを訪問し、行き止まりに達したらバックトラックして次の経路を探索します。先行順、中間順、後行順は深さ優先探索の一種です。

用途: パズルの解決や組み合わせ問題の探索に適しています。

2.4. 節の追加や削除

　木構造における節（ノード）の追加や削除は、データの管理や構造の維持において重要な操作です。

2.4.1. ノードの追加

2分探索木の場合:
1. 根から始めて、追加する値と比較しながら左または右の部分木へ進む。
2. 適切な位置に新しいノードを挿入する。
3. 必要に応じてバランス調整を行う。

2.4.2. ノードの削除

2分探索木の場合:
1. 削除するノードを探索する。
2. ノードの子の数に応じて処理を行う：
  - 子がない場合: 直接ノードを削除。
  - 子が1つの場合: 子ノードで削除するノードを置き換える。
  - 子が2つの場合: 右部分木の最小値（または左部分木の最大値）でノードを置き換え、その最小値（最大値）のノードを削除。
3. 必要に応じてバランス調整を行う。

2.5. ヒープの再構成

　ヒープは、完全2分木の形を持ち、各ノードが特定の順序性を満たすデータ構造です。主に優先度付きキューの実装に用いられます。

最大ヒープ: 親ノードの値が子ノードの値以上。
最小ヒープ: 親ノードの値が子ノードの値以下。

　ヒープの再構成は、ヒープの特性を維持するために行われます。

2.5.1. ヒープへの挿入

新しいノードをヒープの末尾に追加。
親ノードと比較しながら、特性が満たされるまでノードを上へ移動（ヒープ化）。

2.5.2. ヒープからの削除

根ノードを削除し、末尾のノードを根に移動。
子ノードと比較しながら、特性が満たされるまでノードを下へ移動（ヒープ化）。

3. 応用例

3.1. ファイルシステム

　ファイルシステムでは、ディレクトリとファイルの関係を表現するために多分木が用いられます。ディレクトリは子として複数のファイルやサブディレクトリを持つことができ、階層的なデータ管理が可能です。

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

　データベースにおいて、高速なデータ検索を実現するためにB木やB+木といったバランスされた多分木がインデックス構造として使用されます。これにより、大量のデータから目的の情報を迅速に取得できます。

3.3. コンパイラの構文解析

　コンパイラは、プログラムコードを解析して**抽象構文木（AST）**を生成します。ASTは、コードの構文的な構造を木構造で表現し、コードの解析や最適化、コード生成などの工程で活用されます。

3.4. 人工知能と機械学習

　決定木アルゴリズムは、機械学習における分類や回帰問題の解決に用いられます。データの特徴を基に条件分岐を行い、最終的な予測や判断を下すためのモデルを構築します。

3.5. ネットワークルーティング

　ネットワークルーティングプロトコルでは、トライ木を使用してIPアドレスのプレフィックスを効率的に検索し、パケットの転送先を決定します。

4. 例題

例題1

　以下の数列を2分探索木に挿入してください。

[50, 30, 70, 20, 40, 60, 80]

質問:

中間順（Inorder）で巡回した場合の出力を示してください。
先行順（Preorder）で巡回した場合の出力を示してください。
後行順（Postorder）で巡回した場合の出力を示してください。

回答例:

1. 中間順（Inorder）:

20, 30, 40, 50, 60, 70, 80

2. 先行順（Preorder）:

50, 30, 20, 40, 70, 60, 80

3. 後行順（Postorder）:

20, 40, 30, 60, 80, 70, 50

例題2

　以下の最大ヒープから根ノードを削除した後、ヒープを再構成してください。

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

質問:

ヒープ再構成後の木構造を示してください。

回答例:

根ノードの100を削除し、末尾の20を根に移動します。その後、以下の手順でヒープ化を行います。

再構成手順:

20（根）とその子ノード90, 80を比較。最大の90と交換。
20とその子ノード70, 60を比較。最大の70と交換。
20とその子ノード30, 20（存在しない）を比較。最大の30と交換。

最終的な木構造:

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

問題3

　幅優先探索を用いて以下の木構造を巡回した場合の出力を示してください。

質問:

幅優先探索の出力を示してください。

回答例:

幅優先探索の出力:

A, B, C, D, E, F, G

5. まとめ

　木構造は、データを階層的かつ効率的に管理するための重要なデータ構造であり、その理解は情報処理分野において不可欠です。さまざまな種類の木構造（2分木、完全2分木、バランス木、順序木、多分木、探索木、2分探索木）や、データの効率的な処理を可能にする木の巡回法（深さ優先探索、幅優先探索、先行順、中間順、後行順）を適切に使い分けることで、複雑なデータ処理やアルゴリズムの設計が容易になります。また、節の追加や削除、ヒープの再構成といった操作を理解し実装することで、データ構造の最適化と効率的なデータ管理が可能となります。これらの知識は、実際のシステム開発や情報処理技術者試験において重要な基礎となります。