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

Java SQL
スポンサーリンク

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

前半では、 二分探索木が「バランスを失うと遅くなる」こと その問題を解決するための自己平衡二分探索木という発想 AVL木が「高さの差」を厳しく管理する木であること 赤黒木が「色」と「黒高さ」でバランスを保つ木であること を整理しました。

後半では、そこから一歩進んで、 具体的な回転（rotation）のイメージ、 AVL木のバランス調整の流れ、 赤黒木の色反転と回転のパターン、 Java風の簡易コード断片、 そして性能・用途・セキュリティの観点まで含めて、 「実際に使える理解」に近づけていきます。

回転（rotation）という操作を直感的に理解する

赤黒木やAVL木の心臓部にあるのが「回転（rotation）」です。 回転は、一言で言うと「親子関係を入れ替えて木の形を整える操作」です。

最も基本的なものは「右回転（right rotation）」と「左回転（left rotation）」です。

右回転の直感的なイメージを言葉で描いてみます。

あるノード X があり、その左子が Y だとします。 Y の右部分木が B だとします。

構造はこうです。

Y が左にいて、その右に B、 X がその右にいて、X の右に C がある、 という形をイメージしてください。

右回転では、 Y を新しい親にし、 X を Y の右子にします。 もともと Y の右にあった B は、X の左に移ります。

結果として、 木全体の高さが少し変わり、 バランスが改善されます。

左回転はその逆で、 右子を親に持ち上げ、 元の親を左子にする操作です。

重要なのは、 回転は「二分探索木の順序関係（左 < 自分 < 右）」を壊さないように設計されている、 という点です。 値の並び順はそのままに、形だけを変えることでバランスを整えます。

AVL木のバランス調整を具体的なパターンで見る

AVL木では、「どのノードでも左右の高さの差が 1 以内」というルールを守るために、 挿入や削除の後に「どこかで高さの差が 2 以上になっていないか」をチェックします。

高さの差が 2 以上になった場合、 そのノードを「不均衡ノード」として、 回転を行ってバランスを回復します。

代表的なパターンは次の四つです。

左左（LL） 左右（LR） 右右（RR） 右左（RL）

ここでは、LL と LR を例にしてイメージを深掘りします。

LLパターン（左左）の例

LLパターンは、「左の左側に重みが偏っている」ケースです。

例えば、次のような挿入を考えます。

X に対して、左子 Y があり、 さらに Y の左子 Z に値を挿入した結果、 X の左部分木の高さが右部分木よりも 2 大きくなった、 という状況です。

このとき、 X を根とする部分木は「左に倒れた」形になっています。

LLパターンでは、 X を右回転することでバランスを回復します。

右回転の結果、 Y が新しい親になり、 X は Y の右子になります。 Z はそのまま Y の左子です。

これにより、 左右の高さの差が 1 以内に収まり、 AVL木のルールが回復されます。

LRパターン（左右）の例

LRパターンは、「左の右側に重みが偏っている」ケースです。

X に対して、左子 Y があり、 Y の右子 Z に値を挿入した結果、 X の左部分木の高さが右部分木よりも 2 大きくなった、 という状況です。

このとき、 単純な右回転ではバランスがうまく取れません。

LRパターンでは、 まず Y を左回転して Z を持ち上げ、 その後 X を右回転して Z を根にします。

つまり、「二重回転（double rotation）」が必要になります。

この二重回転により、 Z が新しい親になり、 その左に Y、右に X がぶら下がる形になり、 左右の高さの差が 1 以内に収まります。

このように、AVL木では 「どの方向に重みが偏っているか」を見て、 単回転か二重回転かを選びます。

Java風のAVL木の回転コード断片

実装の全体を書くと長くなりすぎるので、 ここでは回転部分のイメージだけを Java 風に示します。

まず、ノードクラスに高さを持たせます。

class AvlNode {
    int key;
    AvlNode left;
    AvlNode right;
    int height;

    AvlNode(int key) {
        this.key = key;
        this.height = 1;
    }
}
Java

高さの更新と回転の基本形は次のようになります。

int height(AvlNode node) {
    return (node == null) ? 0 : node.height;
}

int getBalance(AvlNode node) {
    if (node == null) return 0;
    return height(node.left) - height(node.right);
}

AvlNode rightRotate(AvlNode y) {
    AvlNode x = y.left;
    AvlNode T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;

    return x;
}

AvlNode leftRotate(AvlNode x) {
    AvlNode y = x.right;
    AvlNode T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;

    return y;
}
Java

挿入処理の最後で、 getBalance(node) を使ってバランスをチェックし、 LL・LR・RR・RL のパターンに応じて leftRotate や rightRotate を呼び分けます。

このように、AVL木は「高さを持つノード」と「回転関数」を組み合わせて、 常にバランスを保つように設計されています。

赤黒木の色反転と回転のパターン

赤黒木は、AVL木ほど高さに厳しくない代わりに、 「色」と「黒高さ」のルールを守ることでバランスを保ちます。

代表的なルールをもう一度整理すると、

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

というものです。

挿入や削除のときに、 これらのルールが崩れた場合、 色の反転（recolor）と回転を組み合わせて修正します。

挿入時の典型的なパターンをイメージで説明します。

赤赤違反の修正

赤黒木では、「赤ノードの子は必ず黒」というルールがあります。 挿入によって「親も赤、子も赤」という状態になると、 このルールに違反します。

このとき、 親の兄弟（叔父ノード）が赤か黒かによって、 修正の仕方が変わります。

叔父が赤の場合、 親と叔父を黒にし、 祖父を赤にすることで、 黒高さを保ちながら「赤赤連続」を解消します。

叔父が黒の場合、 回転を使って親子関係を入れ替え、 その後色を入れ替えることで、 赤赤連続を解消します。

例えば、 「左左」のような形で赤赤違反が起きている場合、 右回転と色の入れ替えで修正します。

このように、赤黒木では 「色の反転」と「回転」を組み合わせて、 ルールを維持するように設計されています。

Java風の赤黒木ノードと色の扱い

赤黒木のノードは、 キーと左右の子に加えて「色」を持ちます。

enum Color {
    RED, BLACK
}

class RBNode {
    int key;
    Color color;
    RBNode left;
    RBNode right;
    RBNode parent;

    RBNode(int key, Color color) {
        this.key = key;
        this.color = color;
    }
}
Java

挿入時には、 新しいノードを赤として挿入し、 その後「修正処理（fixup）」を行います。

修正処理の中で、 親と叔父の色を見て、 必要に応じて色を反転したり、 左回転・右回転を行ったりします。

赤黒木の実装は、 AVL木よりもコード量が多くなりますが、 パターン自体は「赤赤違反をどう解消するか」という観点で整理できます。

Java の TreeMap や TreeSet の内部では、 このような赤黒木のロジックが ジェネリクスや比較器と組み合わされて動いています。

AVL木と赤黒木の性能・用途の違い

AVL木と赤黒木は、 どちらも「自己平衡二分探索木」ですが、 性格が少し違います。

AVL木は、 高さのバランスに非常に厳しいため、 探索が速く、 読み取り中心の用途に向いています。

赤黒木は、 バランスのルールがやや緩く、 挿入・削除の回転回数が少なく済むため、 更新が多い用途に向いています。

Java の標準ライブラリでは、 汎用的な用途に向いた赤黒木が採用されています。 これは、「読み取りも更新もそれなりにある」一般的なシナリオに対して、 赤黒木がバランスの良い選択だからです。

一方で、 特定の用途に特化したライブラリや競技プログラミングでは、 AVL木が選ばれることもあります。

重要なのは、 「どちらも O(log N) の探索を保証するが、 バランスの取り方と更新コストが違う」 という視点を持つことです。

セキュリティ・パフォーマンスの観点から見た自己平衡木

自己平衡木は、 「最悪ケースでも O(log N) の性能を保証する」 という意味で、セキュリティにも関わるデータ構造です。

例えば、 通常の二分探索木を使っていると、 攻撃者が「特定の順番でキーを挿入する」ことで 木を意図的に偏らせ、 探索を O(N) に落とすことができます。

これは、 ハッシュテーブルに対する「悪意のあるハッシュ値」と同じように、 サービスの応答時間を劣化させる攻撃手法になり得ます。

自己平衡木を使うことで、 挿入順に関係なく木の高さが O(log N) に保たれるため、 こうした攻撃に対する耐性が高まります。

ただし、 自己平衡木の実装が複雑であることから、 バグや不正な入力によって ルールが崩れた状態になると、 データ構造全体が破綻する可能性があります。

安全な設計としては、

実装を自分で書く場合は徹底的なテストを行う 可能な限り標準ライブラリや実績のあるライブラリを使う 外部入力から渡されたキーに対して、 比較器や整合性のチェックを適切に行う

といった視点が重要になります。

自己平衡木は「性能を守るための防御線」であり、 その防御線を正しく機能させることが セキュリティにも直結します。

後半のまとめ

後半では、赤黒木やAVL木を一段深く理解するために

回転（rotation）を「親子関係を入れ替えて形を整える操作」として捉えること AVL木のLL・LRなどの不均衡パターンと単回転・二重回転の流れ Java風のAVL木の回転コード断片 赤黒木の「色」と「黒高さ」のルールと、赤赤違反の修正パターン 赤黒木ノードの色付き実装イメージ AVL木と赤黒木の性能・用途の違い 自己平衡木が「最悪ケースの性能を守る防御線」であること セキュリティ・パフォーマンスの観点から見た注意点

を整理しました。

赤黒木やAVL木を理解すると、 「ソート済みのマップやセットをどう実装するか」 「最悪ケースでも性能を守るにはどうするか」 といった設計の問いに対して、 自分の頭で答えを出せるようになります。 それは、アルゴリズムとデータ構造の知識を 実務レベルの設計力へとつなげていく大きなステップです。

前へ
12
スポンサーリンク
タイトルとURLをコピーしました