AVL 트리

AVL 트리란?

스스로 균형을 잡는 이진 탐색 트리

한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 사용

→ 스스로 균형을 잡아 편향을 방지

→ 트리의 높이가 h일때 시간 복잡도는 O(h)

 

AVL트리의 특징

• 이진 트리의 속성을 가진다
• 왼쪽, 오른쪽 서브 트리의 높이 차가 최대 1이다
• 높이 차이가 1보다 커지면 회전을 통해 균형을 잡는다
• 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다

 

Balance Factor(BF)

 

왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값

💡 Balance Factor

    BF(K) = left(K) - right(K)

 

    BF = 1 → 왼쪽 서브트리가 높음

    BF = 0 → 양쪽의 높이가 같음

    BF = -1 → 오른쪽 서브트리가 낮음

 

시간/공간 복잡도

AVL 트리	평균	최악
접근	θ(logN)	O(logN)
탐색	θ(logN)	O(logN)
삽입	θ(logN)	O(logN)
삭제	θ(logN)	O(logN)
공간	θ(N)	O(logN)

 

 

회전

삽입 삭제시 BF의 값이 -1, 0, 1 이 아닌 경우(불균형 상태) 불균형 노드를 기준으로 서브트리의 위치를 변경하는 회전 작업을 수행하여 트리의 균형을 맞춤

 

 

LL(left left) case

• y는 z의 왼쪽 자식 노드
• x는 y의 왼쪽 자식 노드

→ right rotation 수행

1. y노드의 오른쪽 자식 노드를 z노드로 변경
2. z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경

→ y는 새로운 루트 노드

RR(right right) case

• y는 z의 오른쪽 자식 노드
• x는 y의 오른쪽 자식 노드

→ left rotation 실행

1. y노드의 왼쪽 자식 노드를 z로 변경
2. z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경

→ y는 새로운 루트 노드

LR(left right) case

• y는 z의 왼쪽 자식 노드
• x는 y의 오른쪽 자식 노드

→ left right 순으로 두번의 rotation 수행

RL(right left) case

• $y$는 $z$의 오른쪽 자식 노드
• $x$는 $y$의 왼쪽 자식 노드

→ right left 순으로 두번의 rotation 수행

코드

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 *lefttRotate (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);

// 새로운 루트 노드 y를 반환  
  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);

// 새로운 루트 노드 y를 반환  
  return y;
}

// BF(BalanceFactor)값을 가져오는 함수.
int getBalanceFactor(struct node *n) {
  if (n == NULL)
    return 0;
  return n->left->height - n->right->height;
}

// 트리의 높이 균형을 유지하는 함수.
// 4가지 케이스를 가지고 rotate를 수행함.
struct node* rebalance(struct node* root) {
  
  int bFactor = getBalanceFactor(root);
  
  // LL Case
  if (bFactor > 1 && key < node->left->key)
    return rightRotate(root);
  // RR Case
  if (bFactor < -1 && key > node->right->key)
    return leftRotate(root);
  // LR Case
  if (bFactor > 1 && key > node->left->key){
    root->left = leftRotate(root->left);
    return rightRotate(root);
  }
  // RL Case
  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;
}