자바스크립트로 구현하는 AVL 트리 클래스

AVL 트리는 이진 탐색 트리(BST)의 단점을 보완한 자가 균형(self-balancing) 트리입니다. 일반적인 이진 탐색 트리는 데이터가 정렬된 순서로 삽입되면 한쪽으로 치우쳐 연결 리스트와 같은 형태가 되고, 검색 성능이 O(N)까지 저하될 수 있습니다. 반면 AVL 트리는 삽입·삭제 시마다 각 노드의 균형 인수(balance factor)를 확인하고, 균형이 깨지면 회전(rotation)을 수행하여 트리의 높이를 항상 O(log N)으로 유지합니다.

다음은 자바스크립트로 작성한 AVL 트리 클래스의 전체 구현 예제입니다.

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 || typeof root === "undefined") {
      height = -1;
    } else {
      height =
        Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
    }
    return height;
  }

  // 새로운 데이터를 트리에 삽입합니다.
  insert(data) {
    const node = new AVLTree.Node(data);
    if (this.root === null) {
      // 트리가 비어 있다면 첫 번째 요소로 삽입합니다.
      this.root = node;
    } else {
      this.root = insertHelper(this, this.root, node);
    }
  }

  // 중위 순회 결과를 콘솔에 출력합니다.
  inOrder() {
    inOrderHelper(this.root);
  }
}

// 트리에서 사용할 노드 클래스
AVLTree.prototype.Node = class {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
};

// 재귀적으로 적절한 위치를 찾아 노드를 삽입하고, 필요하면 회전으로 균형을 복원합니다.
function insertHelper(self, root, node) {
  if (root === null) {
    return node;
  } else if (node.data < root.data) {
    // 왼쪽 서브트리로 이동합니다.
    root.left = insertHelper(self, root.left, node);
    // 균형 인수를 확인하고 알맞은 회전을 수행합니다.
    if (self.getBalanceFactor(root) > 1) {
      if (node.data < root.left.data) {
        root = rotationLL(root);
      } else {
        root = rotationLR(root);
      }
    }
  } else if (node.data > root.data) {
    // 오른쪽 서브트리로 이동합니다.
    root.right = insertHelper(self, root.right, node);
    if (self.getBalanceFactor(root) < -1) {
      if (node.data > root.right.data) {
        root = rotationRR(root);
      } else {
        root = rotationRL(root);
      }
    }
  }
  return root;
}

// 중위 순회: 왼쪽 → 루트 → 오른쪽 순서로 방문합니다.
function inOrderHelper(root) {
  if (root !== null) {
    inOrderHelper(root.left);
    console.log(root.data);
    inOrderHelper(root.right);
  }
}

// LL 케이스: 오른쪽 회전(단일 회전)
function rotationLL(node) {
  const tmp = node.left;
  node.left = tmp.right;
  tmp.right = node;
  return tmp;
}

// RR 케이스: 왼쪽 회전(단일 회전)
function rotationRR(node) {
  const tmp = node.right;
  node.right = tmp.left;
  tmp.left = node;
  return tmp;
}

// LR 케이스: 왼쪽 자식에 좌회전 후, 전체에 우회전(이중 회전)
function rotationLR(node) {
  node.left = rotationRR(node.left);
  return rotationLL(node);
}

// RL 케이스: 오른쪽 자식에 우회전 후, 전체에 좌회전(이중 회전)
function rotationRL(node) {
  node.right = rotationLL(node.right);
  return rotationRR(node);
}

핵심 구성 요소 살펴보기

1. 생성자와 노드 클래스

생성자는 트리가 처음 만들어질 때 루트 노드를 null로 초기화합니다. 노드 클래스는 저장할 데이터(data)와 두 개의 자식 참조(left, right)를 가지며, AVLTree.prototype.Node에 할당하여 클래스의 내부 구성 요소처럼 사용합니다.

2. 높이와 균형 인수 계산

getHeight()는 빈 노드면 -1을 반환하고, 그렇지 않으면 양쪽 자식 높이 중 큰 값에 1을 더해 반환합니다. getBalanceFactor()는 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를 뺀 값으로, 이 값의 절댓값이 1보다 크면 해당 노드에서 균형이 깨진 것으로 판단합니다.

3. 삽입(insert) 로직

삽입은 이진 탐색 트리의 기본 규칙(작은 값은 왼쪽, 큰 값은 오른쪽)을 따라 재귀적으로 위치를 찾습니다. 노드가 삽입된 후에는 호출 스택을 거슬러 올라오며 경로상의 각 노드에 대해 균형 인수를 다시 확인하고, 균형이 무너졌다면 즉시 회전으로 복원합니다.

4. 네 가지 회전 함수

LL 케이스: 왼쪽 자식의 왼쪽에 삽입되어 발생 → 단일 오른쪽 회전
RR 케이스: 오른쪽 자식의 오른쪽에 삽입되어 발생 → 단일 왼쪽 회전
LR 케이스: 왼쪽 자식의 오른쪽에 삽입되어 발생 → 좌회전 후 우회전(이중 회전)
RL 케이스: 오른쪽 자식의 왼쪽에 삽입되어 발생 → 우회전 후 좌회전(이중 회전)

5. 중위 순회(inOrder)

중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 노드를 방문하므로, 트리에 저장된 모든 데이터를 오름차순으로 출력할 수 있습니다.

사용 예시

const tree = new AVLTree();

[10, 20, 30, 40, 50, 25].forEach((data) => tree.insert(data));

tree.inOrder();
// 출력: 10 20 25 30 40 50

만약 일반 이진 탐색 트리였다면 10, 20, 30, 40, 50이 순서대로 삽입될 때 트리가 오른쪽으로 길게 치우쳤을 것입니다. 하지만 AVL 트리는 삽입 과정마다 회전을 수행해 스스로 균형을 잡기 때문에, 어떤 순서로 데이터를 넣어도 항상 낮은 높이를 유지하며 안정적인 O(log N) 검색 성능을 보장합니다.

자바스크립트로 구현하는 AVL 트리 클래스 – 완전한 코드와 상세 해설