js实现红

红黑树的基本概念

红黑树是一种自平衡的二叉搜索树，具有以下特性：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点）是黑色。
4. 红色节点的子节点必须是黑色（不能有连续的红色节点）。
5. 从任一节点到其叶子节点的路径包含相同数量的黑色节点。

红黑树的节点结构

用JavaScript定义红黑树节点的结构：

class RBNode {
  constructor(key, color = 'RED') {
    this.key = key;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.color = color; // 'RED' or 'BLACK'
  }
}

红黑树的插入操作

插入新节点后，可能破坏红黑树的性质，需要通过旋转和重新着色修复：

1. 标准二叉搜索树插入：按二叉搜索树规则插入新节点，初始颜色为红色。
2. 修复红黑树性质：检查父节点和叔节点的颜色，根据情况旋转或重新着色。

class RedBlackTree {
  constructor() {
    this.NIL = new RBNode(null, 'BLACK'); // 叶子节点
    this.root = this.NIL;
  }

  insert(key) {
    const newNode = new RBNode(key);
    newNode.left = this.NIL;
    newNode.right = this.NIL;

    let parent = null;
    let current = this.root;

    while (current !== this.NIL) {
      parent = current;
      if (newNode.key < current.key) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    newNode.parent = parent;
    if (parent === null) {
      this.root = newNode;
    } else if (newNode.key < parent.key) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }

    this.fixInsert(newNode);
  }

  fixInsert(node) {
    while (node.parent && node.parent.color === 'RED') {
      if (node.parent === node.parent.parent.left) {
        const uncle = node.parent.parent.right;
        if (uncle.color === 'RED') {
          node.parent.color = 'BLACK';
          uncle.color = 'BLACK';
          node.parent.parent.color = 'RED';
          node = node.parent.parent;
        } else {
          if (node === node.parent.right) {
            node = node.parent;
            this.leftRotate(node);
          }
          node.parent.color = 'BLACK';
          node.parent.parent.color = 'RED';
          this.rightRotate(node.parent.parent);
        }
      } else {
        // 对称逻辑，处理右子树情况
      }
    }
    this.root.color = 'BLACK';
  }

  leftRotate(x) {
    const y = x.right;
    x.right = y.left;
    if (y.left !== this.NIL) {
      y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
  }

  rightRotate(y) {
    const x = y.left;
    y.left = x.right;
    if (x.right !== this.NIL) {
      x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent === null) {
      this.root = x;
    } else if (y === y.parent.right) {
      y.parent.right = x;
    } else {
      y.parent.left = x;
    }
    x.right = y;
    y.parent = x;
  }
}

红黑树的删除操作

删除操作更复杂，需处理多种情况以保持平衡：

1. 标准二叉搜索树删除：找到后继节点并替换。
2. 修复红黑树性质：根据兄弟节点和其子节点的颜色调整。

// 删除和修复逻辑较长，此处省略，可参考经典算法实现

应用场景

红黑树用于高效维护有序数据，常见于：

• JavaScript引擎（如V8）的Map和Set实现。
• 数据库索引结构。
• 时间复杂度的保证：插入、删除、查找均为O(log n)。

以上代码展示了红黑树的核心逻辑，实际实现需补充完整删除和对称情况的处理。