AVL 트리: 회전, 삽입, 삭제 C++ 예

AVL 트리란 무엇입니까?

AVL 트리 왼쪽과 오른쪽 하위 트리의 높이 차이가 -1, 0 또는 +1인 이진 검색 트리입니다.

AVL 트리는 자체 균형 이진 검색 트리라고도 합니다. 이러한 트리는 로그 검색 시간을 유지하는 데 도움이 됩니다. 이 이름은 발명자(AVL)인 Adelson, Velsky 및 Landis의 이름을 따서 명명되었습니다.

AVL 트리는 어떻게 작동하나요?

AVL 트리의 필요성을 더 잘 이해하기 위해 간단한 이진 검색 트리의 몇 가지 단점을 살펴보겠습니다.

다음 키가 이진 검색 트리에 주어진 순서대로 삽입되었다고 생각해 보세요.


AVL 트리 작업
AVL 트리 시각화

키를 값의 증가 순서대로 삽입하면 트리의 높이는 선형적으로 커집니다. 따라서 최악의 경우 검색 작업은 O(n)이 걸립니다.

요소를 검색하는 데 선형 시간이 걸립니다. 따라서 다음을 사용해도 소용이 없습니다. 이진 검색 트리 구조. 반면에, 트리의 높이가 균형을 이루면 검색 시간이 더 빨라집니다.

이제 동일한 키를 다른 순서로 삽입한 것을 살펴보겠습니다.

AVL 트리 작업

여기서 키는 동일하지만 삽입 순서가 다르기 때문에 위치도 다르고 트리 높이도 균형을 유지합니다. 따라서 검색은 트리의 모든 요소에 대해 O(log n) 이상 걸리지 않습니다. 삽입이 올바르게 수행되면 나무 높이의 균형이 유지될 수 있다는 것이 이제 분명해졌습니다.

AVL 트리에서 우리는 삽입 작업 중에 트리의 높이를 확인합니다. 이진 탐색 트리의 기본 속성을 위반하지 않고 균형 잡힌 높이를 유지하기 위해 수정이 이루어집니다.

AVL 트리의 균형 요소

BF(균형 인자)는 나무 높이를 모니터링하는 데 도움이 되는 AVL 트리의 모든 노드의 기본 속성입니다.

밸런스 팩터의 특성


AVL 트리의 균형 요소

균형 인자 AVL 트리
  • 균형 인자는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이로 알려져 있습니다.
  • 균형계수(노드) = 높이(노드->왼쪽) – 높이(노드->오른쪽)
  • 허용되는 BF 값은 -1, 0, +1입니다.
  • -1 값은 오른쪽 하위 트리에 하나의 추가 항목이 포함되어 있음을 나타냅니다. 즉, 트리가 오른쪽으로 무겁습니다.
  • 값 +1은 왼쪽 하위 트리에 하나의 추가 트리가 포함되어 있음을 나타냅니다. 즉, 트리가 무겁게 남아 있습니다.
  • 값 0은 트리의 양쪽에 동일한 노드가 포함되어 있음을 나타냅니다. 즉, 트리가 완벽하게 균형을 이루고 있음을 나타냅니다.

AVL 회전

AVL 트리 자체의 균형을 유지하기 위해 트리에 노드를 삽입하거나 삭제할 때 회전이 수행됩니다.

우리는 다음의 LL 회전, RR 회전, LR 회전, RL 회전을 수행합니다.

  • 왼쪽 – 왼쪽 회전
  • 오른쪽 – 오른쪽 회전
  • 오른쪽 – 왼쪽 회전
  • 왼쪽 – 오른쪽 회전

왼쪽 – 왼쪽 회전

이 회전은 왼쪽 하위 트리의 왼쪽 자식에 새 노드가 삽입될 때 수행됩니다.


AVL 트리 왼쪽 - 왼쪽 회전

AVL 트리 왼쪽 - 왼쪽 회전

단일 오른쪽 회전이 수행됩니다. 이러한 유형의 회전은 노드의 균형 요소가 +2이고 왼쪽 하위 요소의 균형 요소가 +1일 때 식별됩니다.

오른쪽 – 오른쪽 회전

이 회전은 오른쪽 하위 트리의 오른쪽 자식에 새 노드가 삽입될 때 수행됩니다.

AVL 트리 오른쪽 – 오른쪽 회전

단일 왼쪽 회전이 수행됩니다. 이러한 유형의 회전은 노드의 균형 요소가 -2이고 오른쪽 하위 요소의 균형 요소가 -1일 때 식별됩니다.

오른쪽 – 왼쪽 회전

이 회전은 왼쪽 하위 트리의 오른쪽 자식에 새 노드가 삽입될 때 수행됩니다.

AVL 트리 오른쪽 - 왼쪽 회전

이 회전은 노드의 균형 요소가 –2이고 오른쪽 하위 요소의 균형 요소가 +1일 때 수행됩니다.

왼쪽 – 오른쪽 회전

이 회전은 오른쪽 하위 트리의 왼쪽 자식에 새 노드가 삽입될 때 수행됩니다.

AVL 트리 왼쪽 - 오른쪽 회전

이 회전은 노드의 균형 요소가 +2이고 왼쪽 하위 요소의 균형 요소가 -1일 때 수행됩니다.

AVL 트리에 삽입

삽입 연산은 간단한 이진 검색 트리와 거의 같습니다. 삽입할 때마다 트리의 높이를 균형 잡습니다. 삽입 연산은 O(log n) 최악의 시간 복잡도를 갖습니다.


AVL 트리에 삽입

AVL 트리 삽입 구현

1단계: BST와 동일한 삽입 알고리즘을 사용하여 AVL 트리에 노드를 삽입합니다. 위의 예에서는 160을 입력합니다.

2단계: 노드가 추가되면 각 노드의 밸런스 팩터가 업데이트됩니다. 160이 삽입되면 모든 노드의 균형 요소가 업데이트됩니다.

3단계: 이제 균형 요소가 위반되면 균형 요소의 범위를 위반하는 노드가 있는지 확인한 후 아래 사례를 사용하여 회전을 수행합니다. 위의 예에서는 균형 요소 350이 위반되고 거기에 사례 1이 적용 가능해지며 LL 회전을 수행하고 트리가 다시 균형을 이룹니다.

  1. BF(노드) = +2이고 BF(노드 -> 왼쪽 자식) = +1이면 LL 회전을 수행합니다.
  2. BF(노드) = -2이고 BF(노드 -> 오른쪽 자식) = 1이면 RR 회전을 수행합니다.
  3. BF(노드) = -2이고 BF(노드 -> 오른쪽 자식) = +1이면 RL 회전을 수행합니다.
  4. BF(노드) = +2이고 BF(노드 -> 왼쪽 자식) = -1이면 LR 회전을 수행합니다.

AVL 트리의 삭제

삭제도 매우 간단합니다. 단순 이진 검색 트리와 동일한 논리를 사용하여 삭제합니다. 삭제 후에는 균형 잡힌 높이를 유지하기 위해 필요한 경우 트리를 재구성합니다.

1 단계 : 트리에서 요소를 찾으세요.

2 단계 : BST 삭제에 따라 노드를 삭제합니다.

3 단계 : 두 가지 경우가 가능합니다:-

케이스 1 : 오른쪽 하위 트리에서 삭제합니다.

  • 1A. BF(노드) = +2이고 BF(노드 -> 왼쪽 자식) = +1이면 LL 회전을 수행합니다.
  • 1B. BF(노드) = +2이고 BF(노드 -> 왼쪽 자식) = -1이면 LR 회전을 수행합니다.
  • 1C. BF(노드) = +2이고 BF(노드 -> 왼쪽 자식) = 0이면 LL 회전을 수행합니다.

AVL 트리의 삭제

사례 : 왼쪽 하위 트리에서 삭제 중입니다.

  • 2A. BF(노드) = -2이고 BF(노드 -> 오른쪽 자식) = -1이면 RR 회전을 수행합니다.
  • 2B. BF(노드) = -2이고 BF(노드 -> 오른쪽 자식) = +1이면 RL 회전을 수행합니다.
  • 2C. BF(노드) = -2이고 BF(노드 -> 오른쪽 자식) = 0이면 RR 회전을 수행합니다.

AVL 트리의 삭제

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

위 코드의 실행 예:

  1. 위의 코드를 복사하여 “avl.cpp”에 붙여넣으세요.
  2. 코드를 컴파일합니다.
g++ avl.cpp -o run
  1. 코드를 실행합니다.
./run

C++ AVL 트리의 예

AVL 트리의 장점

  • AVL 트리의 높이는 항상 균형을 이룹니다. 높이는 로그 N 이상으로 커지지 않습니다. 여기서 N은 트리의 총 노드 수입니다.
  • 간단한 이진 검색 트리와 비교할 때 더 나은 검색 시간 복잡도를 제공합니다.
  • AVL 트리에는 자체 균형 조정 기능이 있습니다.

요약

  • AVL 트리는 자체 균형 이진 검색 트리입니다.
  • 균형 요소는 AVL 트리의 기본 속성입니다.
  • 노드의 균형 요소는 해당 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 높이 간의 차이로 정의됩니다.
  • 균형 요소의 유효한 값은 -1, 0 및 +1입니다.
  • 삽입 및 삭제 작업은 균형 계수를 위반한 후에 회전을 수행해야 합니다.
  • 삽입, 삭제, 검색 작업의 시간 복잡도는 O(log N)입니다.
  • AVL 트리는 이진 검색 트리의 모든 속성을 따릅니다.
  • 왼쪽 하위 트리에는 루트 노드보다 작은 노드가 있습니다. 오른쪽 하위 트리에는 항상 루트 노드보다 큰 노드가 있습니다.
  • AVL 트리는 삽입이나 삭제 작업에 비해 검색 작업이 더 빈번한 경우에 사용됩니다.