자바스크립트 AVL 트리에서 균형 계수(Balance Factor) 계산 방법

AVL 트리는 왼쪽 서브트리와 오른쪽 서브트리의 높이를 확인하고, 두 높이의 차이가 1을 초과하지 않도록 보장하는 자가 균형 이진 탐색 트리입니다. 이때 두 서브트리 높이의 차이를 균형 계수(Balance Factor)라고 부릅니다.

예를 들어 아래 세 개의 트리를 살펴보면, 첫 번째 트리는 균형이 잡혀 있지만 나머지 두 트리는 균형이 깨져 있는 상태입니다.

균형 계수의 이해

두 번째 트리에서는 노드 C의 왼쪽 서브트리 높이가 2이고 오른쪽 서브트리 높이가 0이므로 차이가 2가 됩니다. 세 번째 트리에서는 노드 A의 오른쪽 서브트리 높이가 2이고 왼쪽 서브트리가 존재하지 않아 높이가 0이므로, 역시 차이가 2가 됩니다.

AVL 트리는 이러한 차이(균형 계수)가 1까지만 허용됩니다. 만약 그 값이 1을 초과하면 해당 트리는 더 이상 AVL 트리의 조건을 만족하지 않습니다.

BalanceFactor = height(left-subtree) − height(right-subtree)

왼쪽과 오른쪽 서브트리의 높이 차이가 1보다 크다면, 회전(rotation) 기법을 사용해 트리의 균형을 다시 맞추게 됩니다.

자바스크립트 구현 예제

이제 균형 계수를 계산하는 메서드를 정의하고, AVL 트리 클래스를 초기화해 보겠습니다.

class AVLTree {
   constructor() {
      // 루트 요소를 null로 초기화합니다.
      this.root = null;
   }
   getBalanceFactor(root) {
      return this.getHeight(root.left) - this.getHeight(root.right);
   }
   getHeight(root) {
      let height = 0;
      if (root === null) {
         height = -1;
      } else {
         height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
      }
      return height;
   }
}
AVLTree.prototype.Node = class {
   constructor(data, left = null, right = null) {
      this.data = data;
      this.left = left;
      this.right = right;
   }
};

코드 설명

getHeight 메서드는 재귀적으로 호출되며, 노드가 null일 경우 -1을 반환합니다. 빈 트리의 높이를 -1로 정의하면 리프 노드의 높이가 0이 되어 균형 계수 계산이 자연스럽게 이루어집니다. 노드가 존재한다면 왼쪽과 오른쪽 서브트리 중 더 큰 높이에 1을 더한 값을 반환합니다.

getBalanceFactor 메서드는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값을 반환합니다. 이 값이 -1, 0, 1 범위 안에 있다면 해당 노드를 기준으로 하는 트리는 균형 상태라고 판단할 수 있습니다.