【C++】AVLツリーが要素の追加・削除時に実行する回転の種類を出力するプログラム

AVLツリー（AVL木）とは、自己平衡型二分探索木の一種です。すべてのノードにおいて、左部分木と右部分木の高さの差が1を超えないように保たれることが最大の特徴です。

木の回転とは

木の回転（Tree Rotation）とは、AVLツリー上の要素の順序に影響を与えることなく、ツリーの構造を変更する操作のことです。回転では、あるノードを1つ上へ移動させ、別のノードを1つ下へ移動させます。

この操作は、小さい部分木を下へ、大きい部分木を上へ移動させることでツリーの高さを減らし、多くのツリー操作のパフォーマンスを向上させるために使われます。回転の方向は、ノードがどちら側にシフトされるかによって決まります。言い換えれば、どの子ノードがルートの座を引き継ぐかによって決まるとも言えます。

本記事では、AVLツリーを実装し、挿入時に実行された回転の種類を出力するC++プログラムを紹介します。

関数の説明

• 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）でツリーを走査します。

C++サンプルコード

#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;
}

実行結果

以下は、実際にプログラムを実行した際の出力例です。値「4」を挿入したときに「Left-Left Rotation」が、「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: 1
Enter value to be inserted: 13
Enter your Choice: 1
Enter value to be inserted: 10
Enter your Choice: 1
Enter value to be inserted: 15
Enter your Choice: 1
Enter value to be inserted: 5
Enter your Choice: 1
Enter value to be inserted: 11
Enter your Choice: 1
Enter value to be inserted: 4
Left-Left Rotation
Enter your Choice: 1
Enter value to be inserted: 8
Enter your Choice: 1
Enter value to be inserted: 16
Enter your Choice: 3
Inorder Traversal:
4 5 8 10 11 13 15 16
Enter your Choice: 4
Preorder Traversal:
10 5 4 8 13 11 15 16
Enter your Choice: 5
Postorder Traversal:
4 8 5 11 16 15 13 10
Enter your Choice: 1
Enter value to be inserted: 14
Enter your Choice: 1
Enter value to be inserted: 3
Enter your Choice: 1
Enter value to be inserted: 7
Enter your Choice: 1
Enter value to be inserted: 9
Enter your Choice: 1
Enter value to be inserted: 52
Right-Right Rotation
Enter your Choice: 6

まとめ

このプログラムでは、AVLツリーへの要素挿入時に平衡係数を計算し、必要に応じて4種類の回転（LL回転・RR回転・LR回転・RL回転）を自動的に実行します。回転が発生した際には、その種類がコンソールに出力されるため、自己平衡化の仕組みを視覚的に理解するのに最適な教材となっています。中順・前順・後順の各走査も実装されており、平衡化されたツリーの構造をさまざまな角度から確認できます。