【C++】二分探索木の回転操作を徹底解説！AVL木のバランス調整プログラム
二分探索木（BST）とは
二分探索木（Binary Search Tree：BST）は、すべてのノードが次の性質を満たすように整列された二分木です。
- 右部分木の条件： ノードの右部分木に含まれるキーは、必ずその親ノードのキーより大きい。
- 左部分木の条件： ノードの左部分木に含まれるキーは、必ずその親ノードのキー以下である。
- 子の数の制限： 各ノードが持てる子は最大2つまで。
木の回転（Tree Rotation）とは
木の回転とは、二分木の要素の順序（ソート順）を崩すことなく木の構造だけを変更する操作です。回転を行うと、あるノードが1段階上へ移動し、別のノードが1段階下へ移動します。
この操作は主に次の目的で使用されます。
- 木の形状を変えて、高さを低く抑える
- 小さい部分木を下へ、大きい部分木を上へ移動することで、探索・挿入などの各種操作のパフォーマンスを向上させる
回転の方向（左回転か右回転か）は、ノードがどちら側にシフトされるか、言い換えればどの子が根（ルート）の位置に来るかによって決まります。
本記事では、C++を使って二分探索木に対する回転操作（AVL木としての自己平衡化を含む）を実行するプログラムを紹介します。
アルゴリズム
Begin
構造体 avl を作成し、データ d、左ポインタ l、右ポインタ r を宣言する。
クラス avl_tree を宣言し、以下の関数を定義する：
height() ：max関数を使って木の高さを計算する。
difference() ：左右の部分木の高さの差（バランス係数）を計算する。
rr_rotat() ：右右（Right-Right）回転を行う。
ll_rotat() ：左左（Left-Left）回転を行う。
lr_rotat() ：左右（Left-Right）回転を行う。
rl_rotat() ：右左（Right-Left）回転を行う。
balance() ：バランス係数を取得して木を均衡化する。
差を bal_factor に格納し、
bal_factor > 1 なら左部分木をバランスさせ、
bal_factor < -1 なら右部分木をバランスさせる。
insert() ：木に要素を挿入する。
show() ：木の構造を表示する。
inorder() ：中間順走査（Inorder）の結果を表示する。
preorder() ：先行順走査（Preorder）の結果を表示する。
postorder() ：後行順走査（Postorder）の結果を表示する。
main() 内では switch 文により選択肢に応じて各関数を呼び出す。
End.
C++サンプルコード
以下は、AVL木として4種類の回転（LL・RR・LR・RL）を実装し、挿入時に自動的にバランスを保つ完全なサンプルプログラムです。
#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;
}
実行結果
このプログラムを実行すると、メニュー形式で操作を選択できます。値を挿入すると、必要に応じて自動的に回転（LL回転やRR回転など）が実行され、木のバランスが保たれます。以下は実際の実行例です。
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: 4 Left-Left Rotation ... 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: 52 Right-Right Rotation ... Enter your Choice: 6
まとめ
本プログラムでは、二分探索木の基本的な性質を保ちながら、AVL木の手法を用いて挿入時に自動的に回転処理を行うことで、木の偏りを防ぎ、常にバランスの取れた状態を維持しています。これにより、最悪の場合でも O(log n) の計算量で探索・挿入操作が可能となり、データ構造として高い性能を発揮します。
-
C++でAVL木（AVLツリー）を実装する方法：回転操作とサンプルコードを徹底解説
AVL木とは AVL木（AVL Tree）は、自己平衡型二分探索木（Self-balancing Binary Search Tree）の一種です。すべてのノードにおいて、左部分木と右部分木の高さの差が「1以下」に保たれるという性質を持っています。この平衡条件により、木が片側に偏って成長することを防ぎ、検索・挿入・削除といった操作を常に効率的（O(log n)）に行うことができます。 木の回転（Tree Rotation）とは 木の回転とは、要素の順序（ソート順）を崩すことなく木の構造を変更する操作のことです。あるノードを一段上へ移動させ、別のノードを一段下へ移動させることで実現されます。 回
-
C++で二分探索木（AVL木）の左回転を実装するプログラム
二分探索木とは二分探索木（Binary Search Tree）とは、すべてのノードが次の性質を満たすソート済みの二分木です。ノードの右部分木には、親ノードのキーより大きいキーがすべて格納されるノードの左部分木には、親ノードのキーより小さいキーがすべて格納される各ノードが持てる子ノードは最大2つまで木の回転（Tree Rotation）とは木の回転とは、二分木の要素の順序（ソート順）を崩すことなく木の構造を変更する操作です。回転では、あるノードを1つ上へ、別のノードを1つ下へ移動させます。回転は木の形状を変えるために使われ、小さな部分木を下へ、大きな部分木を上へ移動することで木の高さを抑えられ