[바미] Tree algorithms - AVL trees 알고리즘.

AVL trees

AVL 트리는 균형 이진 탐색 트리의 일종으로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리를 말합니다.

AVL 트리에서 각 노드의 높이 차이를 재조정하는 연산을 회전(rotation)이라고 하죠.

 

그래서 AVL 트리에서 균형을 유지하기 위해 각 노드의 두 자식 서브트리의 높이 차이(높이 균형 인수)는 -1, 0, 1 중 하나여야 하는데

만약 높이 균형 인수가 이 범위를 벗어난다면 해당 노드를 불균형 상태로 판단하여 회전 연산을 수행해 균형을 유지하게 되죠.

 

코드 구현

AVL 트리의 구현을 위해 다음과 같은 노드 구조체가 필요한데요.

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

AVLNode 클래스는 트리의 노드를 나타내며, value, left, right, height의 4개의 속성을 가지게 됩니다.

 

이제 AVL 트리의 핵심인 회전 연산을 구현해보죠. 

좌우 회전 구현

AVL 트리는 왼쪽으로 삽입하는 경우와 오른쪽으로 삽입하는 경우로 나눌 수 있으므로, 두 가지 경우에 대해 각각 좌우, 우좌 회전을

구현해야 하는데 우선 좌우 회전을 구현해보죠.

// LL 불균형 상태 -> 우회전
function rotateRight(node) {
  let leftChild = node.left;
  node.left = leftChild.right;
  leftChild.right = node;

  node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
  leftChild.height = Math.max(getHeight(leftChild.left), node.height) + 1;

  return leftChild;
}

좌우 회전을 구현한 코드에서 node는 불균형 상태에 있는 노드, leftChild는 node의 왼쪽 자식 노드이에요.

먼저 node의 왼쪽 자식 노드 leftChild의 오른쪽 자식 노드를 node의 왼쪽 자식 노드로 연결해줘요.

그 다음, node를 leftChild의 오른쪽 자식 노드로 연결하고, 마지막으로 node와 leftChild의 높이를 갱신해주는 형태입니다.

참고로 getHeight 함수는 해당 노드의 높이를 반환하는 함수라고 생각하시면 돼요.

우좌 회전 구현

그 다음으로 우좌 회전을 구현할 차례인데요. 우좌 회전은 왼쪽 서브트리의 높이가 오른쪽 서브트리보다 2 이상 큰 경우에 수행하게 되는데 우좌 회전을 하면 기존의 루트 노드는 새로운 서브트리의 루트 노드가 돼요.

 

우좌 회전을 구현하기 위해서는 다음과 같은 단계를 거쳐요.

1. 우좌 회전할 노드의 왼쪽 자식 노드의 오른쪽 서브트리의 높이가 더 높아야 해요.
2. 우좌 회전할 노드의 왼쪽 자식 노드를 새로운 루트 노드로 설정해요.
3. 새로운 루트 노드의 오른쪽 자식 노드를 우좌 회전할 노드의 왼쪽 자식 노드로 설정해요.
4. 우좌 회전할 노드의 왼쪽 자식 노드를 새로운 루트 노드의 오른쪽 자식 노드로 설정해요.

이걸 바탕으로 구현해보도록 하죠.

// 우좌 회전을 수행하는 함수
function rotateRightLeft(node) {
  node.left = rotateLeft(node.left);
  return rotateRight(node);
}

이 함수에서는 먼저 왼쪽 자식 노드를 기준으로 좌측 회전을 수행하게 되는데 그 후, 우측 회전을 수행하면서 새로운 서브트리의 루트

노드를 설정해줘요.

 

좌좌 회전 구현

function rotateLL(node) {
  let leftChild = node.left;
  node.left = leftChild.right;
  leftChild.right = node;
  node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
  leftChild.height = Math.max(getHeight(leftChild.left), node.height) + 1;
  return leftChild;
}

우우 회전 구현

function rotateRR(node) {
  let rightChild = node.right;
  node.right = rightChild.left;
  rightChild.left = node;
  node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
  rightChild.height = Math.max(getHeight(rightChild.right), node.height) + 1;
  return rightChild;
}

좌좌 회전과 우우 회전은 각각 왼쪽-왼쪽 회전과 오른쪽-오른쪽 회전이에요.

코드는 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 중심으로 회전하게 되는데 회전시에는 노드와 해당 자식 노드를 교환하고, 높이를 다시 계산하여 반환해줘요.

---

마무리

이렇게 해서 AVL 트리의 구현을 해보았는데요. AVL 트리는 높이 균형을 유지하기 때문에(높이 균형이 항상 -1, 0, 1 이어야 하기 때문에), 노드를 삽입하거나 삭제할 때마다 균형을 맞추기 위해 회전 연산이 필요해요.

 

AVL 트리에서 노드를 삽입하거나 삭제할 때마다 균형을 맞추기 위해 회전 연산이 수행하는데 이를 통해 AVL 트리는 항상 균형을 유지하며, 트리의 높이를 최소화할 수 있어요.

노드를 삽입할 때는 삽입 위치를 찾은 후, 새로운 노드를 삽입하고, 그 이후 삽입된 노드를 루트까지 거슬러 올라가며 노드의 높이를 업데이트하고, 높이 균형을 맞추기 위한 회전 연산을 수행하죠.

 

회전 연산에는 LL 회전, RR 회전, LR 회전, RL 회전 4가지 종류가 있으며, 각각의 회전 연산은 서로 반대 방향으로 이루어지는데

이러한 회전 연산들을 조합하여 AVL 트리를 구성하죠.

AVL 트리에서 노드를 삽입하거나 삭제할 때마다 균형을 맞추기 위해 회전 연산이 수행하는데 이를 통해 AVL 트리는 항상 균형을 유지하며, 트리의 높이를 최소화할 수 있어요.

따라서 회전 연산은 AVL 트리의 핵심적인 부분이죠.