メインコンテンツまでスキップ

データ構造：二分木

· 約9分
tanzhuo

連結リストと配列が解決するのは「線形」データの格納問題ですが、階層関係や高速な検索が絡んでくると、線形構造では力不足になります。木構造はまさにそのために生まれたもので、二分木はその中で最も基礎的であり、最もよく問われるものでもあります。ヒープ、BST、赤黒木はすべて二分木の上に成り立っています。

二分木（Binary Tree） はよく使われるデータ構造で、複数のノードから構成され、各ノードは最大でも 2 つの子ノード しか持ちません：

  • 左の子ノード（Left Child）
  • 右の子ノード（Right Child）

そのため 二分木 と呼ばれます。

「最大 2 つ」という制約は一見単純ですが、重要な性質をもたらします。木の形態を再帰的に定義できるのです。すべての二分木は、根ノード、左部分木、右部分木の 3 つの部分から構成され、左右の部分木自身もまた二分木です。この後に出てくる二分木に関するほぼすべてのアルゴリズム（走査、検索、挿入）は、この再帰構造を軸に展開されます。

各ノードは通常 3 つの部分を含みます：

Node {
    value   // ノードが格納するデータ
    left    // 左の子ノードへの参照。なければ空
    right   // 右の子ノードへの参照。なければ空
}

つまり、二分木はメモリ上で連続して格納される必要はなく、ノード同士は参照（ポインタ）で繋がっています。この点は連結リストと似ていますが、各ノードが「1 つの後続」から「最大 2 つの子」に変わっただけです。

シンプルな構造の例：

        A
       / \
      B   C
     / \   \
    D   E   F

このうち：

  • A は 根ノード（Root）
  • B、C は A の 子ノード
  • D、E は B の 子ノード

子ノードを持たないノード（D、E、F など）は 葉ノード（Leaf） と呼ばれます。根から葉までに通る層の数を木の 高さ と呼び、これが木に対するほとんどの操作の所要時間を直接決定します。

形態の違いによって、二分木にはいくつかのよくある特殊なカテゴリがあります。順番に見ていきましょう。

全二分木（Full Binary Tree）​

ある木の すべてのノードが、2 つの子ノードを持つか、子ノードをまったく持たないか のいずれかである場合、全二分木と呼びます。

        A
       / \
      B   C
     / \ / \
    D  E F  G

特徴：

  • 各ノードは 子ノード 0 個 か
  • 子ノード 2 個 のいずれか

言い換えれば、全二分木には「子が 1 つだけ」のノードは存在しません。この形態は最も「詰まって」おり、同じ層数の場合に格納できるノード数が最大になります。

完全二分木（Complete Binary Tree）​

完全二分木の要件は：

  • 最後の層を除き、他の層はすべて埋まっている
  • 最後の層のノードは 左から右へ連続して並んでいる

例：

        1
       / \
      2   3
     / \  /
    4  5 6

この構造は 配列での格納 に非常に適しているため、ヒープ（Heap） は完全二分木なのです。

なぜ完全二分木は配列格納に向いているのでしょうか。ノードに「上から下へ、左から右へ」番号を振ると、途中に穴が空かないからです。根を添字 0 に置くと、添字 i のノードの左の子は 2i + 1、右の子は 2i + 2、親ノードは (i - 1) / 2（切り捨て）になります。ポインタを一切格納せず、添字の計算だけで親子間を行き来できるので、メモリを節約できるうえキャッシュにも優しい。ヒープソートと優先度付きキューはまさにこの性質を利用しています。

二分探索木（BST）​

前の 2 つの分類が注目するのは「形」ですが、二分探索木が注目するのは「ノードの値の並び方の規則」です。二分探索木（Binary Search Tree）は次を満たします：

左子树 < 根节点 < 右子树

この制約は再帰的に効くことに注意してください。左右の子だけでなく、左部分木全体のすべての値が根より小さく、右部分木全体のすべての値が根より大きいのです。

例：

        8
       / \
      3   10
     / \    \
    1   6    14

特徴：

  • 検索効率が高い
  • 平均時間計算量：O(log n)

検索の過程は二分探索とそっくりです。根から始めて、目標値が現在のノードより小さければ左へ、大きければ右へ進む。1 層進むごとに、候補ノードのおよそ半分を除外できます。挿入も同様で、検索の経路に沿って空きの位置まで進み、新しいノードをそこにぶら下げるだけです。

しかし木が連結リストに退化すると：

1
 \
  2
   \
    3

時間計算量は次のように退化します：

O(n)

退化の最も典型的な引き金は、ソート済みの列 を順に挿入することです。新しいノードがどれも以前のものより大きいと、ひたすら右側にぶら下がるしかなく、木は一本の鎖のように「歪んで」成長します。検索時に各層で 1 ノードしか除外できず、BST の利点は完全に失われます。この問題を解決するために、AVL 木や赤黒木といった 自己平衡二分探索木 が生まれました。これらは挿入・削除時に回転によって構造を調整し、木の高さを常に O(log n) レベルに保ちます。

走査方式​

二分木のすべてのノードを訪問する方法を走査と呼び、よく使われるのは 4 種類です：

  1. 前順走査（先行順）：根 → 左部分木 → 右部分木。木のコピーやシリアライズによく使われる
  2. 中順走査（通りがけ順）：左部分木 → 根 → 右部分木。BST に対して中順走査を行うと、得られるのはまさに 昇順の列
  3. 後順走査（帰りがけ順）：左部分木 → 右部分木 → 根。「先に子を処理してから自分を処理する」場面、例えば木全体の解放に適している
  4. レベル順走査：層ごとに左から右へ訪問する。キューを使って実装する、木の上での幅優先探索

前の 3 つは再帰で書くと非常に自然です。これは前述の内容の裏付けでもあります。二分木自体が再帰的に定義された構造なのです。

ハマりどころと注意点​

上記の内容を踏まえて、実際の使用や問題演習でつまずきやすいポイントがいくつかあります：

  • BST が平衡だとデフォルトで思い込まない。計算量を分析するときは「平均 O(log n)」と「最悪 O(n)」を区別すること。面接で突っ込まれるのはたいてい退化の場面です。
  • 中順走査で BST を検証する。ある木が正しい BST かどうかの判定は、ノードとその直接の子を比較するだけでは不十分で、部分木全体が大小関係を満たすことを保証しなければなりません。中順走査で列が厳密に単調増加かをチェックするのが最も間違いにくい書き方です。
  • 再帰の深さ。木が連結リストに退化すると、再帰走査のコールスタックの深さも O(n) になります。データ量が大きいとスタックオーバーフローの可能性があるので、必要なら明示的なスタックを使う反復の書き方に切り替えましょう。
  • 「全」と「完全」を区別する。この 2 つの定義は混同しやすいものです。全二分木は子が 1 つだけのノードを許さず、完全二分木は最後の層が左詰めであることを要求します。正誤問題ではこの 2 つの概念でお互いに引っかけてくることがよくあります。

まとめ​

二分木は最も基礎的かつ最も重要なデータ構造の一つで、その核心的な特徴は

  • 各ノードは最大 2 つの子ノード
  • 効率的な検索 をサポート
  • さまざまな高度なデータ構造へ拡張できる

よくある派生には次のものがあります：

  • 二分探索木（BST）
  • AVL 木
  • 赤黒木
  • ヒープ（Heap）

二分木の理解は アルゴリズムとデータ構造 を学ぶうえでの重要な基礎です。その再帰的な定義、いくつかの形態の違い、そして走査の定石を押さえてから平衡木やヒープを見れば、それらの「高度な」構造が、二分木に追加の制約を重ねただけのものに過ぎないと気づくはずです。

COMMENTS