AVL tree

정의 : 모든 노드에 대해서 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이차가 1이하는 BST (이진탐색트리)

리프노드의 height=0

균형도 값 = 좌측서브트리의 높이-우측서브트리의 높이.

이게 1보다 커지면 회전을 한다

*아무것도 없는것 : -1로 가정함 ! (NULL=-1)

이 값이 양수 -> 왼쪽 치우침 / 음수 -> 오른쪽 치우침

 

높이 결정법

MAX(좌 서브트리높이, 우서브트리높이) + 1 

(둘중 더 큰 값 + 1 이 높이가 됩니당)

 

LL: 왼쪽으로 치우쳐있으므로 오른쪽으로 회전함

RR: 오른쪽으로 치우쳐 있으므로 왼쪽으로 회전

(이건 반대로 회전)

(얘넨 그대로 회전)

LR : 왼쪽으로 치우쳤는데 왼쪽노드의 오른쪽서브트리가 더 무거울때 함

(왼쪽무겁-의 오른쪽무겁 이라서 LR) < 모양

-> 왼쪽서브노드에 좌회전하고 전체에 우회전함

RL : 오른쪽으로치우쳤는데 오른쪽노드의 왼쪽서브트리가 더 무거울때 (1이라도) > 모양

 

이지하네욤~^^ 아래꺼 예제 마니 해보긩

 

두개가 아래로 더튀어나와잇으면 회전!!!

 

회전할땐 양끝연결

 

 

코드 실습

easy 하네영

 

1. rotate LL (우회전)

- 부모의 왼쪽을 왼쪽자식의 오른쪽노드로 설정

- 왼쪽자식의 오른쪽노드를 부모로 설정

-높이 변경; 부모, 왼쪽자식 각각 두자식중 큰 높이 + 1 를 높이로 설정해줌

-> 왼쪽자식 (child 리턴)

AvlNode* rotateLL(AvlNode* parent){
    AvlNode* child=parent->left;//할당
    
    parent->left=child->right;
    child->right=parent; 
    
    //child의 자식에는 parent가 있으므로 parent의 높이 먼저 설정해야함!!
    // 위 아래 둘다 parent 먼저 !!
    parent->Height=Max(height(parent->left), height(parent->right))+1; //+1까먹지 말깅
    child->height=//얘도 마찬가지
   
    //height 함수는 null일 경우 -1 리턴, 아닐경우 걍 height 리턴해주는 함수 ! null일때 때문에 만들어둠
}

2. rotate RR

-오른쪽 자식 노드 할당

-부모먼저!! 부모의 오른쪽=자식의 왼쪽자식

-자식의 왼쪽=부모

-이제 h변경!! 걍 부모먼저~~ 끗 (이때 +1 잊지말기~~)

AvlNode* child=parent->right;

parent->right=child->left;
child->left=parent;

parent->Height=Max(height(parent->left), height(parent->right))+1;
child->Height=Max(parent->Height, height(child->right))+1;

 

3. rotate LR

- left 자식이 오른쪽으로 기울어져있으므로 RR rotate 시킴

그리고 해당 노드 LL rotate

-> LR이므로 left=RR로테이션, 그리고 LL

(RR->LL)

AvlNode* child=parent->left;
parent->left=rotateRR(child); //RR rotate한걸로 새로 끼워넣기 ^^
return rotateLL(parent);

4. rotate RL

(LL->RR)

AvlNode* child=parent->right;
parent->right=rotateLL(child);
return rotateRR(parent);

5. insert

- root=null이면 루트에 추가

 

- 데이터 값이 루트보다 작으면

 재귀로 left로 계속 간다 (root->left=avlAdd(root->left,data); )

 추가하고 나서는 왼.오 차이가 2-> 두개로 나뉨 .

 데이터가 루트의 왼쪽애보다 작으면 LL(왼쪽에추가된거니까), 아니면 LR (오른쪽에추가된거니까)

 

 

- 데이터 값이 루트보다 크면

  위에의 반대로

 

- root의 height 설정. 왼,오 height중 max인거 후 +1

- return root

 

AvlNode* avlAdd(AvlNode* root, int data){
    if(root==NULL){
        root=(AvlNode*)malloc(sizeof(AvlNode));
        if(root==NULL){
            exit(1);
        }
        root->data=data;
        root->Height=0;
        root->left=root->right=NULL;
    }
    else if(data<root->data){
        root->left = avlAdd(root->left, data);
        //
        if(height(root->left)-height(root->right)==2){
            if(data<root->left->data)
                root=rotateLL(root);
            else
                root=rotateLR(root);
        }
    }
    else if(data>root->data){
        root->right=avlAdd(root->right, data);
        //
        if(height(root->right)-height(root->left)==2){
            if(data>root->right->data)
                root=rotateRR(root);
            else
                root=rotateRL(root);
        }
    }
    else{
        printf("중복 키 삽입 오류\n");
        exit(1);
    }
    root->Height=Max(height(root->left), height(root->right))+1;
    return root;
}