木構造 (データ構造)

木構造（きこうぞう、英: tree structure）は、グラフ理論における「木」の概念を応用した、コンピュータサイエンスにおける基本的なデータ構造の一つです。階層的なデータ関係を表現するのに適しており、多くのアルゴリズムやシステム設計の基盤となっています。

基本的な概念と用語

木構造は、ノード（節点）とそれらを結ぶエッジ（枝）で構成されます。データ構造として利用される場合、通常は「根（ルート）」と呼ばれる特定のノードを起点とする根付き木として扱われます。

• 根ノード (Root node): 木の最上位に位置するノード。親を持たない唯一のノードです。
• 子ノード (Child node): あるノードから見て、直接つながっている下位のノード。
• 親ノード (Parent node): あるノードから見て、直接つながっている上位のノード。
• 葉ノード (Leaf node): 子ノードを持たないノード。末端に位置します。
• 内部ノード (Internal node): 葉ノード以外の、少なくとも1つの子を持つノード。
• 部分木 (Subtree): 木構造内の任意のノードを根と見なした際に形成される、それ以下のノード群による木構造。

ノード間の関係性は家系図になぞらえて表現され、あるノードから根までのエッジ数を深さ (depth)、そのノードから最も遠い葉までのエッジ数を高さ (height)と呼びます。

走査法

木構造の全ノードを体系的に訪問する処理を「走査（トラバーサル）」と呼びます。代表的な手法には以下のものがあります。

深さ優先探索 (DFS)

根から開始し、可能な限り深く潜ってから戻る手法です。訪問順序により、前順（根→左→右）、間順（左→根→右）、後順（左→右→根）に分類されます。

幅優先探索 (BFS)

根に近いノードから順に、レベルごとに訪問する手法です。

主な種類

木構造は用途に応じて様々な形態が存在します。

• 二分木 (Binary tree): 各ノードが最大2つの子を持つ木。二分探索木などが有名です。
• 平衡木 (Balanced tree): 葉の深さが均一になるよう調整された木。AVL木や赤黒木などが含まれ、探索効率の維持に寄与します。
• B木 (B-tree): 多分木の一種で、データベースのインデックスなどに広く利用されます。
• デジタル木 (Trie): 文字列の格納や検索に特化した木構造です。

応用例

木構造は、ディレクトリ構造（ファイルシステム）、構文解析における構文木、HTMLのDOMツリー、データベースのインデックスなど、階層的な情報を扱うあらゆる場面で活用されています。