C++でAVL木（AVLツリー）を実装する方法：回転操作とサンプルコードを徹底解説

AVL木とは

AVL木（AVL Tree）は、自己平衡型二分探索木（Self-balancing Binary Search Tree）の一種です。すべてのノードにおいて、左部分木と右部分木の高さの差が「1以下」に保たれるという性質を持っています。この平衡条件により、木が片側に偏って成長することを防ぎ、検索・挿入・削除といった操作を常に効率的（O(log n)）に行うことができます。

木の回転（Tree Rotation）とは

木の回転とは、要素の順序（ソート順）を崩すことなく木の構造を変更する操作のことです。あるノードを一段上へ移動させ、別のノードを一段下へ移動させることで実現されます。

回転は木の形状を変えるために用いられ、小さい部分木を下へ、大きい部分木を上へ移動させることで木の高さを抑えます。その結果、多くの木に対する操作のパフォーマンスが向上します。回転の方向は、ノードがどちら側へシフトされるかで決まると説明されることが多く、別の見方では「どの子が根（ルート）の位置を引き継ぐか」で決まるとも言われます。

各関数の説明

本プログラムで使用している主な関数は以下の通りです。

• height(avl *)：指定されたAVL木の高さを計算します。
• difference(avl *)：指定された木の左右部分木の高さの差（平衡係数）を計算します。
• avl *rr_rotat(avl *)：右右回転（Right-Right Rotation）。右回転を続けて2回組み合わせた操作です。
• avl *ll_rotat(avl *)：左左回転（Left-Left Rotation）。左回転を続けて2回組み合わせた操作です。
• avl *lr_rotat(avl *)：左右回転（Left-Right Rotation）。左回転の後に右回転を行う操作です。
  
• avl *rl_rotat(avl *)：右左回転（Right-Left Rotation）。右回転の後に左回転を行う操作です。
  
• avl *balance(avl *)：平衡係数を取得し、木に対して平衡化（バランス調整）操作を実行します。
• avl *insert(avl*, int)：挿入操作を実行します。この関数を使って木に値を挿入します。
• show(avl*, int)：木の構造と値を整形して表示します。
• inorder(avl *)：木を中間順（In-order）で走査します。
• preorder(avl *)：木を先行順（Pre-order）で走査します。
• postorder(avl*)：木を後行順（Post-order）で走査します。

サンプルコード

以下は、AVL木をC++で実装した完全なサンプルコードです。メニュー形式の対話型プログラムになっており、値の挿入、木の表示、3種類の走査が試せます。

#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
    int d;
    struct avl *l;
    struct avl *r;
}*r;
class avl_tree {
    public:
        int height(avl *);
        int difference(avl *);
        avl *rr_rotat(avl *);
        avl *ll_rotat(avl *);
        avl *lr_rotat(avl*);
        avl *rl_rotat(avl *);
        avl * balance(avl *);
        avl * insert(avl*, int);
        void show(avl*, int);
        void inorder(avl *);
        void preorder(avl *);
        void postorder(avl*);
        avl_tree() {
            r = NULL;
        }
};
int avl_tree::height(avl *t) {
    int h = 0;
    if (t != NULL) {
        int l_height = height(t->l);
        int r_height = height(t->r);
        int max_height = max(l_height, r_height);
        h = max_height + 1;
    }
    return h;
}
int avl_tree::difference(avl *t) {
    int l_height = height(t->l);
    int r_height = height(t->r);
    int b_factor = l_height - r_height;
    return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
    avl *t;
    t = parent->r;
    parent->r = t->l;
    t->l = parent;
    cout<<"Right-Right Rotation";
    return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
    avl *t;
    t = parent->l;
    parent->l = t->r;
    t->r = parent;
    cout<<"Left-Left Rotation";
    return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
    avl *t;
    t = parent->l;
    parent->l = rr_rotat(t);
    cout<<"Left-Right Rotation";
    return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
    avl *t;
    t = parent->r;
    parent->r = ll_rotat(t);
    cout<<"Right-Left Rotation";
    return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
    int bal_factor = difference(t);
    if (bal_factor > 1) {
        if (difference(t->l) > 0)
            t = ll_rotat(t);
        else
            t = lr_rotat(t);
    } else if (bal_factor < -1) {
        if (difference(t->r) > 0)
            t = rl_rotat(t);
        else
            t = rr_rotat(t);
    }
    return t;
}
avl *avl_tree::insert(avl *r, int v) {
    if (r == NULL) {
        r = new avl;
        r->d = v;
        r->l = NULL;
        r->r = NULL;
        return r;
    } else if (v< r->d) {
        r->l = insert(r->l, v);
        r = balance(r);
    } else if (v >= r->d) {
        r->r = insert(r->r, v);
        r = balance(r);
    } return r;
}
void avl_tree::show(avl *p, int l) {
    int i;
    if (p != NULL) {
        show(p->r, l+ 1);
        cout<<" ";
        if (p == r)
            cout << "Root -> ";
        for (i = 0; i < l&& p != r; i++)
            cout << " ";
            cout << p->d;
            show(p->l, l + 1);
    }
}
void avl_tree::inorder(avl *t) {
    if (t == NULL)
        return;
        inorder(t->l);
        cout << t->d << " ";
        inorder(t->r);
}
void avl_tree::preorder(avl *t) {
    if (t == NULL)
        return;
        cout << t->d << " ";
        preorder(t->l);
        preorder(t->r);
}
void avl_tree::postorder(avl *t) {
    if (t == NULL)
        return;
        postorder(t ->l);
        postorder(t ->r);
        cout << t->d << " ";
}
int main() {
    int c, i;
    avl_tree avl;
    while (1) {
        cout << "1.Insert Element into the tree" << endl;
        cout << "2.show Balanced AVL Tree" << endl;
        cout << "3.InOrder traversal" << endl;
        cout << "4.PreOrder traversal" << endl;
        cout << "5.PostOrder traversal" << endl;
        cout << "6.Exit" << endl;
        cout << "Enter your Choice: ";
        cin >> c;
        switch (c) {
            case 1:
                cout << "Enter value to be inserted: ";
                cin >> i;
                r = avl.insert(r, i);
                break;
            case 2:
                if (r == NULL) {
                    cout << "Tree is Empty" << endl;
                    continue;
                }
                cout << "Balanced AVL Tree:" << endl;
                avl.show(r, 1);
                cout<<endl;
                break;
            case 3:
                cout << "Inorder Traversal:" << endl;
                avl.inorder(r);
                cout << endl;
                break;
            case 4:
                cout << "Preorder Traversal:" << endl;
                avl.preorder(r);
                cout << endl;
                break;
            case 5:
                cout << "Postorder Traversal:" << endl;
                avl.postorder(r);
                cout << endl;
                break;
            case 6:
                exit(1);
                break;
            default:
                cout << "Wrong Choice" << endl;
        }
    }
    return 0;
}

実行結果

プログラムをコンパイルして実行すると、以下のような対話型メニューが表示されます。値を挿入していくと、平衡条件が崩れたタイミングで自動的に回転処理（例：「Left-Left Rotation」「Right-Right Rotation」）が実行され、木が常にバランスの取れた状態に保たれているのが確認できます。

1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 13
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 10
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 15
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 5
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 11
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 4
Left-Left Rotation1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 8
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 16
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
4 5 8 10 11 13 15 16
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 4
Preorder Traversal:
10 5 4 8 13 11 15 16
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 5
Postorder Traversal:
4 8 5 11 16 15 13 10
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 14
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 3
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 7
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 9
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 52
Right-Right Rotation
1.Insert Element into the tree
2.show Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 6