AVL 트리 삭제: 높이 갱신과 연속 균형 복구

별도 패키지는 필요하지 않습니다. Node.js가 처음이라면 브라우저와 Node.js 시작 안내부터 확인하세요.

algorithm-avl-tree-deletion.mjs 파일을 만들고 아래 전체 코드를 저장합니다.

function requireKey(key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}
class AVLNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.height = 1;
    this.size = 1;
  }
}
function height(node) { return node ? node.height : 0; }
function sizeOf(node) { return node ? node.size : 0; }
function refresh(node) {
  node.height = 1 + Math.max(height(node.left), height(node.right));
  node.size = 1 + sizeOf(node.left) + sizeOf(node.right);
  return node;
}
function balanceFactor(node) { return height(node.left) - height(node.right); }
function rotateLeft(node) {
  const top = node.right;
  node.right = top.left;
  top.left = node;
  refresh(node);
  return refresh(top);
}
function rotateRight(node) {
  const top = node.left;
  node.left = top.right;
  top.right = node;
  refresh(node);
  return refresh(top);
}
function rebalance(node) {
  refresh(node);
  if (balanceFactor(node) > 1) {
    if (balanceFactor(node.left) < 0) node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  if (balanceFactor(node) < -1) {
    if (balanceFactor(node.right) > 0) node.right = rotateRight(node.right);
    return rotateLeft(node);
  }
  return node;
}
function insertNode(node, key) {
  if (!node) return new AVLNode(key);
  if (key < node.key) node.left = insertNode(node.left, key);
  else if (key > node.key) node.right = insertNode(node.right, key);
  else return node;
  return rebalance(node);
}
function removeNode(node, key) {
  if (!node) return null;
  if (key < node.key) node.left = removeNode(node.left, key);
  else if (key > node.key) node.right = removeNode(node.right, key);
  else {
    if (!node.left) return node.right;
    if (!node.right) return node.left;
    let successor = node.right;
    while (successor.left) successor = successor.left;
    node.key = successor.key;
    node.right = removeNode(node.right, successor.key);
  }
  return rebalance(node);
}
class AVLTree {
  constructor() { this.root = null; }
  get size() { return sizeOf(this.root); }
  has(key) {
    requireKey(key);
    let node = this.root;
    while (node) {
      if (key === node.key) return true;
      node = key < node.key ? node.left : node.right;
    }
    return false;
  }
  insert(key) {
    requireKey(key);
    const before = this.size;
    this.root = insertNode(this.root, key);
    return this.size !== before;
  }
  remove(key) {
    requireKey(key);
    const before = this.size;
    this.root = removeNode(this.root, key);
    return this.size !== before;
  }
  values() {
    const result = [];
    function visit(node) {
      if (!node) return;
      visit(node.left); result.push(node.key); visit(node.right);
    }
    visit(this.root);
    return result;
  }
}
const tree = new AVLTree();
[9, 5, 10, 0, 6, 11, -1, 1, 2].forEach(key => tree.insert(key));
tree.remove(10);
console.log(JSON.stringify(tree.values()));
console.log(JSON.stringify({ size: tree.size }));

파일이 있는 폴더의 터미널에서 실행합니다.

node algorithm-avl-tree-deletion.mjs

기대 출력

[-1,0,1,2,5,6,9,11]
{"size":8}