木構造（ツリー）完全ガイド：種類・基本操作・計算量・実装上の注意をわかりやすく解説
エバープレイ編集部木構造とは
木構造（ツリー構造、tree）は、データを階層的に表現するための基本的なデータ構造の一つです。数学的には「サイクルのない連結グラフ」として定義され、計算機科学では通常「根（root）を持つ有向の階層構造」として扱われます。ノード（節点）とそれらを繋ぐエッジ（辺）から成り、親子関係で表現されます。木構造はファイルシステム、HTMLのDOM、コンパイラの抽象構文木（AST）、データベースのインデックス、検索エンジンのオートコンプリートなど、幅広い用途で使われます。
基本用語
- ノード（節点）: 木の各要素。値や参照を持つ。
- 根（root）: 親を持たないノード。木の最上位。
- 親（parent）・子（child）: エッジで直接つながる上下関係。
- 葉（leaf）: 子を持たないノード（末端ノード）。
- 深さ（depth）: 根からそのノードまでのエッジ数。
- 高さ（height）: ノードから葉までの最大エッジ数。木全体の高さは根の高さ。
- 次数（degree）: ノードが持つ子の数。木の次数は最大次数。
- 部分木（subtree）: 任意のノードとそのすべての子孫からなる木。
- パス（path）: ノード間をたどる経路。根から葉のパスは根路（root-to-leaf path）。
代表的な木の種類と特徴
- 一般木（n-ary tree）：各ノードが任意の個数の子を持てる。階層データの自然な表現。
- 二分木（binary tree）：各ノードが最大2つの子（左と右）を持つ。探索や表現が単純で、再帰的アルゴリズムが使いやすい。
- 二分探索木（BST: Binary Search Tree）：各ノードの左部分木のキーはノードのキーより小さく、右部分木のキーは大きいという性質を持つ。平均的に探索・挿入・削除はO(log n)だが、偏るとO(n)になる。
- 平衡二分木（AVL木、赤黒木など）：高さを制御して最悪時間計算量をO(log n)に保証する。AVLは部分木高さの差が1以下、赤黒木はより緩い色ベースのルールで挿入/削除を効率化。
- B木/B+木：ディスクアクセスを最適化する多分岐木。データベースやファイルシステムで主に利用される。ノードは複数のキーと子を持ち、枝分かれ度を大きくすることでディスクI/Oを削減する。
- ヒープ（Heap）：完全二分木の形で、親ノードが子よりも小さい（または大きい）というヒープ条件を満たす。優先度付きキューの実装に利用される。挿入・最大(最小)取り出しはO(log n)。
- トライ（Trie）：文字列の接頭辞を共有する木。文字列検索・前方一致（prefix）検索に非常に高速（キー長mに対してO(m)）で、オートコンプリートや辞書に利用される。圧縮版に「ラディックス木（Radix tree）」がある。
- セグメント木・フェニックツリー（BIT）：区間・累積和などの範囲クエリを高速に処理するための木構造。セグメント木はO(log n)で区間クエリ・更新が可能。フェニックツリーはBITとも呼ばれ、配列ベースで実装される。
- サフィックスツリー・サフィックス配列：文字列のすべての接尾辞を木（または配列）で構成する。最長共通部分列や検索を線形時間に近い時間で行える。UkkonenアルゴリズムでO(n)構築が可能（サフィックスツリー）。
- 空間分割木（k-d tree など）：k次元空間を分割して近傍探索（NN探索）に用いる。高次元では効率が落ちる点に注意。
基本操作とアルゴリズム
- 探索（search）：BSTでは比較に基づいて枝を辿る。平均O(log n)、最悪O(n)。トライではキー長mに対してO(m)。
- 挿入・削除（insert/delete）：BSTは位置探索後に挿入。削除は葉または子を持つノードの処理（置換や結合）が必要。平衡木は回転などでバランスを保つ。
- 走査（traversal）：
- 深さ優先探索（DFS）: 前順（pre-order）、中順（in-order）、後順（post-order）
- 幅優先探索（BFS）: レベル順走査（キュー利用）
- Morris走査: スタックや再帰を使わないO(1)追加メモリのin-order走査
- シリアライズ/デシリアライズ：木を保存・送信するためには走査順にノードとnullマーカーを記録する手法（例：preorder + null）や、レベル順で空を表す方法が使われる。
- 平衡化（rebalancing）：AVLの回転、赤黒木の再色付けと回転、B木の分割/結合など。これらは木の高さを抑えることで最悪計算量を保証する。
実装上の考慮点
- ノードはポインタ（参照）で子へのリンクを持つことが多いが、ヒープやフェニックツリー、配列ベースの完全二分木は配列で表現することがある（親子のインデックス計算が可能）。
- 左子-右兄弟表現（left-child right-sibling）を使うと、任意分岐の木を二分木として扱える。
- 再帰実装はコードが簡潔になるが、深い木ではスタックオーバーフローを招くことがある。ループと明示的なスタックやMorris法を検討する。
- 永続データ構造（不変木）では部分的な共有を用いて更新コストを抑えつつ完全な履歴を保持できる。
- ディスクやネットワークを介したデータ構造ではノードのサイズやアクセスパターンによりB木のような高分岐構造が有利になる。
- 並行処理下では読み書き同期（ロックやロックフリーデータ構造）やコピーオンライトの工夫が必要。
計算量のまとめ（代表的ケース）
- 二分探索木（平均）: 探索/挿入/削除 O(log n)
- 二分探索木（最悪＝偏り）: O(n)
- AVL/赤黒木: 常に O(log n)（最悪保証あり）
- ヒープ: insert O(log n)、extract-max/min O(log n)、find-max/min O(1)
- トライ: 長さmのキーに対して探索 O(m)（キー長に依存）
- セグメント木/フェニックツリー: 更新・区間クエリ O(log n)
代表的な利用例
- ファイルシステムのディレクトリ構造（階層的管理）
- DOM（HTML/XML）のツリー表現と操作（ブラウザやスクレイピング）
- コンパイラの抽象構文木（AST）: 構文解析後の意味解析・最適化に使用
- データベースインデックス（B木/B+木）：レンジ検索とディスク効率のために採用
- オートコンプリートや辞書（トライ）
- 優先度付きキュー（ヒープ）
- レンダリングやシーン管理（グラフィックスのシーングラフ）
- 機械学習の決定木・ランダムフォレスト
- 文字列検索や最長共通部分列（サフィックス木/配列）
注意点と落とし穴
- 平衡が崩れるとパフォーマンス劣化（BSTの最悪ケース）。適切な平衡化アルゴリズムの選択が重要。
- 再帰深度の問題。とくにイメージの深い階層データではループ実装や明示的スタックを検討する。
- メモリ消費。トライなどはノード数が多くなるとメモリを大量に使う。圧縮表現（ラディックス木、マップ圧縮）やポインタ削減が有効。
- 並列更新時の整合性。分岐・結合の原子的な扱いやロック設計が必要。
まとめ
木構造は階層的な情報を自然に扱える強力な抽象であり、多様な派生とアルゴリズムが存在します。用途やアクセス特性（読み込み中心か更新が多いか、メモリ内かディスクベースか、キーの性質はどうか）に応じて、二分木・平衡木・B木・トライ・ヒープ・セグメント木など最適な型を選ぶことが重要です。設計段階で高さ（深さ）やメモリ、並列性、入出力コスト（ディスクI/O）を考慮すると、実運用での性能と信頼性が大きく変わります。
参考文献
- 木構造 - Wikipedia（日本語）
- 二分木 - Wikipedia（日本語）
- 二分探索木 - Wikipedia（日本語）
- AVL tree - Wikipedia（英語）
- Red–Black tree - Wikipedia（英語）
- B-tree - Wikipedia（英語）
- MDN: Document Object Model (DOM) - Mozilla Developer Network（日本語）
- Trie - Wikipedia（英語）
- Segment tree - Wikipedia（英語）
- Fenwick tree - Wikipedia（英語）
- Suffix tree - Wikipedia（英語）
投稿者プロフィール
