AVL木

Q: AVL木と赤黒木の違いは何ですか？

どちらも `O(log n)` の操作を持つ自己平衡BSTです。AVL木はより厳密に平衡が取られているため検索がわずかに速いですが、挿入/削除でより多くの回転を行う場合があります。赤黒木はより緩やかに平衡が取られ、回転の少なさを優先します。そのため多くの標準ライブラリはマップや集合に赤黒木を使います。

Q: なぜ通常の二分探索木ではなくAVL木を使うのですか？

通常のBSTは、値がソート順で届くと偏った連鎖を形成し、操作が `O(n)` に劣化することがあります。AVL木は回転して平衡を保ち、挿入順序に関わらず `O(log n)` の高さと操作を保証します。

最終更新 2026年7月1日

AVL木は自己平衡二分探索木です。通常のBSTのように動作しますが、挿入のたびに各祖先の平衡係数（左右の部分木の高さの差）を調べ、いずれかのノードが不均衡になった場合（差が1より大きい場合）、回転を行ってバランスを回復します。上部の再生ボタンを押すと、値が挿入され、木が回転して形を整える様子を見られます。

木がわずかにでも傾きすぎることを決して許さないため、AVL木は O(log n) の高さを保証し、検索・挿入・削除は常に O(log n) です。これは通常のBSTを台無しにするソート済み入力に対しても成り立ちます。その代償は、挿入ごとの追加の回転と高さの管理です。

時間計算量と空間計算量

操作	計算量	備考
検索	O(log n)	高さは常に ~1.44 log n
挿入	O(log n)	加えて O(1) 回転
削除	O(log n)	加えて O(log n) 回転
空間	O(n)	ノードごとに高さフィールドが1つ

4つの回転ケース

ケース	不均衡	修正
左-左	左の子の左側が重い	1回の右回転
右-右	右の子の右側が重い	1回の左回転
左-右	左の子の右側が重い	左回転してから右回転
右-左	右の子の左側が重い	右回転してから左回転

具体例

[10, 20, 30, 40, 50, 25] を1つずつ挿入：

ステップ	構造	動作
`10` を挿入	`10`	最初のノードが根になる；均衡
`20` を挿入	`10(_, 20)`	`10` の右へ進む；まだ均衡
`30` を挿入	`20(10, 30)`	`10` で右-右、そこで1回の左回転が `20` を根へ押し上げる
`40` を挿入	`20(10, 30(_, 40))`	`30` の右へ進む；すべての平衡係数が ±1 以内に収まる
`50` を挿入	`20(10, 40(30, 50))`	`30` で右-右、そこで `30` での左回転が `40` を押し上げる
`25` を挿入	`30(20(10, 25), 40(_, 50))`	`20` で右-左：`40` の部分木を右回転し、その後 `20` を左回転

AVL木を使うべき場面

使うべきとき	避けるべきとき
検索が挿入をはるかに上回り、可能な限り最も低い高さが欲しいとき	挿入と削除が支配的なとき - 追加の回転と再平衡は赤黒木より高くつく
敵対的またはソート済みの入力に対してさえ、保証された `O(log n)` の最悪計算量が必要なとき	単純なハッシュテーブルで十分なとき - 順序付き走査や範囲クエリが不要
順序付き操作が必要なとき：中間順走査、前者/後者、範囲クエリ	データ集合が非常に小さいとき - 通常のBSTやソート済み配列の方が単純で十分に速い
データがすでにソート済みで届く可能性があり、不均衡なBSTを連結リストに変えてしまうとき	非常に厳しいメモリ環境で、ノードごとの高さフィールドの追加メモリを負担できないとき

AVL Treeのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なAVL Treeの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのAVL TreeのコードPython
1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6        self.height = 17
8
9def height(node):10    return node.height if node else 011
12
13def update(node):14    node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18    x = y.left19    y.left = x.right20    x.right = y21    update(y)22    update(x)23    return x24
25
26def rotate_left(x):27    y = x.right28    x.right = y.left29    y.left = x30    update(x)31    update(y)32    return y33
34
35def insert(node, key):36    if node is None:37        return Node(key)38    if key < node.key:39        node.left = insert(node.left, key)40    else:41        node.right = insert(node.right, key)42    update(node)43    balance = height(node.left) - height(node.right)44    # Four imbalance cases: LL, RR, LR, RL45    if balance > 1 and key < node.left.key:46        return rotate_right(node)47    if balance < -1 and key > node.right.key:48        return rotate_left(node)49    if balance > 1:50        node.left = rotate_left(node.left)51        return rotate_right(node)52    if balance < -1:53        node.right = rotate_right(node.right)54        return rotate_left(node)55    return node56
57
58def inorder(node):59    if node is None:60        return []61    return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66    root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)
このコードをPythonプレイグラウンドで実行

JavaScriptでのAVL TreeのコードJavaScript
1class Node {2    constructor(key) {3        this.key = key;4        this.left = null;5        this.right = null;6        this.height = 1;7    }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12    n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17    const x = y.left;18    y.left = x.right;19    x.right = y;20    update(y);21    update(x);22    return x;23}24
25function rotateLeft(x) {26    const y = x.right;27    x.right = y.left;28    y.left = x;29    update(x);30    update(y);31    return y;32}33
34function insert(node, key) {35    if (!node) return new Node(key);36    if (key < node.key) node.left = insert(node.left, key);37    else node.right = insert(node.right, key);38    update(node);39    const b = balance(node);40    // Four rebalancing cases: LL, RR, LR, RL41    if (b > 1 && key < node.left.key) return rotateRight(node);42    if (b < -1 && key > node.right.key) return rotateLeft(node);43    if (b > 1) {44        node.left = rotateLeft(node.left);45        return rotateRight(node);46    }47    if (b < -1) {48        node.right = rotateRight(node.right);49        return rotateLeft(node);50    }51    return node;52}53
54function inorder(node, out = []) {55    if (!node) return out;56    inorder(node.left, out);57    out.push(node.key);58    inorder(node.right, out);59    return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));
このコードをJavaScriptプレイグラウンドで実行

JavaでのAVL TreeのコードJava
1public class Main {2    static class Node {3        int key, height = 1;4        Node left, right;5        Node(int key) { this.key = key; }6    }7
8    static int height(Node n) { return n == null ? 0 : n.height; }9    static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10    static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12    static Node rotateRight(Node y) {13        Node x = y.left;14        y.left = x.right;15        x.right = y;16        update(y); update(x);17        return x;18    }19
20    static Node rotateLeft(Node x) {21        Node y = x.right;22        x.right = y.left;23        y.left = x;24        update(x); update(y);25        return y;26    }27
28    static Node insert(Node node, int key) {29        if (node == null) return new Node(key);30        if (key < node.key) node.left = insert(node.left, key);31        else node.right = insert(node.right, key);32        update(node);33        int b = balance(node);34        // Four imbalance cases: LL, RR, LR, RL35        if (b > 1 && key < node.left.key) return rotateRight(node);36        if (b < -1 && key > node.right.key) return rotateLeft(node);37        if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38        if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39        return node;40    }41
42    static void inorder(Node n, StringBuilder sb) {43        if (n == null) return;44        inorder(n.left, sb);45        sb.append(n.key).append(" ");46        inorder(n.right, sb);47    }48
49    public static void main(String[] args) {50        Node root = null;51        int[] keys = {10, 20, 30, 40, 50, 25};52        for (int k : keys) root = insert(root, k);53        StringBuilder sb = new StringBuilder();54        inorder(root, sb);55        System.out.println("Inorder: " + sb.toString().trim());56        System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57    }58}
このコードをJavaプレイグラウンドで実行

C++でのAVL TreeのコードC++
1#include <algorithm>2#include <iostream>3
4struct Node {5    int value;6    int height = 1;7    Node* left = nullptr;8    Node* right = nullptr;9    explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15    n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19    Node* x = y->left;20    y->left = x->right;21    x->right = y;22    updateHeight(y);23    updateHeight(x);24    return x;25}26
27Node* rotateLeft(Node* x) {28    Node* y = x->right;29    x->right = y->left;30    y->left = x;31    updateHeight(x);32    updateHeight(y);33    return y;34}35
36Node* insert(Node* node, int value) {37    if (node == nullptr) return new Node(value);38    if (value < node->value) node->left = insert(node->left, value);39    else node->right = insert(node->right, value);40    updateHeight(node);41    int balance = balanceFactor(node);42    // Four rebalancing cases: LL, RR, LR, RL43    if (balance > 1 && value < node->left->value) return rotateRight(node);44    if (balance < -1 && value > node->right->value) return rotateLeft(node);45    if (balance > 1) {46        node->left = rotateLeft(node->left);47        return rotateRight(node);48    }49    if (balance < -1) {50        node->right = rotateRight(node->right);51        return rotateLeft(node);52    }53    return node;54}55
56void inorder(const Node* n) {57    if (n == nullptr) return;58    inorder(n->left);59    std::cout << n->value << "(h" << n->height << ") ";60    inorder(n->right);61}62
63int main() {64    Node* root = nullptr;65    for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66    std::cout << "Root after rebalancing: " << root->value << "\n";67    std::cout << "In-order: ";68    inorder(root);69    std::cout << "\n";70    return 0;71}
このコードをC++プレイグラウンドで実行

CでのAVL TreeのコードC
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value, height;6    struct Node* left;7    struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15    Node* n = calloc(1, sizeof(Node));16    n->value = value;17    n->height = 1;18    return n;19}20
21void updateHeight(Node* n) {22    n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26    Node* x = y->left;27    y->left = x->right;28    x->right = y;29    updateHeight(y);30    updateHeight(x);31    return x;32}33
34Node* rotateLeft(Node* x) {35    Node* y = x->right;36    x->right = y->left;37    y->left = x;38    updateHeight(x);39    updateHeight(y);40    return y;41}42
43Node* insert(Node* node, int value) {44    if (node == NULL) return newNode(value);45    if (value < node->value) node->left = insert(node->left, value);46    else node->right = insert(node->right, value);47    updateHeight(node);48    int balance = balanceFactor(node);49    // Four rebalancing cases: LL, RR, LR, RL50    if (balance > 1 && value < node->left->value) return rotateRight(node);51    if (balance < -1 && value > node->right->value) return rotateLeft(node);52    if (balance > 1) {53        node->left = rotateLeft(node->left);54        return rotateRight(node);55    }56    if (balance < -1) {57        node->right = rotateRight(node->right);58        return rotateLeft(node);59    }60    return node;61}62
63void inorder(const Node* n) {64    if (n == NULL) return;65    inorder(n->left);66    printf("%d(h%d) ", n->value, n->height);67    inorder(n->right);68}69
70int main(void) {71    int values[] = {10, 20, 30, 40, 50, 25};72    Node* root = NULL;73    for (int i = 0; i < 6; i++) root = insert(root, values[i]);74    printf("Root after rebalancing: %d\n", root->value);75    printf("In-order: ");76    inorder(root);77    printf("\n");78    return 0;79}
このコードをCプレイグラウンドで実行

AVL木のよくある質問

AVL木における平衡係数とは何ですか？

ノードの平衡係数とは、その左部分木の高さから右部分木の高さを引いた値です。AVL木は各ノードの平衡係数を -1、0、+1 のいずれかに保ちます。挿入によってその範囲を外れた場合、回転がバランスを回復します。

AVL木と赤黒木の違いは何ですか？

どちらも O(log n) の操作を持つ自己平衡BSTです。AVL木はより厳密に平衡が取られているため検索がわずかに速いですが、挿入/削除でより多くの回転を行う場合があります。赤黒木はより緩やかに平衡が取られ、回転の少なさを優先します。そのため多くの標準ライブラリはマップや集合に赤黒木を使います。

なぜ通常の二分探索木ではなくAVL木を使うのですか？

通常のBSTは、値がソート順で届くと偏った連鎖を形成し、操作が O(n) に劣化することがあります。AVL木は回転して平衡を保ち、挿入順序に関わらず O(log n) の高さと操作を保証します。

データベースのインデックスにはAVL木と赤黒木のどちらが良いですか？

ワークロード次第です。AVL木はより厳格に平衡が取られているため、読み取りが支配的で最短の検索経路が欲しい場合に有利です。しかし、ほとんどのデータベースや言語ライブラリは赤黒木（またはB木）を選びます。なぜなら書き込みの多いワークロードでより少ない回転で再平衡でき、挿入や削除が頻繁なときにはそれがより重要だからです。

1回のAVL挿入に必要な回転は何回ですか？

1つの値を挿入した後に木を再平衡するには、単回転または二重（2段階）回転のいずれか、最大1回の回転で済みます。これは挿入が部分木の高さを最大でも1しか増やさないため、最も下の不均衡な祖先での1回の修正で十分だからです。削除は異なり、再平衡が根に向かって伝播するにつれて最大 O(log n) 回の回転が必要になることがあります。

回転のたびにノードの高さを更新する必要がありますか？

はい - よくあるバグは、ポインタを正しく回転させたのに、関与する2つのノードの高さの再計算を忘れることです。各回転の後、まず降格したノードの高さを、次に昇格したノードの高さを更新する必要があります。昇格したノードの高さは新しい子に依存するためです。これを怠ると古い平衡係数が残り、将来の再平衡の判断が壊れます。