二分木の基礎から応用まで徹底解説：定義・走査・表現方法・BSTと平衡化・実装のポイント
エバープレイ編集部はじめに — 「二叉木（二分木）とは」
二叉木（一般的には「二分木」と呼ばれます）は、各ノードが子ノードを最大で2つまで持てる木構造（ツリー構造）の一種です。データ構造として非常に基本的かつ重要で、探索・整列・優先度付きキュー・式の解析・圧縮アルゴリズムなど、幅広いアルゴリズム・システムの基礎になっています。本稿では定義、分類、表現方法、走査（トラバース）、主要な応用、実装上の注意点までを深掘りして解説します。
基本定義と用語
- ノード（節点）: 木の各要素。値（キー）と子ノードへの参照を持つ。
- 根（root）: 木の最上位のノード。親を持たない。
- 葉（leaf）: 子を持たないノード。
- 深さ（depth）: 根からそのノードまでの辺の数。
- 高さ（height）: 木全体の高さは根から最も深い葉までの辺の最大数（実装によってはノード数ベースで数えることもある）。
- 部分木（subtree）: 任意のノードを根とする木。
二分木の主な種類（用語の注意）
日本語の文献では用語の使われ方に揺れがあるため、英語の呼称を併記しつつ整理します。
- 一般的な二分木（binary tree）: 各ノードが最大で2つの子を持つ木。
- 満二分木 / Full (proper) binary tree: すべてのノードが子を0個または2個持つもの。
- 完全二分木（complete binary tree）: 多くの日本語文献で「完全二分木」と表記されることがありますが、ここでは「完備二分木（complete binary tree）」として定義します。全レベルが満たされるか、最後のレベルのみ右側ではなく左側から順に埋まっている木。配列表現に適する。
- 完全（Perfect）二分木: 全ての内部ノードがちょうど2つの子を持ち、かつ全ての葉が同一の深さにある木（完璧に満たされた形）。ノード数は高さ h に対して 2^(h+1) - 1 の形を取る。
- 二分探索木（Binary Search Tree: BST）: 左部分木のキーはノードのキーより小さく、右部分木のキーは大きいという順序性を持つ二分木。検索・挿入・削除が木構造に基づいて行える。
- 平衡二分探索木（balanced BST）: AVL木や赤黒木のように、木の高さが O(log n) に保たれるように自己調整するBST群。
数学的性質と関係式
- 完璧な二分木（高さ h）のノード数: 2^(h+1) - 1。
- 任意の二分木で、葉の個数 L と内部ノードの個数 I が満たす関係（各内部ノードがちょうど2つの子を持つとき）: L = I + 1。
- 配列表現（0始まり）の添字関係: 親(i) = floor((i-1)/2)、左子 = 2i+1、右子 = 2i+2。1始まりの場合は parent = floor(i/2)、左子 = 2i、右子 = 2i+1。
表現方法 — ポインタ（参照）方式と配列方式
二分木は主に次の2つの方法で表現されます。
- ポインタ（参照）方式: 各ノードは左子ポインタ・右子ポインタ（および必要なら親ポインタ）を持つ。柔軟性に優れ、疎な木や動的な挿入削除に向く。ただしポインタ領域のオーバーヘッドがある。
- 配列方式: 完備二分木やヒープで用いられる。連続メモリ（配列）に要素を格納し、添字計算で親子を求めるためポインタ不要で高速（キャッシュに有利）。ただし欠損が多い疎な木に対しては無駄が生じる。
走査（トラバース）とその用途
代表的な走査方法と用途は次の通りです。
- 前順（preorder）: 根→左→右 — 木の構造を保存したままシリアライズする際や、式木で前置記法が欲しい時に利用。
- 中順（inorder）: 左→根→右 — 二分探索木で中順走査を行うと、キーが昇順に並ぶ。BSTの出力に必須。
- 後順（postorder）: 左→右→根 — ノードの削除処理（子を先に処理してから親を処理）や式の後置記法生成に適する。
- レベル順（level-order / BFS） — キューを使った幅優先探索。最短経路や完全性の判定、ヒープの構築確認などに用いられる。
実装面では再帰実装が簡潔ですが、深い（偏った）木ではスタックオーバーフローのリスクがあり、反復処理（明示的なスタック）やMorris走査（親ポインタ不要でO(1)追加メモリ）を検討します。
二分探索木（BST）と平衡化手法
BSTは平均的な検索が O(log n) を期待できる一方、最悪（挿入順が偏るなど）では O(n) になります。これを防ぐためにAVL木、赤黒木、Splay木、Treap などの平衡化手法が使われます。
- AVL木: 各ノードで左右部分木の高さ差が最大1になるよう回転で保つ。検索は非常に高速（平均・最悪とも O(log n)）。実装は回転と高さ管理が必要。
- 赤黒木: 色付け（赤/黒）規則で木の「擬似的な平衡」を保つ。挿入/削除での再調整が少ないため実務で広く使われる（例えばJavaのTreeMapやC++のstd::mapの内部実装は赤黒木が多い）。
- 自己調整木（splay tree）: 最近アクセスされた要素を根に持ってくることで局所性に強い。均衡は厳密ではないが漸近的な性能を保証。
代表的な応用分野
- ヒープ（優先度付きキュー）: 完備二分木を配列で表現する二分ヒープは、insertやextract-min/maxが O(log n) で動作。優先度スケジューリングやDijkstraなどで必須。
- 二分探索木（BST）: 辞書型データ構造（集合・マップ）の実装。
- 式木（演算子とオペランド）: コンパイラや電卓における式の解析・評価。
- ハフマン木: 可変長符号化（圧縮アルゴリズム）での最適二分木構築。
- 決定木（Decision tree）: 機械学習のモデル（分類木）。厳密には二分に限らないが、二分分割で構築するケースが多い。
- セグメントツリー / 区間木: 区間クエリに使われる木構造。実装は二分分割に基づく。
代表的な操作の時間計算量（目安）
- 探索（BST）: 平均 O(log n)、最悪 O(n)（平衡なら O(log n））
- 挿入／削除（BST）: 同上（平衡木では O(log n））
- ヒープの挿入・削除: O(log n)、ヒープ構築（配列から）: O(n)
- 走査（全ノード訪問）: O(n)
実装上の注意点と最適化
- 再帰深度: 偏った木では再帰呼び出しが深くなり、言語によってはスタックオーバーフローする。反復実装や尾再帰最適化（言語がサポートする場合）を検討。
- メモリ配置: ポインタ方式は断片化やキャッシュミスの原因になり得る。頻繁にアクセスする場合は配列やメモリプールでノードを連続的に割り当てると高速化できる。
- 平衡化コストと用途: 読み取りが圧倒的に多いなら事前にソートして完全なBSTを一度作る方が効率的。挿入削除が多いアプリでは自己平衡木を使う。
- 並列化: 木構造は局所的なデータ依存が強いため並列化が難しい。ロック粒度の設計やコピーオンライト戦略、ロックフリー技法の検討が必要。
- シリアライズ: 木を保存/送信する場合、中順だけでは構造を一意に復元できない（BSTなら追加情報が必要）。preorderとnullマーカーやレベル順＋nullでの表現が一般的。
応用例の具体例（短いケーススタディ）
- 優先度付きジョブスケジューラ: 二分ヒープを使えば O(log n) で次のジョブを取得・挿入できる。メモリは配列で連続保持するのが一般的。
- 式の評価: 中置式を逆ポーランド記法（postfix）に変換して評価する際、式木を用いれば演算子の優先順位や括弧処理が自然に表現される。
- 圧縮（ハフマン符号）: 文字の出現頻度から最小重み二分木を構築し、各文字に可変長のビット列を割当てる。
まとめ
二分木は単純な構造ながら、アルゴリズムとデータ構造の基礎として非常に多様な用途を持ちます。設計では「どの種類の二分木が適切か」「配列表現かポインタ表現か」「平衡化の有無」「再帰による実装の安全性」といったトレードオフを考えることが重要です。実際のシステム設計ではアクセス頻度や挿入削除の割合、メモリ・キャッシュ特性を踏まえて最適な実装を選びましょう。
