TypeScript数据结构与算法：红黑树

上一篇《TypeScript 数据结构与算法：AVL 树》实现了 Typescript 中自平衡的AVL树的数据结构与算法，本篇继续进一步实现性能更加优秀的红黑树(red–black tree)。

虽然 AVL 树已经实现了二叉搜索树的平衡，但是由于每次添加和删除节点时都会涉及到再平衡操作，所以会比较复杂费时。所以在工业级应用中，都会用另一种近似平衡树算法 红黑树 来实现。

这次断更很长时间，就是因为红黑树花费我了大量的时间来学习和理解。这是至今为止遇到的最难写的数据结构的代码，虽然现在理解了原理，但是让我离线手写我仍然写不出来。而且红黑树和其他数据结构有个最大的区别：普通的数据结构都是设计出来的，但是红黑树是由 2-3 树``推导出来的数学模型。

具体的推导过程我就不把经典复述一遍了，感兴趣的同学可以看《算法第四版》的 269 页到 292 页，详细讲述了 2-3 树如何实现自平衡以及如何把 2-3 树映射成等价的左倾红黑树。值得一提的是，该书的作者 Robert Sedgewick 正是红黑树的发明者。学习完之后有几个深刻体会：

1. 对于 2-3 树等价的红黑树来说，由于 2-3 树的三叉节点被变为了 3 个二叉节点树，所以红黑树中的红颜色就代表着这里是 2-3 树中的三叉节点。
2. AVL 树的高度接近 log₂N；对于 2-3 树来说，由于节点可以为二叉或三叉，所以平衡后高度不会超过 log₂N，也不会低于 log₃N；而对于 2-3 树等价的红黑树来说，由于三叉节点被变为了 2 层，所以平衡后高度不会超过 2log₂N。
3. 很关键的一点，只要看见红黑树的红色节点（链接），别把它当成子节点，把它抻平，就能理解 2-3 树和左倾红黑树的对应关系，如下图所示：

另外，左倾红黑树还有另外一些推导出来的性质：

• 红链接均为左链接；
• 没有任何一个节点同时和两条红链接相连（也就是说红色节点不能相邻或者为兄弟节点）；
• 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同（也就是说把红色抻平后，各个叶子节点的高度相差不会超过 1）。

具体的红黑树的算法实现过程我就不赘述了，按照我的理解把算法第四版的左倾红黑树 TypeScript 代码实现如下：

红黑树代码

节点类

红黑树节点类 RedBlackNode 继承自之前实现的二叉搜索树的节点类 Node：

import { Node } from "./node";

// 节点颜色枚举值
export enum Colors {
  RED = 0,
  BLACK = 1
}

// 红黑树节点，继承自普通Node
export class RedBlackNode<K> extends Node<K> {
  left: RedBlackNode<K>;
  right: RedBlackNode<K>;
  // 红黑树节点有color特殊属性
  color: Colors;

  constructor(public key: K) {
    super(key);
    // 节点的默认颜色为红色
    this.color = Colors.RED;
  }

  /**
   * @description: 返回节点是否为红色
   */
  isRed(): boolean {
    return this.color === Colors.RED;
  }

  /**
   * @description: 位运算反转节点的颜色
   */
  flipColor() {
    this.color = 1 ^ this.color;
  }
}

红黑树类

同样，红黑树类 RedBlackTree 也继承自之前实现的二叉搜索树类 BinarySearchTree。在实现 RedBlackTree 的代码时，参照的算法四中已经实现的红黑树类的 JAVA 代码。

import { defaultCompare, ICompareFunction, Compare } from "../util";
import BinarySearchTree from "./binary-search-tree";
import { RedBlackNode, Colors } from "./models/red-black-node";

export default class RedBlackTree<T> extends BinarySearchTree<T> {
  protected root: RedBlackNode<T>;

  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
    super(compareFn);
  }

  /**
   * 右旋
   * 不管是左旋还是右旋，实现的方式和AVL树的左旋右旋类似
   *
   *       a                           c
   *      / \                         / \
   *     c   b -> rotateRight(a) ->   d   a
   *    / \                             / \
   *   d   e                           e   b
   *
   * @param node Node<T>
   */
  private rotateRight(node: RedBlackNode<T>): RedBlackNode<T> {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    tmp.color = node.color;
    node.color = Colors.RED;
    return tmp;
  }

  /**
   * 左旋
   *
   *     b                              d
   *    / \                            / \
   *   a   d   -> rotateLeft(b) ->    b   e
   *      / \                        / \
   *     c   e                      a   c
   *
   * @param node Node<T>
   */
  private rotateLeft(node: RedBlackNode<T>): RedBlackNode<T> {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    tmp.color = node.color;
    node.color = Colors.RED;
    return tmp;
  }

  /**
   * @description: 插入键
   */
  insert(key: T) {
    this.root = this.insertNode(this.root, key);
    this.root.color = Colors.BLACK;
  }

  /**
   * @description: 插入键的递归方法
   */
  protected insertNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
    // 基线条件，如果插入到空白节点处，就插入一个红节点
    if (node == null) {
      let node = new RedBlackNode(key);
      node.color = Colors.RED;
      return node;
    }

    // 递归点
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else {
      node.key = key;
    }

    return this.balance(node);
  }
  /**
   * 移除最小键
   */
  public deleteMin() {
    if (this.root) return;

    // 如果根节点左右均为黑，则把根节点设为红
    if (!this.isRed(this.root.left) && !this.isRed(this.root.right))
      this.root.color = Colors.RED;

    // 调用删除最小键的递归方法
    this.root = this.deleteMinNode(this.root);
    // 最后把根节点颜色纠正为黑
    if (this.root) this.root.color = Colors.BLACK;
  }

  /**
   * @description: 删除最小键的递归方法
   */
  private deleteMinNode(node: RedBlackNode<T>): RedBlackNode<T> {
    // 基线条件
    if (node.left == null) return null;

    // 如果左右节点均为黑，则调用moveRedLeft
    if (!this.isRed(node.left) && !this.isRed(node.left.left))
      node = this.moveRedLeft(node);

    // 递归调用寻找最小键
    node.left = this.deleteMinNode(node.left);
    // 每次递归后都要平衡节点
    return this.balance(node);
  }

  /**
   * 移除最大键
   */
  public deleteMax() {
    if (!this.root) return;

    // 如果根节点的所有子节点为黑，把根节点设为红
    if (!this.isRed(this.root.left) && !this.isRed(this.root.right))
      this.root.color = Colors.RED;

    // 调用删除最大节点的递归方法
    this.root = this.deleteMaxNode(this.root);
    // 纠正根节点颜色为黑
    if (this.root) this.root.color = Colors.BLACK;
  }

  /**
   * @description: 删除最大键节点的递归方法
   */
  private deleteMaxNode(node: RedBlackNode<T>): RedBlackNode<T> {
    // 当左子节点为红时，右旋
    if (this.isRed(node.left)) node = this.rotateRight(node);

    // 基线条件
    if (node.right == null) return null;

    // 如果左右节点均为黑，则调用moveRedRight
    if (!this.isRed(node.right) && !this.isRed(node.right.left))
      node = this.moveRedRight(node);

    // 递归调用寻找最大键
    node.right = this.deleteMaxNode(node.right);

    // 每次递归后都要平衡节点
    return this.balance(node);
  }

  /**
   * @description: 删除指定key
   */
  public delete(key: T) {
    // 没有节点时直接返回
    if (!this.search(key)) return;

    // 如果根节点的所有子节点为黑，把根节点设为红
    if (!this.isRed(this.root.left) && !this.isRed(this.root.right))
      this.root.color = Colors.RED;

    // 调用删除节点的递归方法
    this.root = this.deleteNode(this.root, key);
    // 纠正根节点颜色为黑
    if (this.root) this.root.color = Colors.BLACK;
  }

  /**
   * @description: 删除指定节点的递归方法
   */
  private deleteNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
    // 如果key比当前节点小
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (!this.isRed(node.left) && !this.isRed(node.left?.left))
        node = this.moveRedLeft(node);
      // 继续递归
      node.left = this.deleteNode(node.left, key);
      //如果key不小于当前节点
    } else {
      if (this.isRed(node.left)) node = this.rotateRight(node);

      // 找到了对应节点并且右子节点为空
      if (
        this.compareFn(key, node.key) === Compare.EQUALS &&
        node.right == null
      )
        return null;

      // 如果左右节点均为黑，则调用moveRedRight
      if (!this.isRed(node.right) && !this.isRed(node.right?.left))
        node = this.moveRedRight(node);

      // 找到了对应节点，并且右侧子节点不为空
      if (this.compareFn(key, node.key) === Compare.EQUALS) {
        const x = this.minNode(node.right);
        node.key = x.key;
        node.right = this.deleteMinNode(node.right);
        // 没有找到继续递归
      } else {
        // 没有找到对应节点，继续递归
        node.right = this.deleteNode(node.right, key);
      }
    }
    // 每次递归后都要平衡节点
    return this.balance(node);
  }

  /**
   * @description: 返回根节点
   */
  getRoot(): RedBlackNode<T> {
    return this.root;
  }

  /**
   * @description: 修正节点颜色
   */
  private flipColors(node: RedBlackNode<T>) {
    node.flipColor();
    node.left.flipColor();
    node.right.flipColor()
  }

  /**
   * @description: 平衡树
   */
  private balance(node: RedBlackNode<T>): RedBlackNode<T> {
    // 核心算法，通过三行判断，来生成一个左倾红黑树
    // 右红左黑，左旋把红链接转到左侧来
    if (this.isRed(node.right) && !this.isRed(node.left))
      node = this.rotateLeft(node);
    // 左红并且左左也红，右旋
    if (this.isRed(node.left) && this.isRed(node.left?.left))
      node = this.rotateRight(node);
    // 不管是旋出来的还是自然插入出来的，只要两红当兄弟，就变色，并把红色向上挪一层（相当于23树中加高一层）
    if (this.isRed(node.left) && this.isRed(node.right)) this.flipColors(node);
    return node;
  }

  /**
   * @description: 假如节点为红，并且左右为黑，使左或者左的子节点为红
   */
  private moveRedLeft(node: RedBlackNode<T>): RedBlackNode<T> {
    this.flipColors(node);
    if (this.isRed(node.right.left)) {
      node.right = this.rotateRight(node.right);
      node = this.rotateLeft(node);
      this.flipColors(node);
    }
    return node;
  }

  /**
   * @description: 假如节点为红，并且节点的右和右左为黑，则使节点的右或者右的子节点为红
   */
  private moveRedRight(node: RedBlackNode<T>): RedBlackNode<T> {
    this.flipColors(node);
    if (this.isRed(node.left.left)) {
      node = this.rotateLeft(node);
      this.flipColors(node);
    }
    return node;
  }

  /**
   * @description: 判断节点是否为红色
   */
  private isRed(node: RedBlackNode<T>) {
    // 如果为空，也认为是黑色
    // 这里很重要，相当于树底部全是黑色空节点
    if (!node) {
      return false;
    }
    return node.isRed();
  }
}

终于把红黑树看完了，下一篇来分析 二叉堆。

---

前端记事本，不定期更新，欢迎关注！

• 微信公众号： 林景宜的记事本
• 博客：林景宜的记事本
• 掘金专栏：林景宜的记事本
• 知乎专栏： 林景宜的记事本
• Github: MageeLin

---