Red-Black 트리 삭제: LLRB 색 이동과 검은 높이 복구

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

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

function requireKey(key) {
  if (!Number.isSafeInteger(key)) throw new TypeError('key must be a safe integer');
}
class RBNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.red = true;
    this.size = 1;
  }
}
function isRed(node) { return node !== null && node.red; }
function sizeOf(node) { return node ? node.size : 0; }
function refresh(node) {
  node.size = 1 + sizeOf(node.left) + sizeOf(node.right);
  return node;
}
function rotateLeft(node) {
  const top = node.right;
  node.right = top.left;
  top.left = node;
  top.red = node.red;
  node.red = true;
  refresh(node);
  return refresh(top);
}
function rotateRight(node) {
  const top = node.left;
  node.left = top.right;
  top.right = node;
  top.red = node.red;
  node.red = true;
  refresh(node);
  return refresh(top);
}
function flipColors(node) {
  node.red = !node.red;
  node.left.red = !node.left.red;
  node.right.red = !node.right.red;
}
function balance(node) {
  if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node);
  if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node);
  if (isRed(node.left) && isRed(node.right)) flipColors(node);
  return refresh(node);
}
function insertNode(node, key) {
  if (!node) return new RBNode(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 balance(node);
}
function moveRedLeft(node) {
  flipColors(node);
  if (isRed(node.right.left)) {
    node.right = rotateRight(node.right);
    node = rotateLeft(node);
    flipColors(node);
  }
  return node;
}
function moveRedRight(node) {
  flipColors(node);
  if (isRed(node.left.left)) {
    node = rotateRight(node);
    flipColors(node);
  }
  return node;
}
function deleteMin(node) {
  if (!node.left) return null;
  if (!isRed(node.left) && !isRed(node.left.left)) node = moveRedLeft(node);
  node.left = deleteMin(node.left);
  return balance(node);
}
function removeNode(node, key) {
  if (key < node.key) {
    if (!isRed(node.left) && !isRed(node.left.left)) node = moveRedLeft(node);
    node.left = removeNode(node.left, key);
  } else {
    if (isRed(node.left)) node = rotateRight(node);
    if (key === node.key && !node.right) return null;
    if (!isRed(node.right) && !isRed(node.right.left)) node = moveRedRight(node);
    if (key === node.key) {
      let successor = node.right;
      while (successor.left) successor = successor.left;
      node.key = successor.key;
      node.right = deleteMin(node.right);
    } else {
      node.right = removeNode(node.right, key);
    }
  }
  return balance(node);
}
class RedBlackTree {
  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);
    this.root.red = false;
    return this.size !== before;
  }
  remove(key) {
    requireKey(key);
    if (!this.has(key)) return false;
    if (!isRed(this.root.left) && !isRed(this.root.right)) this.root.red = true;
    this.root = removeNode(this.root, key);
    if (this.root) this.root.red = false;
    return true;
  }
  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 RedBlackTree();
[17, 9, 19, 75, 85].forEach(key => tree.insert(key));
[19, 75, 85].forEach(key => tree.remove(key));
console.log(JSON.stringify(tree.values()));
console.log(JSON.stringify({ size: tree.size, rootBlack: !tree.root.red }));
[9, 17].forEach(key => tree.remove(key));
console.log(JSON.stringify({ size: tree.size, root: tree.root }));

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

node algorithm-red-black-tree-deletion.mjs

기대 출력

[9,17]
{"size":2,"rootBlack":true}
{"size":0,"root":null}