코딩테스트 JS AVL 트리: 기준 이상 최솟값 찾기

Node.js 24 CommonJS용 전체 풀이입니다. avl-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.

Windows PowerShell:
Get-Content -Raw -Encoding UTF8 .input.json | node .avl-problem.cjs

macOS / Linux:
node avl-problem.cjs < input.json

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;
  }
}

function solve({ ops }) {
  const tree = new AVLSet(), out = [];
  for (const [type, key] of ops) {
    if (type === 'add') tree.add(key);
    else if (type === 'next') out.push(tree.ceiling(key));
    else throw new Error('알 수 없는 작업입니다.');
  }
  return out;
}

module.exports = { solve };

if (require.main === module) {
  const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
  console.log(JSON.stringify(solve(input)));
}

아직 번호가 없을 때 next(15)는 null입니다. 30,10,20 등록은 LR 회전을 만들고 최종 루트가 20이 됩니다. 20을 다시 넣어도 집합은 {10,20,30}입니다. 기준 15의 최소 후보는 20, 기준 30의 후보는 자기 자신 30, 기준 31에는 후보가 없습니다. solve는 등록 시 add, 질의 시 ceiling만 호출하므로 전체 정렬을 반복하지 않습니다.

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

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

q개 작업, 최대로 저장한 서로 다른 키 수 u에 대해 최악 O(q log(u+1)) 시간입니다. 구조 O(u), 삽입 재귀 O(log(u+1)), 반환 결과 O(q) 공간이며 삭제 비용은 포함하지 않습니다.

표본과 경계를 직접 확인하려면 다음 코드를 avl-check.cjs로 저장하고 같은 폴더에서 node avl-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.

const assert = require('node:assert/strict');
const { solve } = require('./avl-problem.cjs');

assert.deepEqual(
  solve({
  "ops": [
    [
      "next",
      15
    ],
    [
      "add",
      30
    ],
    [
      "add",
      10
    ],
    [
      "add",
      20
    ],
    [
      "add",
      20
    ],
    [
      "next",
      15
    ],
    [
      "next",
      30
    ],
    [
      "next",
      31
    ]
  ]
}),
  [null,20,30,null],
);
assert.deepEqual(
  solve({
  "ops": []
}),
  [],
);