バイナリツリー（二分木）入門：用語・走査からBST・ヒープ・AVL／赤黒木の実装と性能比較

2025年11月18日 最終更新日時 : 2025年11月18日 エバープレイ編集部

バイナリツリーとは — 基本定義と用語

バイナリツリー（binary tree、二分木）は、各ノードが最大で2つの子ノード（左子・右子）を持つ木構造です。コンピュータサイエンスやアルゴリズムの基礎データ構造の一つで、探索、ソート、表現（式木）やヒープなど多数の応用があります。

主な用語：

  • 根（root）：ツリーの最上位ノード。
  • 親（parent）／子（child）：直接つながる上位／下位ノード。
  • 葉（leaf、terminal node）：子を持たないノード。
  • 内部ノード（internal node）：少なくとも1つの子を持つノード。
  • 深さ（depth）／高さ（height）：根からの距離／ノードから最も遠い葉までの距離。
  • 部分木（subtree）：あるノードとそのすべての子孫ノードからなる木。

バリエーションと性質

「バイナリツリー」という一般概念の下に、用途や構造に応じた派生が多数あります。代表的なもの：

  • 完全二分木（complete binary tree）：最下層を除いてすべてのレベルが埋まり、最下層は左詰めで構成される。
  • 完全（perfect）二分木：すべての内部ノードが2つの子を持ち、すべての葉が同じ深さにある。
  • 全二分木／満二分木（full/strict binary tree）：各ノードが0か2つの子を持つ。
  • 偏った二分木（skewed tree）：すべてのノードが一方向（左か右）にだけ子を持つ。最悪ケースで線形リストと等価になる。
  • バランス木（balanced tree）：高さが O(log n) に制約されるよう設計された木（例：AVL木、赤黒木）。

表現方法：ポインタ（リンク）型と配列（インデックス）型

バイナリツリーは主に2つの表現で実装されます。

  • リンク（ノード構造）型：各ノードがデータと左子ポインタ・右子ポインタを持つ。動的で任意の形状の木に適する。
  • 配列（ヒープ風）型：完全二分木に有効。0始まりインデックスで i の左子は 2*i+1、右子は 2*i+2、親は floor((i-1)/2)。1始まりなら左 2*i、右 2*i+1、親 floor(i/2)。配列はメモリの連続性でキャッシュに有利。

基本操作とアルゴリズム

代表的なアルゴリズムとその計算量（n はノード数、h は木の高さ）：

  • 走査（Traversal）：
    • 前順（pre-order：根→左→右）、中順（in-order：左→根→右）、後順（post-order：左→右→根） — 再帰/スタックで実装。時間 O(n)、追加空間は再帰深度 O(h)（スタック使用時も同様）。
    • レベル順（level-order、幅優先） — キューを使う。時間 O(n)、空間 O(width)（最悪 O(n)）。
    • Morris traversal（中順の O(1) 空間アルゴリズム）：親ポインタを一時的につなぎ替えることで追加メモリ O(1) を実現。ただし木を一時的に改変する。
  • 探索（一般バイナリツリーは特別な順序なし）：全ノード走査が必要 → O(n)。
  • 二分探索木（BST）の探索・挿入・削除：平均 O(h)（ランダム挿入なら期待 O(log n)）、最悪 O(n)（偏る場合）。
  • ヒープ操作（完全二分木で配列表現）：
    • 挿入（up-heap／sift-up）：O(log n)
    • 削除（pop root, down-heap／sift-down）：O(log n)
    • 構築（heapify、配列からの構築）：O(n)

二分探索木（Binary Search Tree: BST）

BST は「左部分木のキー < ノードキー < 右部分木のキー」という性質を満たす二分木です。この性質により効率的な探索が可能になります。典型的な操作：

  • 検索：根から比較して左/右に進む。平均 O(log n)、最悪 O(n)。
  • 挿入：葉に追加。BST 性を保つ。平均 O(log n)。
  • 削除：ノード削除は 3 ケース（葉、片方の子のみ、両方の子あり）。両方の子がある場合は後続ノード（in-order successor）か先行ノードで置換して削除。

BST の性能は高さ h に依存するため、バランスを保つアルゴリズム（AVL, 赤黒木 等）が重要です。

自己平衡（二分）木：AVL 木と赤黒木

BST の最悪ケース（O(n)）を避けるため、木の高さを O(log n) に抑える自己平衡木が使われます。

  • AVL 木：
    • 各ノードに「高さ」情報を持ち、左右部分木の高さ差（バランス因子）が -1, 0, 1 の範囲となるように回転で保つ。
    • 挿入・削除ごとに最大 O(log n) 回の回転で調整。探索は O(log n)。
    • 検索が頻繁、挿入/削除も許容範囲という用途に適合。
  • 赤黒木：
    • 各ノードに色（赤/黒）を付与し、木の特定の性質（根は黒、赤のノードは黒い子のみ、任意の葉までの黒の数は同じ…など）を保つことで高さを制限する。
    • AVLよりは挿入/削除の回転が少なく、実装上トレードオフがある。多くの標準ライブラリ（例：C++ の map/set、Java の TreeMap）では赤黒木が利用されることが多い。

ヒープ（Heap）と完全二分木の応用

ヒープは「部分木の根が子よりも大きい（max-heap）／小さい（min-heap）」という性質を持つ完全二分木です。配列表現が一般的で、優先度キュー（priority queue）やヒープソートで使われます。ヒープは BST とは異なり鍵の順序での探索効率は保証しませんが、最大（最小）要素の取得／削除を O(log n) で行えます。

式木（Expression Tree）とその他の応用

演算式を木で表す式木はコンパイラやインタプリタで用いられます。内部ノードは演算子、葉はオペランド（数値や変数）で表され、走査順序によって中置・前置・後置記法に対応します。

その他の応用例：

  • 区間木（Segment Tree）や完全二分木をベースにしたセグメント構造（区間クエリを高速化）
  • 決定木（Decision Tree）や探索木（ゲーム木）
  • ハフマン木（Huffman Tree；可変長符号の圧縮）

実装上の注意点とパフォーマンス実務的ヒント

  • 再帰の深さ：偏った木では再帰が深くなりスタックオーバーフローの原因に。大規模データには反復的実装か自己平衡木を検討する。
  • メモリ局所性：配列表現は連続メモリによりキャッシュフレンドリー。完全二分木やヒープに適している。
  • デバッグと可視化：中順走査で要素が昇順出力されるか（BST）をチェックすると整合性確認が容易。
  • 並列化：レベル毎の処理は幅優先走査で並列化しやすいが、依存関係のある更新は注意が必要。

典型的な擬似コード（概念説明用）

中順走査（再帰）の簡易擬似コード：

function inorder(node):
  if node == null: return
  inorder(node.left)
  visit(node)
  inorder(node.right)

BST の検索：

function bst_search(node, key):
  while node != null:
    if key == node.key: return node
    if key < node.key: node = node.left
    else: node = node.right
  return null

まとめ

バイナリツリーは幅広いアルゴリズムとデータ構造の基礎で、用途に応じた派生（BST、ヒープ、AVL、赤黒木、式木、区間木など）を選ぶことが重要です。性能は「木の高さ」に依存するため、バランスを保つ設計や表現方法（配列 vs リンク）を使い分けることで実務での効率化が図れます。各アルゴリズムの時間・空間特性を理解し、データ特性や操作頻度に応じて選定してください。

参考文献

カテゴリー
IT
前の記事
ロイ・ウッド（Roy Wood）とは？The Move・ELO・Wizzardを貫く音楽性と代表曲・名盤『Boulders』完全ガイドNew!!
2025年11月18日
次の記事
Roy Wood入門：必聴アルバム6選と聴きどころ・コレクターガイドNew!!
2025年11月18日