11. AVL tree

 

 

 

AVL tree

모든 BST 연산은 $ O(d) $ (d는 트리의 높이) 이다.

$ d = \lfloor \log_2 N \rfloor $ (N은 트리의 총 노드 갯수)

• best case: $ O(\log N) $
• worst case: $ O(N) $

 

여기서 차이가 나는 이유는 트리의 균형의 문제이다.

 

BST의 균형을 맞추기 위해 고안된 알고리즘이 많다.

• AVL tree: Adelson-Velskii and Landis (AVL) trees (height-balanced trees)
• Weight-balanced trees
• Red-black trees
• Splay trees and other self-adjusting trees
• B-trees and other (e.g. 2-4 trees) multiway search trees

 

AVL 트리란?

Height-balanced binary search trees

즉, 모든 노드에 대해 왼쪽 및 오른쪽 하위 트리의 높이가 1 이하인 BST이다.

 

 

 

$ height \ of \ node = h \\ balance \ factor = h_{left} - h_{right} \\ empty \ height = -1 $

 

구조

 

각 노드는 위와 같은 구조를 갖고 balance 변수의 절댓값이 1을 초과하는 순간 balancing을 실행하게 된다.

 

Balancing

 

대부분 노드를 새로 추가할 때 균형이 깨지면서 balancing이 필요하다.

• 일부 노드의 경우 균형 계수가 2 또는 -2가 될 수 있습니다.
• Insert 후 노드별로 루트 노드로 돌아가서 높이를 업데이트합니다.
• 새로운 균형 계수 ($ h_{left} - h_{right} $ 차이)가 2 또는 -2인 경우 노드를 중심으로 회전하여 트리를 조정합니다.

 

i. LL rotation

Example) 7, 8을 추가했을 때

node 9를 기준으로 높이차이 (balance factor) 가 2가 나버린다.

 

 

 

 

번호가 매겨진 원: 재조정 중인 노드를 나타냅니다.
글자가 있는 삼각형: 그 자체가 균형 AVL 트리인 하위 트리를 나타냅니다.
노드 옆의 숫자: 가능한 균형 요소를 나타냅니다. (괄호 안은 삭제 시에만 발생).

 

 

ii. RR rotation

노드 10, 11을 추가 했을 때

 

 

iii. RL rotation: LL + RR

 

노드 34 추가

 

 

Balance factor가 30에서 -2로 무너진다. 따라서 30부터 오른쪽 (R) 자식 인 40, 40의 왼쪽 (L) 자식인 35에 34에 삽입되었으므로 RL rotation라고 부른다.

 

 

 

 

 

 

 

 

 

 

iv. LR rotation: RR + LL

그림추가

 

 

 

 

 

종합하자면, 재조정이 필요한 노드를 a라고 할 때 4가지 경우가 있습니다.

 

외부 케이스(1회전 필요):

1. a의 왼쪽 자식의 왼쪽 하위 트리에 삽입. (LL)
2. a의 오른쪽 자식의 오른쪽 서브트리에 삽입. (RR)

 

내부 케이스(이중 회전 필요):

1. a의 왼쪽 자식의 오른쪽 서브트리에 삽입. (LR)
2. a의 오른쪽 자식의 왼쪽 하위 트리에 삽입. (RL)

 

재조정은 4개의 개별 회전 알고리즘을 통해 수행됩니다.

 

 

구현

struct node {
  int balance;
  int key;
  node left, right;
} node;


int getHeight(node node) {
  if (node == NULL) return 0;
  int left = leftHeight (node->left);
  int right = rightHeight (node->right);
  return (left > right) ? left + 1 : right + 1;
}

int balanceFactor (node node) {
  if (node == NULL) return 0;
  int left = leftHeight (node->left);
  int right = rightHeight (node->right);
  return left - right;
}

node rotateLL (node A) {
  node B = ;
  A->left = ;
  B->right = ;
  return ;
}

node rotateRR (node A) {
  node B = ;
  A->left = ;
  B->right = ;
  return ;
}


node rotataLR (node A) { // RR and LL 
  node B = ;
  A->left = rotateRR( );
  return rotateLL ( );
  
}

node rotateRL (node A) { // LL and RR
  node B = A->right;
  A->right = rotateLL( );
  return rotateRR( ) ;
}


node rebalance (node node) {
  int bf = balanceFactor(node);
  
  if (bf >=2) {
    if (balanceFactor(node->left) >= 1) node = rotateLL(node); // LL, outside case
    else node = rotateLR(node); 	// LR, inside case
  }
  
  else if (bf <= -2) {
    if (balanceFactor(node->right) <= -1) node = rotateRR(node);
    else node = rotateRL(node);
  }
  
  return node;
}

 

 

트리의 높이와 시간복잡도

$ N(h) $: h의 높이를 가진 AVL 트리의 최소 노드 갯수

• $ N(0) = 1, \ \ N(1) = 2 $
• $ N(h) = N(h-1)+N(h-2) + 1 $
• $ N(h) \geq \phi^h (\phi \approx 1.62 ) $

 

$ n \geq N(h) \\ n \geq \phi^h \\ \log_{\phi} n \geq h \\ h \leq 1.44\log_2n $

따라서 검색은 $ O(\log n) $ 시간 안에 가능하다.