2.1 木の主なコンポーネント
木構造は、特殊なグラフの一種であり、
非循環的かつ
連結です。木構造では、どのノードのペア間にも唯一の道が存在し、そのため
階層的な構造となります。
木の主なコンポーネント：
1. ノード:
- データを含む木の基本要素。
- 例えば、図の各円はノードを表します。
2. ルート:
- 親ノードを持たないノードです。木の始点となります。
- 例えば、図の最上部のノード。
3. 葉:
- 子ノードを持たないノードで、木の「端」に位置します。
- 例えば、図の下部のノード。
4. エッジ:
- ノード間の接続を示し、親子関係を定義します。
- 例えば、図でノードを結ぶ線。
5. 部分木:
- ノードとその全ての子孫から成る木の部分集合。
- 例えば、あるノードから始まる木の枝。
木の重要な特性:
1. 木の高さ:
- ルートから最も遠い葉までの道の長さ。
- 例えば、図の階層数。
2. ノードの深さ:
- ルートから該当ノードまでの道の長さ。
- 例えば、ルートから特定ノードまでの階層数。
2.2 二分木
いろいろな種類の木を区別できます。まずは一番簡単なものから始めましょう。
二分木は、各ノードが2つ以下の子ノードを持つ木で、それらは左子と右子と呼ばれます。
二分木の例:
特別な種類の二分木:
完全二分木:
最後のレベルを除いた全てのレベルが完全に埋められており、最後のレベルのノードはできるだけ左に配置されます。
完璧な二分木:
全ての内部ノードが正確に2つの子ノードを持ち、全ての葉が同じレベルにあります。
平衡二分木:
任意のノードの部分木の高さの差が1を超えません。
二分探索木:
任意のノードに対して、その左部分木には小さい値のノードのみが含まれ、右部分木には大きい値のノードのみが含まれます。
2.3 n-分木
n-分木は、各ノードがn個以下の子ノードを持つ木です。
特別な種類のn-分木:
1. 三分木 (Ternary Tree):
各ノードが3つ以下の子ノードを持ちます。
2. k-分木 (k-ary Tree):
各ノードがk個以下の子ノードを持ちます。
3-分木の例（各ノードが3つ以下の子ノードを持つ）:
2.4 木の利用例
1. ファイルシステム
木構造の利用: オペレーティングシステム内でのファイルとフォルダの階層的な構造の表現。
ルートノードはルートディレクトリを表し、内部ノードはフォルダ、葉はファイルを表します。操作にはファイルとフォルダの作成、削除、移動が含まれます。
2. 意思決定木
木構造の利用: 分析と機械学習における意思決定。
内部ノードは質問や条件を表し、枝は可能な回答、葉は最終的な決定や行動を表します。例えば、医学における症状に基づく病気の診断。
3. XML/HTML ドキュメント
木構造の利用: XMLやHTML形式でのデータの構造的な表現。
ルートノードは全ドキュメントを表し、内部ノードはタグや要素、葉はテキストノードや属性を表します。これにより、ドキュメントの内容の解析と操作が簡単になります。
4. 組織構造
木構造の利用: 組織や企業の階層の表現。
ルートノードはCEOを表し、内部ノードは管理者や部署、葉は従業員を表します。これにより、組織構造の視覚化と管理が容易になります。
5. チェスゲーム
木構造の利用: ゲーム内の可能な動きの表現。
ルートノードはゲームの開始状態を表し、内部ノードは可能な動き、葉はゲームの最終状態を表します。これにより、チェスプログラムでの戦略の計画と意思決定を支援します。
GO TO FULL VERSION