二分木とは：定義・種類（BST／ヒープ／AVL）・実装と巡回の基礎を徹底解説
エバープレイ編集部はじめに — 「二進木」と「二分木」について
まず用語の確認ですが、一般にコンピュータサイエンスで使われる「binary tree」は日本語で「二分木（にぶんぎ）」と表記します。質問にある「二進木（にしんぎ）」という表現はあまり一般的ではありません。この記事では以降「二分木」を正式な呼称として解説します。
二分木の基本定義
二分木とは、各ノードが最大2つの子ノード（左子・右子）を持つ木構造です。主要な用語は次の通りです。
- 根（root）：木の最上位のノード。
- 葉（leaf）：子を持たないノード。
- 内部ノード（internal node）：子を1つ以上持つノード。
- 高さ（height）：根から最も深い葉までの辺の最大数（またはノード数ベースの定義もある）。
- 深さ（depth）：根からそのノードまでの辺の数。
- 部分木（subtree）：あるノードを根とする下位の木。
二分木は抽象データ型として非常に汎用性が高く、検索、並べ替え、表現、ヒープ構造など多くのアルゴリズム・データ構造の基礎になります。
二分木の主な分類
用語は混乱しやすいため、定義を明確に示します（英語名称を併記）。
- Full / Strict binary tree（フル二分木）：各ノードがちょうど0または2個の子を持つ。
- Perfect binary tree（完備（全）二分木）：すべての内部ノードが2子を持ち、すべての葉が同じ深さにある。ノード数は2^(h+1)-1。
- Complete binary tree（完全二分木）：最下層を除きすべてのレベルが満たされ、最下層のノードは左詰めで配置される（配列実装に適する）。
- Balanced binary tree（平衡二分木）：木の高さが O(log n) に抑えられているものの総称（AVL木・赤黒木など具体的アルゴリズムあり）。
探索木（Binary Search Tree; BST）
二分探索木（BST）は各ノードにキーがあり、任意のノードについて左部分木のキーはそのノードのキー未満、右部分木はそのノードのキー以上（あるいは単純に大きい）という不変条件（BSTプロパティ）を満たします。この性質により、探索・挿入・削除が木の高さに比例する時間で行えます。
- 平均・期待計算量（ランダムな挿入順の場合）: 探索・挿入・削除は O(log n)。
- 最悪計算量（退化した場合、リスト状になった場合）: O(n)。
- 中間順巡回（in-order traversal）を行うと、キーが昇順に得られるためソートと密接に関係する。
主要操作とアルゴリズム
代表的な操作の概要と計算量（nはノード数、hは高さ）を示します。
- 探索（search）：BSTでは平均 O(h)（通常は O(log n)）、最悪 O(n)。
- 挿入（insert）：BSTでは探索に続けて新ノードを葉として挿入。平均 O(h)。
- 削除（delete）：削除対象に応じて（葉、子が1つ、子が2つ）処理が分かれる。子が2つの場合は小さいほうの右部分木の最小ノード（後続 successor）で置き換える等の手順が必要。
- 巡回（traversal）：preorder、inorder、postorder（深さ優先）とlevel-order（幅優先）。再帰またはスタック／キューで実装。
トラバーサル（巡回）の詳細
典型的な巡回方法と用途：
- 前順（preorder）: 根→左→右。木の構造を先に処理する。ツリーのコピーや直列化（シリアライズ）に便利。
- 中順（inorder）: 左→根→右。BSTではキーが昇順に出力される。
- 後順（postorder）: 左→右→根。木の削除や子の処理を先にしたい場合に有効。
- 幅優先（level-order）: 各レベルを左から右へ処理。キューを用いる。
再帰実装は簡潔ですが、深い木ではスタックオーバーフローの懸念があります。反復（イテレータ）実装は明示的スタックやMorris巡回（追加メモリ O(1)、一時的にポインタを変更）などの手法があります。
配列とポインタによる実装の違い
二分木は主に2つの方法で表現されます。
- ポインタベース（リンク）: 各ノードが左子・右子へのポインタ（参照）を持つ。動的な挿入・削除に向く。
- 配列ベース（インデックス）: 完全二分木に対して特に有効。1始まりの配列であれば、あるノード i の左子は 2i、右子は 2i+1、親は floor(i/2)。ヒープ（完全二分木）で用いられる。
配列はメモリ局所性が良く、ヒープ実装に最適ですが、任意形状（不完全）な木を配列で扱うと空き領域が増えるという欠点があります。
二分ヒープ（Binary Heap）
ヒープは完全二分木で、各ノードが親とのキー関係（最大ヒープなら親 >= 子、最小ヒープなら親 <= 子）を満たします。配列実装が主流で、優先度付きキューの実現に使われます。
- 挿入: 要素を配列末尾に追加し、親と比較して上方向にスワップ（“sift-up”）してヒープ条件を回復。O(log n)。
- 取り出し（最大/最小の取り出し）: 根を取り出し、配列末尾の要素を根に置き、下へ“sift-down”して回復。O(log n)。
- ヒープ構築（heapify）: 任意配列から O(n) 時間でヒープを作る下向き操作がある（効率的なビルド）。
自己平衡二分探索木
BSTが最悪ケースで線形時間になる問題を解決するために、高さを O(log n) に保つ自己平衡木が使われます。代表例：
- AVL（Adelson-Velsky and Landis）木: 各ノードは左右部分木の高さ差（バランス因子）が -1, 0, 1 に保たれる。検索は高速だが挿入/削除時に回転（ローテーション）が多く生じやすい。
- 赤黒木（Red-Black Tree）: 色（赤/黒）を用いて木の黒高さを制約することで高度を制御。AVLより制約が緩く、挿入/削除の際の回転は平均的に少ない。JavaのTreeMapやC++のstd::mapの多くは赤黒木に基づいている。
- スプレー木（Splay Tree）: 最近アクセスされた要素を根に持ってくる自己調整木。amortized（漸近平均）で O(log n) を実現。
これらはそれぞれ特性（読み取りに強い、書き込みに強い、実装の単純性など）が異なり、用途に応じて使い分けられます。
高度なテクニックと表現法
実用や研究で使われる応用的な技術を紹介します。
- スレッド化二分木（Threaded Binary Tree）: null ポインタを前後の巡回に使う参照に流用して再帰やスタックを使わずに巡回する手法。
- Morris traversal: ポインタを一時的に書き換えることで O(1) 追加メモリで中順巡回を実現するアルゴリズム（ツリーを元に戻す処理を含む）。
- 永続データ構造（Persistent Trees）: 古いバージョンを保持しつつ更新を行う。不変オブジェクト指向や関数型言語で多用される。
- 圧縮・簡潔表現（succinct data structures）: ビット列やランク・セレクトを用いてほとんど最小ビットで木を表現し、高速なランク/選択やナビゲーションをサポートする。
- 外部メモリ向けの木構造: ディスクアクセスを最小化するための B木・B+木 等（これらは二分ではないが「木」の扱いとして重要）。
応用例
二分木は理論から実用まで幅広く使われます。
- 式木（Expression Trees）: 演算子を内部ノード、オペランドを葉にすることで式の評価や中間コード生成に利用。
- 決定木（Decision Trees）: 機械学習では特徴に基づく分岐で予測を行う（必ずしも二分ではないが二分分割のものも多い）。
- ヒープ（優先度付きキュー）、ヒフマン木（可変長符号化）、区間木・セグメント木（区間演算に使う二分木構造の派生）。
- 構文木（AST: Abstract Syntax Tree）: コンパイラでソースコードの構造を表現。
- 探索アルゴリズムやゲーム木、パス探索など幅広いアルゴリズム的応用。
実装上の注意点とベストプラクティス
実際に実装する際の注意点を挙げます。
- 再帰深度: デフォルトのスタックサイズで深い木（線形に近い）を再帰処理するとスタックオーバーフローするので、反復実装や明示的スタック、あるいは木の平衡化を検討する。
- メモリ管理: C/C++ではノード単位の動的確保が多く断片化や割り当てコストが問題になる。プール配分や arena アロケータを使うと効率が向上する。
- 並列処理: 並列挿入・探索は競合制御が必要。ロック分割（lock coupling）、細粒度ロック、あるいはロックフリー構造が研究されている。
- 永続化とシリアライズ: preorder と null マーカーやbreadth-firstの配列化を用いて木を一意に直列化し、復元する。
- テストと検証: 木構造は境界条件（空木、単一ノード、片側に偏った木）、バランス条件の検査などを網羅するテストが重要。
まとめ
二分木（正しくは「二分木」）は、コンピュータサイエンスで最も基本的かつ重要なデータ構造の一つです。単純な形から高度な自己平衡木、ヒープや圧縮表現に至るまで、多様なバリエーションと応用があります。用途に応じて、配列ベースかポインタベースか、平衡性をどの程度保証するか、メモリ効率や並列性の要件は何かを明確にして設計することが重要です。
参考文献
- Wikipedia: 二分木（日本語）
- Wikipedia: Binary tree (English)
- Wikipedia: Binary search tree
- Wikipedia: AVL tree
- Wikipedia: Red–black tree
- Wikipedia: Binary heap
- Wikipedia: Morris traversal
- MIT OpenCourseWare: Introduction to Algorithms（講義資料）
- Stanford/UMass 等の講義ノート（木構造の総論）
投稿者プロフィール
