Java | 「赤黒木」と「AVL木」をもっと深く理解する

Javaで考える「赤黒木」と「AVL木」をもっと深く理解する（前半）

赤黒木（Red-Black Tree）や AVL 木は、 「常にバランスを保つ二分探索木」というカテゴリの代表選手です。 これらを理解できると、 ソート済みデータ構造・辞書・セット・マップの内部構造が見えるようになり、 Java の TreeMap や TreeSet が「ただの黒箱」ではなくなります。

前半では、まず なぜ「バランスする二分探索木」が必要なのか 通常の二分探索木が抱える問題 その問題を解決するための発想としての「AVL木」と「赤黒木」 を、初心者向けにかみ砕いて整理します。 後半では、回転（rotation）や具体的な挿入・削除の流れまで踏み込んでいきます。

二分探索木の基本と「バランスが崩れる」という問題

まず、土台となる「二分探索木（Binary Search Tree）」を整理します。 二分探索木は、次のような性質を持つ木構造です。

左部分木のすべての値 < 自分の値 右部分木のすべての値 > 自分の値

この性質のおかげで、 探索・挿入・削除を「左か右か」を選びながら進めることができ、 理想的には O(log N) で操作できます。

Java での基本的な二分探索木のノードは、次のような形になります。

class Node {
    int key;
    Node left;
    Node right;

    Node(int key) {
        this.key = key;
    }
}

class Node {
    int key;
    Node left;
    Node right;

    Node(int key) {
        this.key = key;
    }
}

例えば、次のように挿入していきます。

public Node insert(Node root, int key) {
    if (root == null) {
        return new Node(key);
    }
    if (key < root.key) {
        root.left = insert(root.left, key);
    } else if (key > root.key) {
        root.right = insert(root.right, key);
    }
    return root;
}

public Node insert(Node root, int key) {
    if (root == null) {
        return new Node(key);
    }
    if (key < root.key) {
        root.left = insert(root.left, key);
    } else if (key > root.key) {
        root.right = insert(root.right, key);
    }
    return root;
}

この形は非常にシンプルで分かりやすいのですが、 一つ大きな問題を抱えています。

それは、「挿入する値の順番によって、木の形が極端に偏る」という問題です。

極端に偏った二分探索木が「ほぼリンクリスト」になる

例えば、次のような順番で値を挿入してみます。

1, 2, 3, 4, 5, 6, 7

この順番で先ほどの insert を使うと、 木は次のような形になります。

1 └ 2 └ 3 └ 4 └ 5 └ 6 └ 7

つまり、「右にだけ伸びた一本鎖」のような形になります。 このとき、探索の計算量は O(N) になってしまい、 二分探索木の「速さのメリット」がほぼ失われます。

二分探索木は「バランスが取れていれば速い」が、 「バランスが崩れると遅くなる」という性質を持っています。

ここでいうバランスとは、 「どのノードを根にしても、左部分木と右部分木の高さが極端に違わない」 というイメージです。

この問題を解決するために登場するのが、 AVL 木や赤黒木といった「自己平衡二分探索木」です。

自己平衡二分探索木という発想

自己平衡二分探索木（Self-Balancing BST）は、 「挿入や削除のたびに、木のバランスを保つように自動調整する」 という発想に基づいたデータ構造です。

ポイントは、 「バランスを保つためのルール」と 「そのルールを維持するための操作（回転）」 を定義していることです。

AVL 木と赤黒木は、 どちらも「バランスを保つ二分探索木」ですが、 バランスの定義と調整の仕方が少し違います。

AVL 木は「高さの差」に厳しいルールを持ち、 赤黒木は「色と黒高さ」に基づく、少し緩めのルールを持ちます。

この違いが、 「探索が速いか」「挿入・削除が軽いか」といった特性の差につながります。

AVL木とは何か：「高さの差」を厳しく管理する木

AVL 木は、 「どのノードについても、左部分木と右部分木の高さの差が 1 以内である」 というルールを持つ二分探索木です。

高さとは、「そのノードから一番深い葉までの距離」です。

例えば、あるノード X について、 左部分木の高さが 3、右部分木の高さが 1 だとすると、 高さの差は 2 になり、AVL 木のルールに違反します。

AVL 木では、挿入や削除のたびにこの高さの差をチェックし、 差が 2 以上になった場合には「回転（rotation）」という操作を行って バランスを回復します。

この「高さの差を厳しく管理する」という性質のおかげで、 AVL 木は非常にバランスが良く、 探索の計算量がほぼ常に O(log N) に保たれます。

ただし、バランスを保つための回転が頻繁に発生するため、 挿入・削除のコストはやや重くなります。

赤黒木とは何か：「色」と「黒高さ」でバランスを保つ木

赤黒木は、 各ノードに「赤（Red）」か「黒（Black）」の色を持たせ、 いくつかのルールを守ることでバランスを保つ二分探索木です。

代表的なルールは次のようなものです。

根は必ず黒 赤ノードの子は必ず黒（赤が連続しない） 任意のノードから葉（NILノード）までの「黒ノードの数」が同じ

この「黒ノードの数」が同じという性質を「黒高さ（black height）」と呼びます。

赤黒木は、 この色と黒高さのルールを守ることで、 木の高さが O(log N) に収まるようにバランスを保ちます。

AVL 木ほど「高さの差」に厳しくないため、 木の形は多少アンバランスになることがありますが、 その分、挿入・削除の回転回数が少なく済み、 更新操作に強いという特徴があります。

Java の TreeMap や TreeSet は、 内部で赤黒木を使って実装されています。 つまり、皆さんが日常的に使っている標準ライブラリの中で、 赤黒木はすでに活躍しているのです。

「バランスする二分探索木」を直感的にイメージする

ここまでの話を、直感的なイメージでまとめてみます。

通常の二分探索木は、 「とりあえず左か右かに挿していく」だけなので、 挿入順によっては「片側に伸びた一本鎖」になってしまいます。

AVL 木は、 「どのノードでも左右の高さの差が 1 以内」という かなり厳しいルールを守ることで、 木全体をきれいにバランスさせます。

赤黒木は、 「色と黒高さ」という少し緩めのルールを使って、 木の高さを O(log N) に保ちつつ、 挿入・削除のコストを抑えます。

どちらも、「バランスを保つためのルール」と「回転」という操作を持ち、 その結果として「速い探索」を保証している、 という点では共通しています。

この「バランスする二分探索木」という発想を理解できると、 データ構造の設計を一段深いレベルで考えられるようになります。

前半のまとめと後半への橋渡し

前半では、赤黒木やAVL木を深く理解するための土台として

二分探索木の基本構造と「バランスが崩れると遅くなる」という問題 極端に偏った二分探索木が「ほぼリンクリスト」になること 自己平衡二分探索木という発想 AVL 木が「高さの差」を厳しく管理してバランスを保つ木であること 赤黒木が「色」と「黒高さ」のルールでバランスを保つ木であること Java の TreeMap / TreeSet が赤黒木を内部で使っていること

を整理しました。

後半では、ここから一歩進んで

AVL 木の具体的な回転（単回転・二重回転）の流れ 赤黒木の挿入・削除時の色反転と回転のパターン Java 風の簡易実装イメージ AVL と赤黒木の性能・用途の違い セキュリティ・パフォーマンスの観点から見た「自己平衡木」の注意点

を、より具体的なコード断片とともに深掘りしていきます。