자료구조, AVL Left-Rotate & Right-Rotate 구현

자료구조, AVL Left-Rotate & Right-Rotate 구현

---

2023.04.02 - [알고리즘] - 자료 구조, Linked List

2023.04.02 - [알고리즘] - 자료구조, Binary Search Tree

---

저번에 Linked List와 BST를 공부하면서 AVL을 가볍게 공부해봤다.

오늘은 AVL에 대해서 공부한 내용을 정리해 보려고 한다.

 

📌 AVL이란?

Adelson-Velsky, Landis

사람 이름(소련, 1964년) 약자로 자가균형트리를 의미한다. 

모든 노드에 대해서 왼쪽부트리와 오른쪽 부트리의 높이차가 1이하인 BST를 의미한다.

 

BST	AVL

차이가 보이는가?

BST는 루트 노드에서 오른쪽 부트리와 왼쪽 부트리의 높이차가 2로, 1이하가 아니므로 AVL이 아니다.

반면 AVL에서는 모든 노드에서 오른쪽 부트리와 왼쪽 부트리의 높이차가 1이하이다.

 

📌 그렇다면, 높이차가 1이하인게 왜 중요할까?

AVL 증명

양쪽 부트리의 높이 차가 1이하면,  O(log N)의 시간복잡도가 보장되기 때문이다.

 

📌 AVL insert/delete

양쪽 부트리의 높이차를 1이하로 유지하기 위해

삽입 삭제 시 single/double 규칙에 따라 rebalancing(재조정)이 필요한다.

rotation 출처 : Chan-Su Shin 자료구조 강의 자료

위 그림과 같이 높이 차가 1보다 커지면, 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄여준다.

rotate는 사실 linked list의 연결을 끊고 정렬 후, 재배치하는 방법이다.

---

📌 Left-Rotate pseudocode

 

Rotate 출처 : CLRS book

left-rotate : 베타 노드는 y의 왼쪽 서브트리임으로 항상 y보다 작다. (β < y)

ritght-rotate : 베타 노드는 x의 오른쪽 서브트리임으로 항상 x보다 크다. (β > x)

Left-Rotate, 출처 : CLRS book

처음에 조금 이해하기 힘들었다.

일단 컴퓨터적인 사고로 수도 코드에 접근해야 한다.

x.right = y.left

컴퓨터 구조를 조금 공부해 본 사람이면 알텐데, 메모리에 접근해 값을 변경할 때는 '=' 우측 변수부터 접근해야 한다.

y.left의 변수 주소에 접근. x.right 변수의 주소값을 할당한다.

값을 바꿔준다고 생각하지만, 사실상 value의 address를 바꿔주는 것이다.

 

이와 같은 식으로 코드를 접근하면 이해가 쉽다.

노드y의 left가 노드 x의 right에 할당된다.

 

이런식으로 이해해야 한다.

또한 노드와 노드를 연결할 경우, 노드x의 오른쪽 자식(right)으로 β를 연결해 줬으면,

노드 β의 부모(parent)로 노드 x를 연결해줘야 한다. 

즉, 양방향 연결을 해줘야 한다.

이러한 개념을 이해 했으면, 다음 코드를 충분히 이해 할 수 있다.

---

📄 rotate_left 함수

void rotate_left(rbtree *t, node_t *p) {
  node_t *right = p->right;
  p->right = right->left;
  if (right->left != t->nil) {
    right->left->parent = p; // right의 부모를 p노드로 지정
  }
  right->parent = p->parent;
  if (p->parent == t->nil) {
    t->root = right;
  } else if (p == p->parent->left) {
    p->parent->left = right;
  } else {
    p->parent->right = right;
  }
  right->left = p;
  p->parent = right;
}

rotate-left 코드 이해

 

---

📄 rotate_right 함수

void rotate_right(rbtree *t, node_t *p) {
  node_t *left = p->left;
  p->left = left->right;
  if (left->right != t->nil) {
    left->right->parent = p; // right의 부모를 p노드로 지정
  }
  left->parent = p->parent;
  if (p->parent == t->nil) {
    t->root = left;
  } else if (p == p->parent->right) {
    p->parent->right = left;
  } else {
    p->parent->left = left;
  }
  left->right = p;
  p->parent = left;
}

---

공부 자료1 : Chan-Su Shin 자료구조-균형이진트리-AVL 트리 정의 https://youtu.be/dHHjrl6m5CE

공부 자료2 : CLRS book (Introduction to Algorithms) 13장 레드 블랙 트리