SorryToPerson logo
返回
算法2026-04-15·9 分钟

算法知识库：红黑树实现

红黑树的节点、插入和平衡操作的 JavaScript/TypeScript 实现。

红黑树实现

1. 红黑树基础

  • 每个节点要么是红色，要么是黑色。
  • 根节点必须是黑色。
  • 红色节点的子节点必须是黑色。
  • 从根到叶子的每条路径必须包含相同数量的黑色节点。

2. 红黑树节点定义

ts
enum Color {
  RED = 'RED',
  BLACK = 'BLACK',
}

class RBTreeNode<T = number> {
  value: T;
  color: Color;
  left: RBTreeNode<T> | null = null;
  right: RBTreeNode<T> | null = null;
  parent: RBTreeNode<T> | null = null;

  constructor(value: T, color: Color = Color.RED) {
    this.value = value;
    this.color = color;
  }
}

3. 左旋和右旋

ts
function rotateLeft<T>(root: RBTreeNode<T> | null, node: RBTreeNode<T>): RBTreeNode<T> | null {
  // 时间复杂度: O(1)
  const right = node.right;
  if (!right) return root;
  node.right = right.left;
  if (right.left) right.left.parent = node;
  right.parent = node.parent;

  if (!node.parent) {
    root = right;
  } else if (node === node.parent.left) {
    node.parent.left = right;
  } else {
    node.parent.right = right;
  }

  right.left = node;
  node.parent = right;
  return root;
}

function rotateRight<T>(root: RBTreeNode<T> | null, node: RBTreeNode<T>): RBTreeNode<T> | null {
  // 时间复杂度: O(1)
  const left = node.left;
  if (!left) return root;
  node.left = left.right;
  if (left.right) left.right.parent = node;
  left.parent = node.parent;

  if (!node.parent) {
    root = left;
  } else if (node === node.parent.right) {
    node.parent.right = left;
  } else {
    node.parent.left = left;
  }

  left.right = node;
  node.parent = left;
  return root;
}

4. 插入与修复

ts
function insertRB<T>(root: RBTreeNode<T> | null, value: T): RBTreeNode<T> {
  // 时间复杂度: O(log n)
  const newNode = new RBTreeNode(value);
  if (!root) {
    newNode.color = Color.BLACK;
    return newNode;
  }

  let parent: RBTreeNode<T> | null = null;
  let current = root;
  while (current) {
    parent = current;
    current = value < current.value ? current.left : current.right;
  }

  newNode.parent = parent;
  if (parent) {
    if (value < parent.value) parent.left = newNode;
    else parent.right = newNode;
  }

  return insertFixup(root, newNode);
}

function insertFixup<T>(root: RBTreeNode<T>, node: RBTreeNode<T>): RBTreeNode<T> {
  // 时间复杂度: O(log n)
  while (node.parent && node.parent.color === Color.RED) {
    const parent = node.parent;
    const grandparent = parent.parent;
    if (!grandparent) break;

    const uncle = parent === grandparent.left ? grandparent.right : grandparent.left;

    if (uncle?.color === Color.RED) {
      parent.color = Color.BLACK;
      uncle.color = Color.BLACK;
      grandparent.color = Color.RED;
      node = grandparent;
    } else {
      if (parent === grandparent.left) {
        if (node === parent.right) {
          node = parent;
          root = rotateLeft(root, node)!;
        }
        parent.color = Color.BLACK;
        grandparent.color = Color.RED;
        root = rotateRight(root, grandparent)!;
      } else {
        if (node === parent.left) {
          node = parent;
          root = rotateRight(root, node)!;
        }
        parent.color = Color.BLACK;
        grandparent.color = Color.RED;
        root = rotateLeft(root, grandparent)!;
      }
    }
  }

  root.color = Color.BLACK;
  return root;
}

5. 实现要点

  • 尽量保持 null 节点简化逻辑。
  • 旋转时必须同步更新父节点指针。
  • 插入后修复时分为颜色重绘和旋转两类操作。
  • 红黑树适合实现有序集合、映射和自平衡二叉树。
算法红黑树JavaScript