JavaScript AVL 트리: 높이 불변식과 LL·RR·LR·RL 삽입 회전

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

문제 상황과 API 계약

일반 BST에 10,20,30,40을 순서대로 넣으면 오른쪽으로만 이어져 검색이 선형 시간이 될 수 있습니다. AVL은 순서 불변식에 높이 조건을 추가해 이런 편향을 막습니다. 키가 순서대로 들어올 수 있고 매번 특정 값 이상인 가장 작은 키를 찾아야 한다면 정렬되지 않은 Map만으로는 답하기 어렵습니다.

이 구현은 안전한 정수 키를 저장하는 집합입니다. 중복 키는 추가하지 않고 add는 새 키가 들어갔을 때만 true를 반환합니다. has는 포함 여부, ceiling(x)는 x 이상인 최소 키 또는 null, toArray는 오름차순 배열을 반환합니다. 삭제·키별 값 저장·동일 키의 빈도 카운터는 구현하지 않습니다.

높이는 빈 자식 0, 잎 1로 정의합니다. 다른 자료의 빈 트리 높이 −1 규칙과 섞으면 회전 기준이 어긋납니다. 노드와 root는 설명을 위해 외부에서 볼 수 있지만 직접 수정하지 않아야 하며, 내부 insert와 회전 메서드는 공개 입력 검증용 API가 아닙니다.

정확성을 지키는 불변식

모든 노드에서 왼쪽 키는 node.key보다 작고 오른쪽 키는 큽니다. 중복은 새 노드로 만들지 않으므로 엄격한 부등호를 쓸 수 있습니다. 동시에 node.height는 1+max(왼쪽 높이,오른쪽 높이)이고, 균형 인수 balance=왼쪽 높이−오른쪽 높이는 −1,0,1이어야 합니다.

삽입은 먼저 일반 BST와 같은 한 경로를 내려갑니다. 재귀가 돌아올 때 그 경로의 높이를 다시 계산하고 균형을 고칩니다. 회전은 중위 순서를 바꾸지 않고 부모·자식 관계만 재배치합니다. 오른쪽 회전에서 x.right였던 middle은 y.left로 옮겨야 모든 키가 x< middle <y 순서를 보존합니다.

높이 h의 AVL이 가질 수 있는 최소 노드 수는 N(h)=1+N(h−1)+N(h−2)입니다. 높이 차이를 최대 1까지 허용하는 가장 작은 트리를 세는 식입니다. 이 수는 높이에 대해 지수적으로 증가하므로 n개 노드의 높이는 O(log n)입니다. 따라서 최악 입력 순서에서도 삽입 경로와 조회 경로가 로그 길이를 유지합니다.

전체 구현과 실행

Node.js 24의 CommonJS 환경을 기준으로 합니다. 아래 전체 코드를 avl.cjs로 저장하고 파일이 있는 폴더에서 node avl.cjs를 실행하세요. 외부 패키지는 필요하지 않습니다. module.exports는 다른 파일에서 가져올 때 사용하며 require.main 조건 안의 호출은 직접 실행할 때만 작동합니다.

class AVLSet {
  constructor() {
    this.root = null;
    this.size = 0;
  }
  check(key) {
    if (!Number.isSafeInteger(key)) throw new TypeError('키는 안전한 정수여야 합니다.');
  }
  height(node) { return node?.height ?? 0; }
  update(node) {
    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
  }
  rotateRight(y) {
    const x = y.left, middle = x.right;
    x.right = y;
    y.left = middle;
    this.update(y);
    this.update(x);
    return x;
  }
  rotateLeft(x) {
    const y = x.right, middle = y.left;
    y.left = x;
    x.right = middle;
    this.update(x);
    this.update(y);
    return y;
  }
  add(key) {
    this.check(key);
    const before = this.size;
    this.root = this.insert(this.root, key);
    return this.size !== before;
  }
  insert(node, key) {
    if (!node) {
      this.size++;
      return { key, left: null, right: null, height: 1 };
    }
    if (key < node.key) node.left = this.insert(node.left, key);
    else if (key > node.key) node.right = this.insert(node.right, key);
    else return node;
    this.update(node);
    const balance = this.height(node.left) - this.height(node.right);
    if (balance > 1) {
      if (key > node.left.key) node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }
    if (balance < -1) {
      if (key < node.right.key) node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }
    return node;
  }
  has(key) {
    this.check(key);
    let node = this.root;
    while (node) {
      if (key === node.key) return true;
      node = key < node.key ? node.left : node.right;
    }
    return false;
  }
  ceiling(key) {
    this.check(key);
    let node = this.root, candidate = null;
    while (node) {
      if (node.key >= key) {
        candidate = node.key;
        node = node.left;
      } else node = node.right;
    }
    return candidate;
  }
  toArray() {
    const result = [];
    const visit = (node) => {
      if (!node) return;
      visit(node.left);
      result.push(node.key);
      visit(node.right);
    };
    visit(this.root);
    return result;
  }
}

module.exports = { AVLSet };

if (require.main === module) {
  const t = new AVLSet();
  [30, 10, 20, 20].forEach(key => t.add(key));
  console.log(JSON.stringify({ root: t.root.key, sorted: t.toArray(), ceiling: t.ceiling(15) }));
}

직접 실행 출력:

{"root":20,"sorted":[10,20,30],"ceiling":20}

rotateRight(y)는 y.left를 새 루트 x로 올립니다. 링크를 바꾼 뒤 아래로 내려간 y의 높이를 먼저 고치고 새 루트 x를 고칩니다. 순서를 반대로 하면 x가 아직 낡은 y.height를 읽습니다. rotateLeft도 같은 이유로 아래 노드부터 갱신합니다.

insert의 balance>1 분기에서 새 key가 node.left.key보다 크면 LR입니다. 먼저 왼쪽 자식을 왼쪽으로 회전해 LL 모양으로 바꾸고 node를 오른쪽으로 회전합니다. balance<−1의 대칭 조건은 RL을 처리합니다. 삽입된 키를 이용한 이 판별은 삽입용이며 삭제에 그대로 재사용하면 안 됩니다.

add가 this.root=this.insert(…)를 수행하는 것은 회전 후 루트가 바뀔 수 있기 때문입니다. 재귀 호출 결과를 node.left 또는 node.right에 다시 대입하는 것도 같은 이유입니다. 회전을 계산만 하고 반환 루트를 연결하지 않으면 새로운 구조가 트리에 반영되지 않습니다.

ceiling은 node.key가 기준 이상이면 후보를 기록하고 더 작은 답이 있을 수 있는 왼쪽으로 갑니다. 기준 미만이면 왼쪽 전체도 작으므로 오른쪽으로 갑니다. 현재 후보보다 더 좋은 가능성이 남은 경로 하나만 따라가므로 정렬 배열을 전부 만들 필요가 없습니다. toArray는 학습용 확인과 결과 나열에만 사용합니다.

상태 변화 따라가기

복잡도와 적용하지 말아야 할 경우

삭제는 없습니다. 삭제 후에는 높이가 줄어 여러 조상에서 다시 균형이 깨질 수 있고, 삽입 키 방향으로 회전을 분류할 수도 없습니다. add 코드의 부등호만 바꿔 delete를 만들지 마세요. 삭제가 필수이면 그 연산까지 검증된 균형 트리 구현을 사용해야 합니다.

숫자가 아닌 키를 지원하려면 일관된 전순서 비교자를 도입해야 합니다. NaN처럼 비교에서 양쪽 모두 false가 되는 값을 허용하면 중복 판정과 검색이 깨집니다. 이 코드는 Number.isSafeInteger로 그런 값을 거부합니다.

모든 키가 한 번에 주어지고 이후 삽입이 없다면 정렬 배열과 이진 탐색이 더 간단합니다. 정확 포함 여부만 필요하면 Set도 대안입니다. AVL은 지속적인 삽입과 순서 질의를 함께 요구할 때 비용을 지불할 가치가 있습니다. 문자열 비교가 긴 경우처럼 비교 자체가 O(1)이 아니면 표의 시간에 비교 비용도 반영해야 합니다.

연습으로 확인하기

번호를 온라인으로 등록하면서 기준 이상의 가장 작은 등록번호를 찾아 보세요. 단순 has와 달리 순서 질의가 균형 BST를 선택하는 이유를 보여 줍니다.

[창작 문제] 기준 이상 등록번호 안내

LeetCode 1382 – Balance a Binary Search Tree — 기존 BST를 균형 트리로 바꾸는 공식 문제입니다. 매 삽입마다 균형을 유지하는 이 AVL 구현과 동일한 과제가 아니므로, 정렬 순회와 재구성 대안을 비교하는 연습으로 사용하세요.

공식 자료

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

• Princeton Algorithms 공식 AVLTreeST 문서
• LeetCode 1382 – Balance a Binary Search Tree