木構造とは？

詳細解説

木構造（Tree）は、根（ルート）ノードを頂点に、各ノードが0個以上の子ノードを持つ階層的なデータ構造です。親を持たないノードがルート、子を持たないノードが葉（リーフ）です。重要な用語：深さ（あるノードからルートまでの辺の数）、高さ（ルートから最も深い葉までの辺の数）、次数（ノードの子の数）。代表的な木の種類：2分木（各ノードの子が最大2つ）、2分探索木（左の子 < 親 < 右の子を維持する2分木、探索O(log n)）、ヒープ（親が子より常に大きい/小さい完全2分木、優先度付きキューの実装に使用）、B木・B+木（データベースのインデックスに使用）。木の探索方法：前順（Pre-order: 根→左→右）、中順（In-order: 左→根→右）、後順（Post-order: 左→右→根）、幅優先探索（BFS: 同じ深さのノードを横断）、深さ優先探索（DFS: 深い方向を優先）。FE試験では2分探索木への要素追加後の木構造トレース、木の高さの計算、中順探索の結果（昇順になる）が頻出です。ファイルシステム（フォルダの階層）も木構造の実例です。

FE試験での出題ポイント

• 12分探索木：左 < 親 < 右を維持。中順探索で昇順に並ぶ
• 2前順・中順・後順の探索順序の違い（実際の出力をトレース）
• 3ヒープ：親 >= 子（最大ヒープ）を維持。優先度付きキューの実装
• 4B+木：データベースのインデックス構造（実務接続の重要知識）

関連用語