二分木とは？基礎・走査・BST・平衡木を初心者向けに徹底解説
エバープレイ編集部はじめに — 二分木とは何か
二分木（にぶんぎ、binary tree）は、各ノードが高々2つの子ノード（左子と右子）を持つ木構造の一種です。コンピュータサイエンスにおける基本的なデータ構造であり、検索、整列、式の表現、ヒープや探索木など多くのアルゴリズムや応用の基盤となります。
基本的な用語と性質
- ノード（node）：データと子ノードへの参照（ポインタ）を持つ単位。
- 根（root）：木の最上位のノード。親を持たない。
- 葉（leaf）：子が存在しないノード。
- 高さ（height）：根から最も深い葉までのエッジ数（あるいはノード数で定義することもある）。定義の差に注意。
- 深さ（depth / level）：あるノードが根から何番目の位置にあるか（根の深さは0または1の慣習がある）。
- 部分木（subtree）：あるノードを根とする木全体。
二分木の主な種類
- 完全二分木（complete binary tree）：全レベルが完全に埋まっているか、最下層のみ右側ではなく左側から順に埋まっている木。配列表現に向く。
- 満二分木（perfect binary tree）：全ての内部ノードがちょうど2つの子を持ち、全ての葉が同じ深さにある木（完全かつ均一）。
- 完全二分木と満二分木の違い：満二分木は各レベルが完全に埋まる（葉が同深度）ことを要求するのに対し、完全二分木は最下層のみ左詰めでよい。
- 完全ではないが二分木：各ノードの子が0〜2個である一般的な二分木。偏ったものは連結リストに等しい場合もあり得る（退化木）。
- 二分探索木（BST: Binary Search Tree）：任意のノードについて、左部分木の全てのキーはそのノードより小さく、右部分木の全てのキーは大きい（重複の扱いは実装により異なる）。これにより探索や順序走査が効率的になる。
- 平衡二分木（balanced BST）：部分木の高さ差を制約することで高さをO(log n)に保つ木（例：AVL木、赤黒木など）。
- 二分ヒープ（binary heap）：完全二分木の形を取り、親と子の間にヒープ条件（親が子より大きい／小さい）を満たす構造。優先度付きキューに利用。
表現方法（メモリ上の表現）
- ポインタ（参照）ベース：各ノードが左子・右子（および必要に応じて親）へのポインタを持つ。任意の形の二分木に適する。
- 配列ベース：主に完全二分木に適用。0始まりインデックスの場合、ノードiの左子は2i+1、右子は2i+2（1始まりなら左子2i、右子2i+1）。メモリ局所性が良いが、欠損がある不完全木では無駄が出る。
- その他：スレッド化二分木（threaded tree）は空の子ポインタを利用してin-order走査を容易にする。またシリアライズ（保存・復元）ではPreorder＋nullマーカーやレベル順（BFS）を用いる。
トラバーサル（走査）— 基本と特徴
二分木でよく使われる走査法とその用途：
- 前順（Pre-order: 根→左→右）：木の構造を記録（シリアライズ）するのに便利。根を先に処理する。
- 中順（In-order: 左→根→右）：二分探索木では昇順ソートされた順序で要素が得られるため、ソート済の列挙に使う。
- 後順（Post-order: 左→右→根）：子を先に処理するため、ノード削除や式木（演算子が根、オペランドが葉）の評価に適する。
- レベル順（Level-order / BFS）：キューを使って幅優先で訪問。最短経路や完全性チェック、ヒープの操作に関係する。
走査は再帰的に実装するのが直感的だが、スタックを使う反復実装、あるいはMorris走査のような追加空間O(1)での方法も存在します（Morrisは一時的に右ポインタを繋ぎ替えてin-orderを実現）。
主要な操作とアルゴリズム
- 探索（search）：一般木ではO(n)。二分探索木では平均O(h)（通常はO(log n)）、最悪O(n)。
- 挿入（insert）：BSTでは葉に挿入して構造を保つ。平衡木では挿入後に高さ制約を満たすための回転などが必要。
- 削除（delete）：BSTの削除は場合分けが必要（葉の削除、片側のみ子を持つ場合、両側に子を持つ場合）。両側存在時は通常、インオーダーの次ノード（後継）または前任者（前任）と交換して削除する。
- 走査の時間計算量：全ノードを訪問する走査はO(n)。
- シリアライズ/デシリアライズ：Preorderにnullマーカー（またはBFSでレベルごとにnullを入れる）を含めて保存すれば、木構造を一意に復元できる。
平衡二分木：AVL木と赤黒木（概要）
平衡を保つ目的は操作（探索・挿入・削除）を効率的にO(log n)にすることです。主な実装例：
- AVL木：各ノードについて左右部分木の高さ差が-1〜1の範囲に保たれる。挿入・削除で不均衡が生じたら単回転または二重回転で修正。高いバランス性を持つが回転が頻繁でやや複雑。
- 赤黒木（Red-Black Tree）：各辺に色（赤/黒）を付け、幾つかの整合条件（根は黒、赤ノードの子は黒、任意のノードから葉への黒ノード数が同じなど）を満たすことで高さを制限する。挿入・削除は色の再分配と回転で対応。実装はやや複雑だが挿入・削除の平均的操作回数は少なく、ライブラリ（JavaのTreeMapやC++のset/mapなど）で広く使われる。
応用例
- 式木（Expression Trees）：コンパイラや電卓で二項演算子を内部ノード、数値を葉に持つことで式を表現・評価する。
- 二分ヒープ（優先度付きキュー）：完全二分木を用いて最大値/最小値を高速に取り出す。
- 二分探索木：データベースやインデックス、集合・辞書の実装。
- Huffman木：可変長符号化のための二分木（葉が記号、深さが符号長）。
- 決定木（Decision Tree）：機械学習で特徴に基づく分岐を二分木で表現する場合が多い（必ずしも完全に二分とは限らない）。
実装上の注意点と落とし穴
- 再帰の深さ：退化した二分木では再帰深度がO(n)になりスタックオーバーフローの危険がある。反復的実装や明示的スタックの使用、あるいは再帰最適化が必要になる場合がある。
- 重複キーの扱い：BSTにおける重複キーは実装で方針を決めておく（左側へ入れる、右側へ入れる、同値はリストで管理する等）。
- 高さの定義：高さをエッジ数で数えるかノード数で数えるかでアルゴリズムの記述が変わることがある。ドキュメントで明示すること。
- メモリ管理：言語によってはノードの動的確保・解放を適切に行う必要がある。ガーベジコレクションの有無で設計が変わる。
面接でよく出るトピック（短く）
- 二分探索木での挿入・削除の実装例およびそのケース分け
- トラバーサルの再帰・反復実装（スタック・キュー）
- 平衡化のための回転（単回転・二重回転）ロジック
- 二分ヒープの配列表現とヒープ操作（heapify, sift-up, sift-down）
- ツリーの幅（最大ノード数）や深さを求めるアルゴリズムの複雑度
まとめ
二分木は「各ノードが最大2つの子を持つ」という単純な定義にも関わらず、表現方法・走査法・平衡化戦略など多様な設計選択を持つ非常に重要なデータ構造です。用途に応じてBST、ヒープ、平衡木などを選び、実装時には高さ・重複・メモリ管理・再帰深度などの点に注意することが求められます。面接や実務で問われることが多い基礎分野なので、トラバーサルや挿入／削除の各ケースを手で追って理解しておくとよいでしょう。
