AVL tree란 무엇인가?

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

우리는 이전에 bst dictionary에서 lookup, insert 그리고 find_min이 O(log n)의 cost를 가진다는 걸 확인했었다.

하지만 모든 종류의 BST에서 전부 O(log n)cost를 가질까?

 

empty BST에 아래와 같은 insertions을 진행한다고 해보자

insert 10
insert 20
insert 30 
insert 40
insert 50
insert 60

60까지 넣고 나면 아래와 같이 tree가 형성된다.

이 tree에서 70을 lookup 하려면 모든 node를 체크해야하기에 O(n)의 cost가 필요하다.

이를 통해 우리는 O(log n) 이 항상 보장되지 않음을 확인했다. 

 

결국 lookup의 cost는 treer가 얼마나 아래로 깊이 갈 수 있냐에 따라서 결정되는 것이다. 

-만약 key가 tree안에 있다면 worst-case는 leaf node까지 내려가는 것이다.

-만약 tree안에 없다면 이 역시 leaf node까지 확인해봐야 한다.

 

Root부터 leaf까지의 가장 긴 길로 연결된 노드의 개수들을 height라고 부른다. 

따라서 height h 를 가진 tree 의 lookup은 항상 O(h)의 시간 복잡도를 가진다. 

단 이때 h는 O(n) 혹은 O(log n)가 될 수 있다. 

 

수학적으로 이 height를 정의하자면

height(EMPTY) = 0

height(Non empty) = 1 + max (height (left subtree) + height(right subtree))

 

Balanced Trees

우리는 tree의 height가 O(log n)보다 작다면 balanced하다고 말한다. 

balanced tree라면 lookup, insert 그리고 find_min 모두 O(log n)의 cost를 가진다.

 

우리가 새로운 node를 추가해도 tree가 balanced 되길 원한다.

이러한 특징을 가진 tree를 우리는 self-balancing이라고 부른다. 

 

우리는 self-balancing trees에 대해 아래와 같이 체크할 수 있다.

1) height∈O(log n)

2) tree를 유지하는 cost가 크지 않다.

 

우리는 이러한 self-balancing trees 중 AVL trees 를 살펴보고자 한다. 

 

AVL Trees

self-balancing tree로써 체크하기 위해 우리는 아래와 같은 heigh invariant를 확인할 수 있다.

"모든 node별로 left subtree와 right subtree의 height가 최대 1만큼 차이난다."

이 height invariant를 유지하기 위해서 3가지 가능성이 존재한다.

1)right subtree의 height가 left subtree의 height보다 1만큼 큰 경우

2) right subtree의 height와 left subtree의 height가 같은 경우

3) right subtree의 height가 left subtree의 height보다 1만큼 작은 경우

 

AVL tree example)

위 사진은 invariant를 만족하는 AVL tree이다. 

 

하지만

위 tree는 AVL tree가 아니다

-> Node 15에서 violation이 발생한다(왼쪽 subtree는 height가 0이고 오른쪽 subtree는 height가 2이다)

 

Rotation

BST에 새롭게 node를 insert할 경우 height invariant이 유지되지 않을 수도 있다.

-> 가장 lowest violation이 발생하는 곳에서 이를 fix해야 한다. 

예시를 하나 살펴보자

20을 넣으면서 node 10에서 violation이 발생하고 이에 따라 그 시점에서 fix가 필요하다

만약 이게 더 큰 사이즈의 tree였다면

이제 fix에 사용되는 다양한 rotation을 알아보자

 

Left Rotation

위처럼 C위치에 있는 subtree가 insertion이후 너무 길어졌을 때 left rotation을 진행한다

 

Right rotation

위의 left rotation의 symmetric한 상황이 right rotation이다. 

A 위치에 있는 subtree가 갑자기 커질 경우 right rotation을 진행한다.

 

두 rotations을 single rotation이라고 부른다. (Cost: O(1))

만약 lowest violation이 tree의 root에서 발생했고 가장 outer subtree 중 하나가 너무 커졌을 때 single rotation을 진행한다. 

 

Double rotations

1) Right-left double rotation

y root를 기준으로 subtree B, C가 insertion이후 커지면 double rotation을 진행한다. 

 

2) Left-right double rotation

위의 기준으로 symmetric한 rotation이 left-right double rotation이다. 

y root를 기준으로 subtree B, C가 insertion이후 커지면 double rotation을 진행한다. 

 

우리는 이러한 double rotation을

1) lowest violation이 root에서 발생하고 2) 안쪽 inner subtrees가 커졌을 때 진행한다

 

왜 이름이 double rotation인가?

- double rotation은 두가지 single rotation의 sequence로 볼 수 있기 때문이다.

 

rotation이 필요한 때를 총정리하면 아래와 같이 정리할 수 있다.

Insertion into an AVL Tree

height h를 가진 tree에 새로운 node를 insert할때 두 가지 경우가 생길 수 있다.

1) height violation

2) no violation

 

violation이 일어난다고 가정하고 이것을 fix하는 상황에서의 height의 변화를 알아보자

 

1) right subtree에 insertion을 해서 violation이 발생한다면

T_R height: h

T_L height: h-2

 

right subtree안에 있는 subtree를 살펴보면 

새로운 insertion이 이 중 left에 들어가거나 right에 들어가거나 둘 중 하나의 경우가 된다. 

 

1) right-right tree에 insertion이 발생했다면 

Ti 와 To는 h-2의 height를 가진다. 

이에 따라 우리는 left rotation을 해야 하는 상황을 확인할 수 있다.

right-left subtree에 insertion을 해도 같은 상황을 확인할 수 있다. 

 

AVL dictionary implementation

위에서 살펴봤던 AVL tree의 invariant에 따라서 우리는 이를 dictionary에도 적용해야 한다.

구체적으로

1) height invariant 를 고려한다

2) insert에는 rotation이 포함되어야 한다

3) lookup 과 find_min 함수는 그대로 유지된다.

 

 

avl_lookup

-이전 bst tree에서 보았던 lookup 함수와 동일하다. 

entry avl_lookup(tree* T, key k)
//@ requires is_avl(T);
//@ ensures \result==NULL || key_compare(entry_key(\result), k)==0;
{
  if (T==NULL) return NULL;
  
  int cmp = key_compare(k, entry_key(T->data));
  if (cmp==0) return T->data;
  if (cmp <0) return avl_lookup(T->left, k);
  //@assert cmp >0;
  return avl_lookup(T->right, k);
}

cost: O(log n)

find_min function도 마찬가지이다.

 

avl_insert

tree* avl_insert(tree*T, entry e)
//@ requires is_avl(T) && e!=NULL;
//@ ensures is_avl(\result) && \result != NULL;
//@ ensures avl_lookup(\result, entry_key(e))==e;
{
  //code for empty tree
  if (T==NULL) return leaf(e);
  
  //code for non-empty tree
  int cmp = key_compare(entry_key(e), entry_key(T->data));
  if (cmp==0) T->data = e;
  else if (cmp <0){
     T->left = avl_insert(T->left, e);
     T = rebalance_left(T);
  else{ //@assert cmp > 0;
     T->right = avl_insert(T->right,e);
     T = rebalance_right(T);
  }
  return T;
}

매 recursive call이 발생할때마다 우리는 tree를 rebalance한다.

->이를 통해 우리는 lowest violation을 fix할 수 있다.

cost: O(log n)

(rebalance cost : O(1))

 

그렇다면 rebalance right/left는 어떻게 구현될까?

tree* rebalance_right(tree* T)
//@ requires T !=NULL && T->right != NULL;
{
  if (height(T->right)-height(T->left)==2){
    if (height(T->right->right) > height(T->right->left)){ //outer right subtree
       T = rotate_left(T); //single rotation
    }else{
      //@assert (T->right->left) > (T->right->right); //inner subtree
      T->right = rotate_right(T->right); //double rotation
      T = rotate_left(T);
     }
    }
   return T;
}

cost: O(1)

단 위에서 사용된 height 함수 역시 아래와 같이 구현이 가능하다

int height(tree* T)
//@ requires is_tree(T);
//@ ensures \result >=0;
{
  if (T==NULL) return 0;
  return 1+ max(height(T->right), height(T->left));
}

만약 tree가 n nodes를 가진다면 height(T)는 O(n)의 cost를 가진다. 

더 적은 복잡도를 가질순없을까?

 

방법은 height field를 struct에 포함시키는 것이다

typedef struct tree_node tree;
struct tree_node{
   tree* left;
   int data;
   tree* right;
   int height;
};

이럴 경우 height 함수가 그저 height field를 return하면 된다

int height(tree* T)
//@ requires is_tree(T);
//@ ensures \result >=0;
{
   return T==NULL ? 0 : T->height;
}

이에 따라 rotation function도 바뀔 수 있다.

void fix_height(tree* T)
//@requires is_tree(T) && T!=NULL;
{
  int hl = height(T->left);
  int hr = height(T->right);
  T->height = 1+ max(hl, hr);
}

tree* rotate_left(tree* T)
//@requires T!=NULL && T->right != NULL;
{
  tree* tmp = T->right;
  T->right =T->right->left;
  tmp ->left = T;
  fix_height(T);
  fix_height(tmp);
  return tmp;
}

rebalance function도 이에 따라 수정한다

tree* rebalance_right(tree* T)
//@ requires T !=NULL && T->right != NULL;
{
  if (height(T->right)-height(T->left)==2){
    if (height(T->right->right) > height(T->right->left)){ //outer right subtree
       T = rotate_left(T); //single rotation
    }else{
      //@assert (T->right->left) > (T->right->right); //inner subtree
      T->right = rotate_right(T->right); //double rotation
      T = rotate_left(T);
     }
   }else{
     fix_height(T); //rotation이 없어도 height를 fix한다.
   }return T;
}

새로운 leaf 를 형성할때도 height field를 설정해야한다

tree* leaf(entry e)
//@requires e!=NULL;
//@ensures is_avl(\result) && \result != NULL;
{
  tree* T = alloc(tree);
  T->data = e;
  T->left = NULL;
  T->right = NULL;
  T->height = 1;
  return T;
}

Representation invariant

위에서 구성한 각 함수들에서 height invariant가 유지되고 있는지도 확인할 필요가 있다.

tree* avl_insert(tree*T, entry e)
//@ requires is_avl(T) && e!=NULL;
//@ ensures is_avl(\result) && \result != NULL;
//@ ensures avl_lookup(\result, entry_key(e))==e;
{
  //code for empty tree
  if (T==NULL) return leaf(e);
  
  //code for non-empty tree
  //@assert is_avl(T->left) && is_avl(T->right);
  int cmp = key_compare(entry_key(e), entry_key(T->data));
  if (cmp==0) T->data = e;
  else if (cmp <0){
     T->left = avl_insert(T->left, e);
     //@assert is_avl(T->left) && is_avl(T->right);
     T = rebalance_left(T);
     //@assert is_avl(T);
  else{ //@assert cmp > 0;
     T->right = avl_insert(T->right,e);
     //@assert is_avl(T->left) && is_avl(T->right);
     T = rebalance_right(T);
     //@assert is_avl(T);
  }
  return T;
}

tree* rebalance_right(tree* T)
//@ requires T !=NULL && T->right != NULL;
//@ requires is_avl(T) && is_avl(T->right);
//@ ensures is_avl(\result);
{
  if (height(T->right)-height(T->left)==2){
    if (height(T->right->right) > height(T->right->left)){ //outer right subtree
       T = rotate_left(T); //single rotation
    }else{
      //@assert (T->right->left) > (T->right->right); //inner subtree
      T->right = rotate_right(T->right); //double rotation
      T = rotate_left(T);
     }
   }else{
     fix_height(T); //rotation이 없어도 height를 fix한다.
   }return T;
}