[자료구조] AVL Tree

1. AVL Tree란?

AVL Tree: 균형 이진 탐색 트리

• 모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1이하이다.
• 높이: log(n) (n: 트리의 노드 수)
  

대부분의 이진탐색트리 연산의 시간 복잡도는 O(h)이다. (h: 트리의 높이)
한쪽으로 치우쳐진 편향이진트리가 되면 높이가 높아져 시간 복잡도도 높아진다. 그러므로 시간 복잡도를 줄이기 위해서 AVL Tree를 이용한다.

2. 트리의 re-balance

이진 탐색 트리에 노드를 삽입하는 경우, 트리가 불균형 상태로 변할 수 있다. 이 트리를 다시 균형있게 만들기 위해 회전을 이용한다.

회전을 시켜도 key(A) < key(x) < key(B) < key(y) < key(C)이므로 이진탐색트리(BST)의 속성을 따른다.

1. Left Left Case

y는 z의 왼쪽 자식이고, x는 y의 왼쪽 자식인 경우

z를 루트 노드로 오른쪽 회전한다.
key(A) < key(x) < key(B) < key(y) < key(C) < key(z) < key(D)

2. Left Right Case

y는 z의 왼쪽 자식이고, x는 y의 오른쪽 자식인 경우

y를 루트 노드로 왼쪽 회전 하고, z를 루트 노드로 오른쪽 회전한다.
key(A) < key(y) < key(B) < key(x) < key(C) < key(z) < key(D)

3. Right Right Case

y는 z의 오른쪽 자식이고, x는 y의 오른쪽 자식인 경우

z를 루트 노드로 왼쪽 회전한다.
key(A) < key(z) < key(B) < key(y) < key(C) < key(x) < key(D)

4. Right Left Case

y는 z의 오른쪽 자식이고, x는 y의 왼쪽 자식인 경우

y를 루트 노드로 오른쪽 회전 하고, z를 루트 노드로 왼쪽 회전한다.
key(A) < key(z) < key(B) < key(x) < key(C) < key(y) < key(D)

3. AVL Tree 구현

struct node {
  int key;
  struct node *left, *right;
  int height;
};

int max(int a, int b) {
  return (a > b)? a : b;
}

struct node* newNode(int key) {
  struct node *temp = (struct *node)malloc(sizeof(struct node));

  temp->data = key;
  temp->left = NULL;
  temp->right = NULL;
  temp->height = 1;
  return temp;
}

struct node *leftRotate (struct node *z) {
  struct node *y = z->right;
  struct node *T2 = y->left;

// left 회전
  y->left = z;
  z->right = T2;

  z->height = 1 + max(z->left->height, z->right->height);
  y->height = 1 + max(y->left->height, y->right->height);

  return y;
}


struct node *rightRotate (struct node *z) {
  struct node *y = z->left;
  struct node *T2 = y->right;

// right 회전
  y->right = z;
  z->left = T2;

  z->height = 1 + max(z->left->height, z->right->height);
  y->height = 1 + max(y->left->height, y->right->height);

  return y;
}


int getBalanceFactor(struct node *n) {
  if (n == NULL)
    return 0;
  return n->left->height - n->right->height;
}

struct node* rebalance(struct node* root) {
  
  int bFactor = getBalanceFactor(root);
  
  // LL 회전
  if (bFactor > 1 && key < node->left->key)
    return rightRotate(root);
    
  // RR 회전
  if (bFactor < -1 && key > node->right->key)
    return leftRotate(root);
    
  // LR 회전
  if (bFactor > 1 && key > node->left->key){
    root->left = leftRotate(root->left);
    return rightRotate(root);
  }
  
  // RL 회전
  if (bFactor < -1 && key < node->right->key){
    root->right = rightRotate(root->right);
    return leftRotate(root);
  }

  return root;
}

// 삽입 함수.
struct node* insert(struct node* root, int key) {

  if (root == NULL)
    return newNode(key);
  if (key > root->data)
    root->right = insert(root->right, key);
  else if (key < root->data)
    root->left = insert(root->left, key);
  else
    return root;

  root->height = 1 + max(node->left->height, node->right->height);
  root = rebalance(root);
  return root;
}

4. Rank 구현

Rank: 각 노드를 루트로 하는 서브트리의 높이

Make-Set(x) { 
    p[x] <- x;
    rank[x] <- 0;

Union(x,y) { 
    x' <- Find-Set(x);
    y' <- Find-Set(y);
    if ( rank[x'] > rank[y'])
    	then p[y'] <- x';
    else {
        p[x'] <- y;
        if (rank[x'] = rank[y'])
            then rank[y'] <- rank[y'] + 1;
    }
 }
 
 Find-Set(x) { 
    if (p[x] != x ) then p[x] <- Find-Set(p[x]);
    return p[x];
}

5. [예제]

LeetCode 110. Balanced Binary Tree

def isBalanced(self, root):
    def check(root):
        if not root:
            return 0
        
        left = check(root.left)
        right = chech(root.right)
       
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1
    
    return check(root) != -1