AVLツリー: 回転、挿入、削除 C++ 例:
サラ・チェン
AVL ツリーとは何ですか?
AVL ツリー は、左右のサブツリーの高さの差が -1、0、または +1 である二分探索ツリーです。
AVL ツリーは、自己平衡型二分探索ツリーとも呼ばれます。 これらのツリーは、対数検索時間を維持するのに役立ちます。 この名前は、発明者 (AVL) の Adelson、Velsky、Landis にちなんで命名されました。
AVL ツリーはどのように機能しますか?
AVL ツリーの必要性をより深く理解するために、単純な二分探索ツリーの欠点をいくつか見てみましょう。
バイナリ検索ツリーに指定された順序で挿入された次のキーを検討します。
キーを値の昇順で挿入すると、ツリーの高さは線形に大きくなります。したがって、最悪の場合でも、検索操作には O(n) かかります。
要素の検索には直線的な時間がかかります。 したがって、 二分探索木 構造。一方、木の高さがバランスが取れていれば、検索時間は短縮されます。
次に、同じキーが異なる順序で挿入されたものを見てみましょう。
ここでは、キーは同じですが、挿入順序が異なるため、位置が異なり、木の高さのバランスが保たれています。 したがって、ツリーのどの要素についても、検索に O(log n) を超えることはありません。 挿入が正しく行われれば、木の高さのバランスが保たれることがわかりました。
AVL ツリーでは、挿入操作中にツリーの高さをチェックします。バイナリ検索ツリーの基本的な特性に違反することなく、バランスの取れた高さを維持するために変更が行われます。
AVL ツリーのバランス係数
バランス係数 (BF) は、AVL ツリー内のすべてのノードの基本的な属性であり、ツリーの高さの監視に役立ちます。
バランスファクターの特性
- バランス係数は、左側のサブツリーと右側のサブツリーの高さの差として知られています。
- バランス係数(ノード) = 高さ(ノード→左) – 高さ(ノード→右)
- BF の許容値は –1、0、および +1 です。
- 値 –1 は、右側のサブツリーに余分な XNUMX つが含まれていること、つまりツリーが右側に重いことを示します。
- 値 +1 は、左側のサブツリーに余分な XNUMX つが含まれていること、つまりツリーが左側に重いことを示します。
- 値 0 は、ツリーの両側に等しいノードが含まれていること、つまりツリーが完全にバランスが取れていることを示します。
AVL 回転
AVL ツリー自体のバランスを整えるため、ツリーにノードを挿入または削除するときに、回転が実行されます。
以下のLL回転、RR回転、LR回転、RL回転を実行します。
- 左 - 左回転
- 右 – 右回転
- 右 – 左回転
- 左→右回転
左 - 左回転
この回転は、新しいノードが左側のサブツリーの左側の子に挿入されるときに実行されます。
右回転を 2 回実行します。 このタイプの回転は、ノードのバランス係数が +1 であり、その左の子ノードのバランス係数が +XNUMX である場合に識別されます。
右 – 右回転
この回転は、新しいノードが右のサブツリーの右の子に挿入されるときに実行されます。
単一の左回転が実行されます。 このタイプの回転は、ノードのバランス係数が -2 で、その右側の子ノードのバランス係数が -1 である場合に識別されます。
右 – 左回転
この回転は、新しいノードが左側のサブツリーの右側の子に挿入されるときに実行されます。
この回転は、ノードのバランス係数が -2 であり、その右側の子ノードのバランス係数が +1 である場合に実行されます。
左→右回転
この回転は、新しいノードが右のサブツリーの左の子に挿入されるときに実行されます。
この回転は、ノードのバランス係数が +2 であり、その左の子ノードのバランス係数が -1 である場合に実行されます。
AVL ツリーへの挿入
挿入操作は、単純な二分探索木とほぼ同じです。挿入するたびに、木の高さを調整します。挿入操作には、最悪の O(log n) の時間計算量がかかります。
ステップ 1: BST と同じ挿入アルゴリズムを使用して、AVL ツリーにノードを挿入します。 上の例では、160 を挿入します。
ステップ 2: ノードが追加されると、各ノードのバランス係数が更新されます。 160 を挿入すると、すべてのノードのバランス係数が更新されます。
ステップ 3: 次に、バランス係数の範囲に違反しているノードがあるかどうかを確認し、バランス係数に違反している場合は、以下のケースを使用して回転を実行します。 上の例では、バランス係数 350 に違反しており、ケース 1 が適用できるようになり、LL 回転を実行してツリーのバランスが再度とられます。
- BF(node) = +2 かつ BF(node -> left-child) = +1 の場合、LL 回転を実行します。
- BF(node) = -2 かつ BF(node -> right-child) = 1 の場合、RR ローテーションを実行します。
- BF(node) = -2 および BF(node -> right-child) = +1 の場合、RL 回転を実行します。
- BF(node) = +2 および BF(node -> left-child) = -1 の場合、LR 回転を実行します。
AVL ツリーの削除
削除も非常に簡単です。 単純な二分探索ツリーと同じロジックを使用して削除します。 削除後、必要に応じてツリーを再構築し、バランスのとれた高さを維持します。
ステップ1： ツリー内の要素を見つけます。
ステップ2： BST の削除に従って、ノードを削除します。
ステップ3： XNUMX つのケースが考えられます:-
ケース1： 右側のサブツリーから削除します。
- 1A. BF(node) = +2 かつ BF(node -> left-child) = +1 の場合、LL 回転を実行します。
- 1B. BF(node) = +2 および BF(node -> left-child) = -1 の場合、LR 回転を実行します。
- 1C. BF(node) = +2 かつ BF(node -> left-child) = 0 の場合、LL 回転を実行します。
ケース2: 左側のサブツリーから削除します。
- 2A. BF(node) = -2 および BF(node -> right-child) = -1 の場合、RR ローテーションを実行します。
- 2B. BF(node) = -2 および BF(node -> right-child) = +1 の場合、RL 回転を実行します。
- 2C。 BF(node) = -2 かつ BF(node -> right-child) = 0 の場合、RR ローテーションを実行します。
C++ AVLツリーの例
以下は C++ AVL ツリーを実装するもの:
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
上記のコードの実行例:
- 上記のコードをコピーし、「avl.cpp」に貼り付けます。
- コードをコンパイルします。
g++ avl.cpp -o run
- コードを実行します。
./run
AVL ツリーの利点
- AVL ツリーの高さは常にバランスが保たれています。 高さが log N を超えることはありません。N はツリー内のノードの総数です。
- 単純なバイナリ検索ツリーと比較すると、検索時間の複雑さが軽減されます。
- AVL ツリーには自己バランス機能があります。
製品概要
- AVL ツリーは、自己平衡型の二分探索ツリーです。
- バランス係数は AVL ツリーの基本的な属性です
- ノードのバランス係数は、そのノードの左右のサブツリーの高さの差として定義されます。
- バランス係数の有効な値は、-1、0、および +1 です。
- 挿入および削除操作では、バランス係数に違反した後に回転を実行する必要があります。
- 挿入、削除、検索操作の時間計算量は O(log N) です。
- AVL ツリーは、二分探索ツリーのすべてのプロパティに従います。
- 左側のサブツリーには、ルート ノードよりも小さいノードがあります。 右側のサブツリーには、ルート ノードよりも常に大きいノードがあります。
- AVL ツリーは、挿入操作や削除操作に比べて検索操作の方が頻繁に行われる場合に使用されます。
