1.02 红黑树

当然, 我可以为您提供一个在 Bun 环境下使用 TypeScript 泛型实现的红黑树操作实例。红黑树是一种自平衡的二叉搜索树, 它在插入和删除操作后能保持平衡, 从而保证了搜索、插入和删除操作的时间复杂度为 O (log n)。

以下是完整的实现:

enum Color {
  RED,
  BLACK
}
 
class Node<T> {
  data: T;
  color: Color;
  left: Node<T> | null;
  right: Node<T> | null;
  parent: Node<T> | null;
 
  constructor(data: T) {
    this.data = data;
    this.color = Color.RED;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}
 
class RedBlackTree<T> {
  private root: Node<T> | null;
 
  constructor() {
    this.root = null;
  }
 
  insert(data: T): void {
    let newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
      this.root.color = Color.BLACK;
    } else {
      this.insertNode(this.root, newNode);
      this.fixViolation(newNode);
    }
  }
 
  private insertNode(node: Node<T>, newNode: Node<T>): void {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
        newNode.parent = node;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
        newNode.parent = node;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
 
  private rotateLeft(node: Node<T>): void {
    let rightChild = node.right!;
    node.right = rightChild.left;
 
    if (rightChild.left !== null) {
      rightChild.left.parent = node;
    }
 
    rightChild.parent = node.parent;
 
    if (node.parent === null) {
      this.root = rightChild;
    } else if (node === node.parent.left) {
      node.parent.left = rightChild;
    } else {
      node.parent.right = rightChild;
    }
 
    rightChild.left = node;
    node.parent = rightChild;
  }
 
  private rotateRight(node: Node<T>): void {
    let leftChild = node.left!;
    node.left = leftChild.right;
 
    if (leftChild.right !== null) {
      leftChild.right.parent = node;
    }
 
    leftChild.parent = node.parent;
 
    if (node.parent === null) {
      this.root = leftChild;
    } else if (node === node.parent.right) {
      node.parent.right = leftChild;
    } else {
      node.parent.left = leftChild;
    }
 
    leftChild.right = node;
    node.parent = leftChild;
  }
 
  private fixViolation(node: Node<T>): void {
    let parent = null;
    let grandParent = null;
 
    while (node !== this.root && node.color !== Color.BLACK && node.parent!.color === Color.RED) {
      parent = node.parent!;
      grandParent = parent.parent!;
 
      if (parent === grandParent.left) {
        let uncle = grandParent.right;
 
        if (uncle !== null && uncle.color === Color.RED) {
          grandParent.color = Color.RED;
          parent.color = Color.BLACK;
          uncle.color = Color.BLACK;
          node = grandParent;
        } else {
          if (node === parent.right) {
            this.rotateLeft(parent);
            node = parent;
            parent = node.parent!;
          }
 
          this.rotateRight(grandParent);
          let temp = parent.color;
          parent.color = grandParent.color;
          grandParent.color = temp;
          node = parent;
        }
      } else {
        let uncle = grandParent.left;
 
        if (uncle !== null && uncle.color === Color.RED) {
          grandParent.color = Color.RED;
          parent.color = Color.BLACK;
          uncle.color = Color.BLACK;
          node = grandParent;
        } else {
          if (node === parent.left) {
            this.rotateRight(parent);
            node = parent;
            parent = node.parent!;
          }
 
          this.rotateLeft(grandParent);
          let temp = parent.color;
          parent.color = grandParent.color;
          grandParent.color = temp;
          node = parent;
        }
      }
    }
 
    this.root!.color = Color.BLACK;
  }
 
  inorderTraversal(): T[] {
    const result: T[] = [];
    this.inorderTraversalHelper(this.root, result);
    return result;
  }
 
  private inorderTraversalHelper(node: Node<T> | null, result: T[]): void {
    if (node !== null) {
      this.inorderTraversalHelper(node.left, result);
      result.push(node.data);
      this.inorderTraversalHelper(node.right, result);
    }
  }
}
 
// 使用示例
const tree = new RedBlackTree<number>();
tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
 
console.log("Inorder traversal:", tree.inorderTraversal());

这个实现包括以下主要部分:

1. Node<T> 类: 表示红黑树中的节点, 包含数据、颜色、左右子节点和父节点。

2. RedBlackTree<T> 类: 实现红黑树的主要逻辑。

3. insert 方法: 插入新节点并维护红黑树的性质。

4. rotateLeft 和 rotateRight 方法: 实现左旋和右旋操作。

5. fixViolation 方法: 在插入新节点后修复红黑树的性质。

6. inorderTraversal 方法: 中序遍历红黑树, 用于验证树的结构。

要在 Bun 环境中运行这个示例, 你可以创建一个新的 TypeScript 文件 (例如 redBlackTree.ts), 将上面的代码粘贴进去, 然后使用以下命令运行:

bun run redBlackTree.ts

这个实现提供了红黑树的基本操作。你可以根据需要添加更多功能, 如删除操作、搜索操作等。请注意, 红黑树是一个相对复杂的数据结构, 这个实现主要关注了插入操作和维护红黑树性质的部分。在实际应用中, 可能需要更全面的测试和错误处理。