[자료구조](14)[이진트리의 구현 3]

 

AVL 트리

앞에서 구현했던 BST의 연산을 이용해 AVL의 self-balancing을 구현하면 된다

 

height

AVL에서 BF 계산을 위해 height를 계산하는 함수

int height(TreeNode* root){
    if (root == NULL){
        return -1; //자식 노드가 없으면 -1로 처리
                   // l, r 모두 -1이 나오고 마지막에 +1해서 결국 -1 반환됨
    }
    int l = height(root->left);
    int r = height(root->right);
    int max_height = (l>r ? l : r);
    return max_height + 1;
}

 

BF

height 기반 Balance Factor 계산
AVL은 BF가 -1, 0, 1이 되게 해야 함

int BF(TreeNode* root){
    if (root == NULL){
        return 0;
    }
    return height(root->left) - height(root->right);
}

 

rotateLL / rotateRR

 

LL 경우를 처리하는 함수

     a                    b
    /                    / \
   b          ->       T2   a
  / \                      /
 T1  T2                   T2

TreeNode* rotateLL(TreeNode* a){
    TreeNode* b = a->left;
    TreeNode* T2 = b->right;
    b->right = a;
    a->left = T2;
    return b;
}
int main(){
    a = rotateLL(a);
}

 

RR 경우를 처리하는 함수

 a                      b
  \                    / \
   b          ->      a   T2
  / \                  \    
T1   T2                 T1

TreeNode* rotateRR(TreeNode* a){
    TreeNode* b = a->right;
    TreeNode* T1 = b->left;
    b->left = a;
    a->right = T1;
    return b;
}
int main(){
    a = rotateRR(a);
}

 

rotateLR / rotateRL

 

LR 경우를 처리하는 함수
LR -> rotateRR로 LL로 바꾸기 -> rotateLL로 처리

     a                   a                b
    /                   /               /   \
   c         ->        b        ->     c     a
  / \                 / \             / \    /
 T1  b               c   T3          T1 T2  T3
    / \             / \
   T2  T3          T1 T2

TreeNode* rotateLR(TreeNode* a) {
    a->left = rotateRR(a->left);  // RR
    return rotateLL(a);           // LL
}
int main(){
    a = rotateLR(a);
}

 

RL 경우를 처리하는 함수
RL -> rotateLL로 RR로 바꾸기 -> rotateRR로 처리

     a                   a                    b
      \                   \                 /   \
       c         ->        b        ->     a     c
      / \                 / \               \   / \
     b   T1              T2  c              T2 T3 T1
    / \                     / \
   T2  T3                  T3 T1

TreeNode* rotateLR(TreeNode* a) {
    a->left = rotateLL(a->left);  // LL
    return rotateRR(a);           // RR
}
int main(){
    a = rotateRL(a);
}

 

insertAVL

BF, rotate로 삽입할 때마다 균형을 잡음

TreeNode* insertAVL(TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertAVL(root->left, data);
    }
    else if (data > root->data) {
        root->right = insertAVL(root->right, data);
    }
    else {
        return root;
    }

    int balance = BF(root);

    if (balance > 1 && data < root->left->data)  // LL
        return rotateLL(root);
    if (balance < -1 && data > root->right->data) // RR
        return rotateRR(root);
    if (balance > 1 && data > root->left->data) { // LR
        root->left = rotateRR(root->left);
        return rotateLL(root);
    }
    if (balance < -1 && data < root->right->data) { // RL
        root->right = rotateLL(root->right);
        return rotateRR(root);
    }

    return root;
}