ツリー構造（木構造）完全ガイド：定義・用語・主要種類・実装とアルゴリズムの基礎
エバープレイ編集部ツリー構造とは — 概要
ツリー構造（ツリー、木構造）は、ITや情報工学で極めて頻繁に用いられるデータ構造の一つです。親子関係による階層的な表現が特徴で、ファイルシステムやDOM、データベースのインデックス、コンパイラの構文木など、さまざまな分野で利用されます。グラフ理論では「木」は循環を持たない連結グラフとして定義され、根付き木（rooted tree）はさらに根（root）を定めて方向付けした概念です。
基本概念と用語
- ノード（頂点）: ツリーの構成要素。情報を格納する単位。
- エッジ（辺）: 親子関係を表す接続。ツリーではノード数 n に対して辺数は n-1（連結な場合）。
- 根（root）: 根付き木で最上位に位置するノード。親を持たない。
- 親・子（parent / child）: 直接接続した上下関係。
- 葉（leaf、外部ノード）: 子を持たないノード。
- 内部ノード: 少なくとも1つの子を持つノード。
- 深さ（depth）: ルートからの経路長（一般にルートの深さは 0）。
- 高さ（height）: ノードから最も深い葉までの経路長。ツリー全体の高さは根の高さ。
- 部分木（subtree）: 任意のノードを根とするそのノード以下の木。
グラフ理論における定義と性質
グラフ理論では、木は以下のように同値な複数の定義を持ちます。
- 連結で循環（サイクル）を持たない無向グラフ。
- n 個のノードを持つ連結グラフの辺数が n−1 であるもの。
- 辺を 1 本追加すると必ずサイクルができるような最小の連結グラフ。
森林（forest）は木の集合であり、k 個の連結成分（木）を持つ n ノードの森林の辺数は n − k となります。
ツリーの種類（代表例）
- 根付き木（rooted tree）: 明確なルートを持つツリー。ほとんどのアルゴリズム実装はこれを想定します。
- 二分木（binary tree）: 各ノードが最大2個の子を持つ木。探索木（BST）、ヒープ、AVL木、赤黒木など多くの派生がある。
- 完全二分木・満二分木: 完全（complete）は左詰めでレベルが埋まる木、満（full/proper）は各内部ノードがちょうど2つの子を持つ木で、満二分木では葉 = 内部ノード + 1 が成り立つ。
- トライ（Trie）: 文字列集合を格納する木。接頭辞検索に強い。
- サフィックスツリー / サフィックス配列: 文字列処理（最長共通部分列等）で使われる高度な木構造。
- B木 / B+木: ディスクベースの索引構造。ノード当たり多数の子を持ち、平衡を保つことでI/Oを最小化する。
ツリーの表現方法
主な実装方法とその特徴：
- ポインタ方式（ノードに子ポインタ）:
- 各ノードが子への参照（ポインタ）を保持。可変形状の木に適する。
- メモリオーバーヘッドはポインタ数に依存。
- 配列（完全二分木向け）:
- 1ベースインデックスで親 = floor(i/2)、子 = 2i, 2i+1。0ベースでは親 = floor((i-1)/2)、子 = 2i+1, 2i+2。
- ヒープ実装などに適し、メモリアクセスの連続性で高速。
- 隣接リスト / 隣接配列（汎用グラフ表現）:
- ノード数 n、辺数 n−1 のため O(n) の空間で格納可能。
- 順序が重要な木（ordered tree）の場合、子リストの順番を保持する。
- 親ポインタ配列:
- 各ノードに親のインデックスだけを持たせる。メモリ効率は良いが子方向の列挙が遅い。
- 子-兄弟表現（left-child/right-sibling）:
- 任意の分岐数を持つ木を二分木として表現するテクニック。
基本操作とアルゴリズム
一般的な操作と計算量（n はノード数、h は高さ）：
- 探索（Traversal）:
- 深さ優先（DFS）: preorder, inorder（※二分木のみ）, postorder — 時間 O(n)、再帰またはスタックで実装。
- 幅優先（BFS / レベルオーダー）: キューを使う — 時間 O(n)。
- 検索（特に二分探索木）:
- 平均的には O(h)（平衡なら h=O(log n)）、最悪は O(n)（偏った木）。
- 挿入・削除（BST, AVL, 赤黒木）:
- BST の単純な挿入は平均 O(h)。平衡二分探索木（AVL, 赤黒木）は回転等で O(log n) を保証。
- 最小共通祖先（LCA）:
- 単純解は深さをそろえて親をたどる O(h)。
- 事前処理で高速化する手法: バイナリリフティング（O(n log n) 前処理、O(log n) クエリ）、Euler Tour + RMQ を用いた O(1) クエリ（O(n) 前処理）など。
- 平衡化（回転）: AVL・赤黒木などは挿入・削除後に回転を行い高さを O(log n) に保つ。
設計上の注意点とトレードオフ
- 高さの管理: 木の高さが操作性能に直結する。極端な偏り（リスト状）を防ぐために平衡化やランダム化が重要。
- メモリ対速度: ポインタ方式は柔軟だがポインタオーバーヘッドが大きい。配列は高速でキャッシュ効率が良いが完全木向け。
- ディスクI/O 最適化: データベースやファイルシステムではブロック単位で効率よく参照できるB木・B+木が好まれる。
- 順序性の保持: XMLやHTMLのDOMなど順序が重要な木では子順を保持する構造が必要。
- 永続性（Immutable / Persistent Trees）: 変更可能な構造ではないバージョンを保持したい場合、部分共有を利用する不変木（関数型データ構造）が使われる。
実世界での応用例
- ファイルシステム（ディレクトリ構造はツリー）
- DOM（HTML/XML の階層表現）
- 検索エンジンやDBの索引（B木、トライなど）
- コンパイラの構文木（AST: Abstract Syntax Tree）
- 決定木・ランダムフォレスト（機械学習）
- ゲームAIや探索空間の表現（探索木）
よくある混同と注意点
「ツリー」と「ツリー状に見えるが循環を含むグラフ」を混同しないこと。例えば、シンボリックリンクがあるファイルシステムは純粋な木ではなくグラフになります。また「二分木の inorder」は意味があるのは二分木に対してであり、一般の木では未定義です。さらに高さや深さの定義は文献によって差があるので、数式や評価を行う際は定義を明確にしておくことが重要です。
まとめ
ツリー構造は、階層的なデータ表現において最も基本的かつ重要な概念の一つです。理論的にはグラフ理論の中の重要なクラスであり、実装面では用途に応じて配列、ポインタ、B木、トライなど多様な表現が選ばれます。性能は主に木の高さに依存するため、用途に応じた平衡化や構造選択が設計上の鍵となります。
