C++で二分探索木（AVL木）の左回転を実装するプログラム

二分探索木とは

二分探索木（Binary Search Tree）とは、すべてのノードが次の性質を満たすソート済みの二分木です。

• ノードの右部分木には、親ノードのキーより大きいキーがすべて格納される
• ノードの左部分木には、親ノードのキーより小さいキーがすべて格納される
• 各ノードが持てる子ノードは最大2つまで

木の回転（Tree Rotation）とは

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

回転は木の形状を変えるために使われ、小さな部分木を下へ、大きな部分木を上へ移動することで木の高さを抑えられます。その結果、検索・挿入・削除など多くの木操作のパフォーマンスが向上します。

回転の方向は、ノードがどちら側にシフトされるかによって決まります。本記事では、C++による二分探索木（AVL木）の左回転を含むバランス操作の実装例を紹介します。

関数の説明

• height(avl *)：指定されたAVL木の高さを計算します。
• difference(avl *)：指定されたノードの左右の部分木の高さの差（平衡係数）を計算します。
• avl *rr_rotat(avl *)：RR回転。右回転を適用するケース（右部分木に偏った場合）の回転処理です。
• avl *ll_rotat(avl *)：LL回転。左回転を適用するケース（左部分木に偏った場合）の回転処理です。
• avl *lr_rotat(avl*)：LR回転。左回転の後に右回転を組み合わせた処理です。
• avl *rl_rotat(avl *)：RL回転。右回転の後に左回転を組み合わせた処理です。
• avl * balance(avl *)：平衡係数をもとに、木全体のバランスを取る操作を行います。
• avl * insert(avl*, int)：挿入操作を行います。この関数を使って木に値を追加します。
• show(avl*, int)：木の構造と値を表示します。
• inorder(avl *)：木を中間順（In-order）で走査します。
• preorder(avl *)：木を先行順（Pre-order）で走査します。
• postorder(avl*)：木を後行順（Post-order）で走査します。

サンプルコード

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

実行結果

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木として知られる自己平衡型二分探索木を実装しています。値を挿入するたびにbalance()関数が平衡係数をチェックし、木が偏っている場合はLL・RR・LR・RLのいずれかの回転を自動的に適用して高さを一定に保ちます。これにより、最悪の場合でも検索・挿入・削除をO(log n)の時間計算量で実行できるのが大きな特徴です。