谁说前端不能搞红黑树，用这55张图拿JS一起手撕红黑树

Hi~，我是一碗周，如果写的文章有幸可以得到你的青睐，万分有幸~

🍎 写在前面

红黑树是数据结构与算法中比较难理解的一个树状结构了，在前端开发中，如果仅仅是业务开发的话，几乎是用不到红黑树的；那为什么还有学习红黑树呢？红黑树可以说是现在应用的最复杂的二叉树之一，如果红黑树都能掌握还会怕其他的树状结构嘛？

通过本篇文章你将会掌握下面这些内容，我大概说明了内容以及难度：

上面的难度划分仅仅是我按照文中的内容进行划分，如果大佬非说红黑树的操作简单，大佬，请收下我的膝盖。

🥭 平衡树和不平衡树

二叉搜索树又分为平衡树和不平衡树，如下图所示：

上图的两棵树都是二叉搜索树，左边这颗平衡的二叉搜索树查找一个节点的时间复杂度是，假如有10个亿的数据只需要查找30次即可；右边这颗不平衡的二叉搜索树就相当于是一个排序后的链表，时间复杂度最坏为，假如还是10亿数据，查找可能需要10亿次。

假如我们依次往二叉搜索树插入1, 2, 3, 4, 5, ... n，插入的数量为n，树的高度也是n，因为我们最新插入的节点永远都是叶子节点。

常见的平衡树主要有AVL树和红黑树：

• AVL树的出现早于红黑树的，它是一颗高度平衡树，它的任意节点的左右子树的高度差不会超过1，每为其增加一个节点，如果其左右子树的高度差超过了1，都会进行旋转，直到平衡为止；由于其需要频繁进行旋转，所以其性能要低于红黑树。
• 红黑树通过变色、左旋、右旋来保持二叉搜索树的平衡性（这里的平衡性指的是黑色平衡，所谓的黑色平衡就是每个节点到叶子节点所经过的黑色节点是一致的），性能要优于AVL树，所以现在平衡树的应用都是红黑树。

🍏 AVL树

AVL树并不是这篇文章的重点，这里仅仅介绍一个AVL树的构建过程，从而说明为什么红黑树的性能要优于AVL树。

假如我们往二叉搜索树中依次插入10, 9 ,8, 7, 6, 5, 4, 3, 2, 1，二叉搜索树是下面这个样子的：

根据这个图我们可以看出这棵二叉树已经退化成了一个有序链表，现在我们用AVL树来优化一下。

第一步：插入10和9，这个没有什么可说的直接插入就好；

第二步，插入8，发现10的左子树的高度为2，右子树的高度为0，需要进行旋转，如下图：

第三步：插入数据7，插入后任意一个节点都满足左右子树的高度差不大于1，所以不用进行旋转。

第四步：插入数据6，插入后发现节点8和节点9的左右子树高度差都是大于1的，需要进行旋转，当出现多个节点不满足左右子树高度差都是大于1时，旋转距离插入节点最近的祖先节点 ，如下图所示：

第五步：插入数据5后，对于根节点9来说，左子树的高度为3，右子树的高度为1，需要进行旋转，过程如下：

第六步，插入数据4，对于节点6来说，左子树的高度为2，右子树的高度为0，需要进行旋转，过程如下：

第七步：插入数据3，插入后插入后任意一个节点都满足左右子树的高度差不大于1，所以不用进行旋转。

第八步：插入数据2，对于节点4来说，左子树的高度为2，右子树的高度为0，需要进行旋转，过程如下：

最后一步，插入数据1，插入数据1后需要

AVL树为每个节点都维护一个平衡因子，平衡因子的值是左子树的高度减去右子树的高度或者右子树的高度减去左子树的高度；当节点的平衡因子的值为1、0、-1，则说明它是平衡的，当节点的平衡因子的绝对值大于2时，则说明这棵树是不平衡的，需要进行旋转。

上图出自为维基百科

🍑 AVL树和红黑树优缺点对比

首先我们先来看一下如果上面那些数据依次插入红黑树是什么样子的，先不用管红黑树是怎么构建的，这里主要分析一下AVL树和红黑树的优缺点。

从上图中我们可以看到：

• 红黑树并没有追求完全平衡，它只是黑色节点平衡（即根节点到叶子节点的黑色节点数量一致，例如节点5到任何叶子节点的黑色节点数量都是2），而AVL树是高度平衡树，也就是追求完全平衡；这就意味这AVL树随着节点数量的越来越多，出现不平衡时，旋转次数也就会也来越多，而红黑树出现任何不平衡，旋转三次之内一定会解决（后面会验证这个结论）
• 删除一个树种的节点导致失衡，AVL树需要从维护从根节点到删除节点路径上所有节点的平衡，时间时间复杂度时为O(logn)，而红黑树最多只需旋转三次即可恢复平衡，时间复杂度为O(1)；
• 由于AVL树是高度平衡树，查找效率要高于红黑树，但是红黑树比AVL树不平衡最多一层，也就是说差多最多就差一次。

基于以上几点得出红黑树的综合能力要优于AVL树，表现会更加稳定。

🍒2-3-4树

2-3-4树是四阶的B树，它属于一种多路查找，其具有以下限制：

B树是一种自平衡的树，其插入、查找和删除的时间复杂度都是O(logn)

• 所有叶子节点都必须具有相同的深度，也就说2-3-4树是一颗满树；

• 2-3-4树把数据存储在元素中，元素组成节点，节点只能是下列之一

  • 2-节点：包含一个元素和2个子节点；
  • 3-节点：包含两个元素和3个子节点；
  • 4-节点：包含三个元素和4个子节点。

• 元素使用保持排序顺序，整体上保持二叉搜索树的特质，即左子树小于根节点，右子树大于跟节点；

2-3-4树的节点如下所示：

🍓2-3-4树的构建过程

现在我们从头来构建一颗2-3-4树，往树中依次插入71, 88, 80, 90, 89, 91, 66, 101, 150, 130, 166：

第一步：由于2-3-4树必须是满树，且可以是2~4节点，所以前三个元素直接构成一个4节点：

第二步：插入元素90，过程如下图：

第三步：插入元素89，合并节点后插入元素91，过程如下：

第四步：插入元素66，过程如下：

第五步：插入元素101，过程如下：

第六步：插入元素150，过程如下：

第七步：插入元素166合并节点后，插入元素130，过程如下：

此时如果我们在插入一个元素，他会寻找自己的位置，并于原节点组成新的节点，例如插入元素35，最终的2-3-4树如下所示：

由构建过程可以得知，2-3-4的构建是从叶子节点依次到根节点进行构建。

🫐 2-3-4树与红黑树的关系

2-3-4树的任意一个节点，都至少对应红黑树的一种结构，也就是说2-3-4树至少对应一棵红黑树，一棵红黑树对应一颗2-3-4树，如下图展示了2-3-4树中的节点与红黑树结构的对应关系

2-3-4树还有一个状态，就是一个4节点插入元素后，这里将这个状态称为裂变状态，如下图所示：

根据新插入元素的大小不同分为不同的4个位置。

🍈 2-3-4树与红黑树的转换

我们了解了2-3-4树与红黑树的关系后，现在我们将之前画的2-3-4树转换为红黑树，如下图所示：

现在来将一颗红黑树转换为2-3-4树，如下图所示：

🍊 红黑树

前面我们用了很大的篇幅来介绍平衡的二叉搜索树、AVL树和2-3-4树，其目的就是为了更好更快的学习和了解红黑树，现在我们正式开始进入红黑树的学习。

🍉 红黑树的五大特性

红黑树除了满足二叉搜索树的基本规则外，还满足以下五个特性：

• 节点是红色或者黑色（废话，要不然咋叫红黑树）；

• 根节点是黑色（这是因为红黑树是由2-3-4树转换而来，根据2-3-4树的2节点、3节点或者4节点转换为红黑树的结对应关系，黑色节点总是作为父节点）

• 每个叶子节点都是黑色的空节点（这里的叶子节点指的NIL节点，如下图）

  

• 每个红色节点的两个子节点都是黑色，也就是说叶子节点到根节点所在的路径上不会出现两个连续的红色节点。

  出现红色节点的情况主要有两种情况：

  • 2-3-4树的3节点会出现一个红色节点；
  • 2-3-4树的4节点会出现两个红色节点；

  2-3-4树的3节点肯定会出现3个节点，这三个节点不管是什么节点都存在黑色节点，最小的那个黑色节点作为红色节点父级的左子树，剩余的两个节点作为红色节点的左右子树，如下图所示：

  

  2-3-4树的4节点的情况与3节点类似，如下图所示：

  

• 从任意节点到其他叶子节点的所有路径所包含相同数量的黑色节点；这是因为2-3-4是一颗满树，每个节点转换为红黑树只有一个黑节点。

🍒 完整代码

红黑树的源代码在GitHub中，各位看官可以结合源代码与文本一起食用，效果更佳。

🍋 红黑树的变色操作

本篇文章中关于红黑树的操作全部使用JavaScript完成，首先我们定义一个类，用于创建红黑树的节点，然后在定义一个类，用于实例化红黑树，代码如下：

const RED = 'RED'
const BLACK = 'BLACK'
class RBNode {
  /**
   * 创建一个新的节点
   * @author ywanzhou
   * @param {number} val 要插入的数值
   * @param {RBNode} parent 父节点
   * @param {RBNode} left 左子树
   * @param {RBNode} right 右子树
   * @param {string} color 颜色
   * @returns 一个新的节点
   */
  constructor(val, parent, left = null, right = null, color = RED) {
    if (color !== RED && color !== BLACK)
      throw new Error('color can only be RED or BLACK')
    this.val = val
    this.parent = parent
    this.left = left
    this.right = right
    this.color = color
  }
}
class RBTree {
  constructor() {
    this.root = null
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

节点的变色操作比较简单，无非就是黑色变红色，红色变黑色，示例代码如下：

/**
 * 给定一个节点，修改节点的颜色 这是一个私有方法
 * @author ywanzhou
 * @param {RBNode} node 需要改变的颜色
 * @param {string} color 需要节点改变后的颜色
 */
#setColor(node, color) {
  if (color !== RED && color !== BLACK)
    throw new Error('color can only be RED or BLACK')
  if (!node) throw new Error('node is a empty RBNode')
  node.color = color
}
1
2
3
4
5
6
7
8
9
10
11
12

🍌 红黑树的旋转操作

旋转操作分为左旋和右旋，我们依次来看：

• 左旋转：又称逆时针旋转，旋转时以某个节点作为旋转点，其右子节点变成自己的父节点，右子节点的左节点变成旋转节点的右节点，过程如下图所示：
  

• 右旋转：又称顺时针旋转，旋转时以某个节点作为旋转点，其左子节点变成自己的父节点，左子节点的右节点变成旋转节点的左节点，过程如下图所示：
  

实现左旋右旋的代码如下 （下列的代码中每一行均有注释，两种旋转方式一种是对代码的理解，一种是实现步骤）：

/**
 * 围绕 node 进行左旋
 * 效果如下
 *         node           ->          pr(r)
 *        /   \           ->         /   \
 *       pl   pr(r)       ->       node   cr
 *           / \          ->       /  \
 *          cl  cr        ->      pl   cl
 * @author ywanzhou
 * @param {Node} node 需要旋转的节点
 */
#leftRotate(node) {
  if (!node) return
  // 缓存一下 node 的右节点
  const r = node.right
  // 将 pr 的右节点 pr 重新赋值为 cl
  node.right = r.left
  if (r.left !== null) {
    // 将 cl 的父节点指向 node
    r.left.parent = node
  }
  // 将节点r连接node节点的父节点
  r.parent = node.parent
  if (node.parent === null) {
    // 如果需要旋转的节点是根节点，则将根节点从node修改为r
    this.root = r
  } else if (node.parent.left === node) {
    // 说明要旋转的node是父节点的左节点
    node.parent.left = r
  } else if (node.parent.right === node) {
    // 说明要旋转的node是父节点的右节点
    node.parent.right = r
  }
  // 处理 r 节点的左节点
  r.left = node
  // 处理 node 的父节点
  node.parent = r
}
/**
 * 围绕 node 进行右旋
 * 效果如下
 *           node         ->          pl(l)
 *          /   \         ->        /   \
 *         pl(l) pr       ->       cl   node
 *        /  \            ->           / \
 *       cl   cr          ->          cr  pr
 * @author ywanzhou
 * @param {Node} node 需要旋转的节点
 */
#rightRotate(node) {
  if (!node) return
  // 1. 修改旋转节点 左节点的右节点 为 旋转节点的左节点
  // 1.1 缓存一下 node 的左节点
  const l = node.left
  // 1.2 修改左节点的右节点为旋转节点的左节点
  node.left = l.right

  // 2. 连接旋转节点的左节点与旋转节点的引用
  if (l.right !== null) {
    l.right.parent = node
  }

  // 3. 修改 l 节点的父节点
  l.parent = node.parent
  if (node.parent === null) {
    // 3.1 如果 node 此时是根节点，则将根节点重新指向 l
    this.root = l
  } else if (node.parent.left === node) {
    // 3.2 如果 node 是父节点的左节点，则更换左节点
    node.parent.left = l
  } else if (node.parent.right === node) {
    // 3.3 如果 node 是父节点的右节点，则更换右节点
    node.parent.left = r
  }
  // 4. 将旋转节点作为旋转节点左节点的右节点
  l.right = node
  // 4.1 重新建立parent引用
  node.parent = l
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

🍍 红黑树的新增操作

红黑树的新增操作需要分为多种情况讨论，这里我们先拿2-3-4树在推导出红黑树插入插入节点需要哪些操作。

为了保持红黑树的黑色平衡，插入节点时需要旋转和变色操作，情况分为如下几种：

情况一 ：插入节点时不存在任何节点，插入一个节点（新节点始终都是红色，为什么是红色？就拿下图二和图三来说吧，如果直接插入黑色节点，需要做变色处理操作），直接由红色节点转换为黑色节点即可，如下图所示：

情况二：插入节点时，存在父级存在一个黑色节点，在2-3-4树中对应往2节点中插入元素，如下图所示：

情况三 ：2-3-4树种存在一个3节点，插入一个元素时，转换为红黑树可以分为六种情况，如下图所示：

情况四：2-3-4树中已经存在一个4节点，插入元素后的情况如下：

上面的9个图已经列举了红黑树中所有的插入情况，我们现在通过JavaScript来实现一下对应的代码：

/**
 * 往红黑树中插入一个节点
 * @author ywanzhou
 * @param {number} val 要插入的值
 * @return {RBNode} RBTree的根节点
 */
insert(val) {
  // 只允许插入数值
  if (typeof val !== 'number')
    throw new TypeError('insert value is not a number')
  let t = this.root
  // 情况一：红黑树中不存在任何节点，插入收据后直接作为根节点
  if (t === null) {
    this.root = new RBNode(val, null, null, null, BLACK)
    return this.root
  }

  // 1. 寻找插入位置
  // parent 指针用于记录当前要插入的节点位置
  let parent = t.parent
  do {
    parent = t
    // 当前值与根节点的值进行比较，如果当前值大则 cmp 大于 0
    let cmp = val - t.val
    // 判断 cmp 的值 如果大于 0 则插入右子树
    if (cmp > 0) {
      t = t.right
    }
    // 如果小于0则插入左子树
    else if (cmp < 0) {
      t = t.left
    }
    // 如果等于0则说明已经存在，抛出异常
    else {
      throw new Error('insert value already exists')
    }
    /**
     * 当循环结束，此时已经到达末尾节点，t 的值为null，parent表示最后的末尾节点
     */
  } while (t !== null)

  // 2. 将节点插入树中
  // 2.1 创建节点
  const newNode = new RBNode(val, parent)
  // 2.2 根据节点的值来判断是插入右子树还是左子树
  if (newNode.val > parent.val) {
    parent.right = newNode
  } else {
    parent.left = newNode
  }

  // 3. 调整节点位置和颜色，维持红黑树的特性
  this.#fixAfterInsertNode(newNode)
  return this.root
}
/**
 * 给定一个节点，调整在红黑树的位置和颜色
 * @author ywanzhou
 * @param {RBNode} node 要调整的节点
 */
#fixAfterInsertNode(node) {
  // * 需要调整的情况由博文中的图五到图九
  // 新增的节点为红色
  node.color = RED
  // * 博文中图二、三、四都是不需要调整的情况，这三个图都具有一个特点，就是父亲节点的颜色为黑色
  while (node !== null && node !== this.root && node.parent.color === RED) {
    // 1. 首先处理图七和图九的前两种情况（先处理图七和图五无所谓，只是换个方向）
    // 1.1 判断 node 的父节点是爷爷节点的左孩子
    if (
      this.#getParent(node) ===
      this.#getLeft(this.#getParent(this.#getParent(node))) // 当前节点的父节点的父节点的左节点与当前节点的父节点是否相等
    ) {
      // 如果满足条件，已经对应图七和图九中的前两种情况
      // 1.2 获取叔叔节点
      let uncle = this.#getRight(this.#getParent(this.#getParent(node)))
      // 1.3 判断叔叔节点的颜色是否为红色，如果是则变色
      if (this.#getColor(uncle) === RED) {
        // * 如果进入则说明存在叔叔节点，也就是进入图九的前两种情况，按照途中的步骤，通过代码实现
        const grandpa = this.#getParent(this.#getParent(node))
        // 1.3.1 将父节点和叔叔节点修改为黑色，将爷爷节点修改为红色
        this.#setColor(this.#getParent(node), BLACK)
        this.#setColor(uncle, BLACK)
        this.#setColor(grandpa, RED)
        // 将爷爷节点赋值给node，这里对应图九的最后一句话
        node = grandpa
      }
      // * 处理图七和图八的情况
      // 1.4 说明没有叔叔节点或者叔叔节点是黑色，则不需要操作叔叔节点，只需要操作父节点和爷爷节点
      else {
        // 1.7 处理图八的情况
        // 1.7.1 判断插入的节点是否为父节点右节点
        if (node === this.#getRight(this.#getParent(node))) {
          // 1.7.2 将节点的父节点赋值给当前节点
          node = this.#getParent(node)
          // 1.7.3 对 node 进行左旋 转换为图七的情况
          this.#leftRotate(node)
          // 接下来就可以按照图七进行操作
        }
        // 1.5 父节点变黑色 爷爷节点变红色
        const grandpa = this.#getParent(this.#getParent(node))
        this.#setColor(this.#getParent(node), BLACK)
        this.#setColor(grandpa, RED)
        // 1.6 对爷爷节点进行右旋操作
        this.#rightRotate(grandpa)
      }
    } else {
      // 如果不满足条件，已经对应图五和图九中的后两种情况，与上面的代码基本类似
      // 1.2 获取叔叔节点
      let uncle = this.#getLeft(this.#getParent(this.#getParent(node)))
      // 1.3 判断叔叔节点的颜色是否为红色，如果是则变色
      if (this.#getColor(uncle) === RED) {
        // * 如果进入则说明存在叔叔节点，也就是进入图九的后两种情况，按照途中的步骤，通过代码实现
        const grandpa = this.#getParent(this.#getParent(node))
        // 1.3.1 将父节点和叔叔节点修改为黑色，将爷爷节点修改为红色
        this.#setColor(this.#getParent(node), BLACK)
        this.#setColor(uncle, BLACK)
        this.#setColor(grandpa, RED)
        // 将爷爷节点赋值给node，这里对应图九的最后一句话
        node = grandpa
      }
      // * 处理图五和图六的情况
      // 1.4 说明没有叔叔节点或者叔叔节点是黑色，则不需要操作叔叔节点，只需要操作父节点和爷爷节点
      else {
        // 1.7 处理图六的情况
        // 1.7.1 判断插入的节点是否为父节点右节点
        if (node === this.#getLeft(this.#getParent(node))) {
          // 1.7.2 将节点的父节点赋值给当前节点
          node = this.#getParent(node)
          // 1.7.3 对 node 进行右旋 转换为图五的情况
          this.#rightRotate(node)
          // 接下来就可以按照图五进行操作
        }
        // 1.5 父节点变黑色 爷爷节点变红色
        const grandpa = this.#getParent(this.#getParent(node))
        this.#setColor(this.#getParent(node), BLACK)
        this.#setColor(grandpa, RED)
        // 1.6 对爷爷节点进行左旋操作
        this.#leftRotate(grandpa)
      }
    }
  }
  // 将根节点变成黑色
  this.#setColor(this.root, BLACK)
}
/**
 * 获取指定节点的父节点
 * @author ywanzhou
 * @param {RBNode} node
 * @returns {RBNode}
 */
#getParent(node) {
  return node !== null ? node.parent : null
}
/**
 * 获取指定节点的左节点
 * @author ywanzhou
 * @param {RBNode} node
 * @returns {RBNode}
 */
#getLeft(node) {
  return node !== null ? node.left : null
}
/**
 * 获取指定节点的右节点
 * @author ywanzhou
 * @param {RBNode} node
 * @returns {RBNode}
 */
#getRight(node) {
  return node !== null ? node.right : null
}
/**
 * 获取指定节点的颜色
 * @author ywanzhou
 * @param {RBNode} node
 * @returns {string}
 */
#getColor(node) {
  return node === null ? BLACK : node.color
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

现在我们来实例化这个树，看一下创建出的红黑树是否符合标准，示例代码如下：

/**
 * 中序遍历红黑树，打印结果，查看插入操作是否正确
 * @param {RBNode} root
 * @param {number} deep
 * @returns
 */
function inorder(root, deep = 1) {
  if (!root) return
  let tab = ''
  for (let i = 1; i < deep; i++) {
    tab += '\t'
  }
  root.left && inorder(root.left, deep + 1)
  console.log(
    '%c' + tab + root.val,
    root.color[0] === 'R' ? 'color:red' : 'color:black'
  )
  root.right && inorder(root.right, deep + 1)
}
const tree = new RBTree()
let arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
arr.forEach(v => {
  console.log(`------插入数据${v}------`)
  tree.insert(v)
  inorder(tree.root)
  console.log('--------------------')
})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

最后一次打印在控制台的输出如下：

插入的每一步可以在Red/Black Tree Visualization中进行验证插入的过程是否正确。

🍎 红黑树的删除操作

🍏 删除节点之前的准备工作

在开始删除红黑树的节点之前，我们先来前驱节点和后继节点，简单的说：

• 比当前节点小的那一个就是前驱节点；
• 比当前节点大的那一个就是后继节点；

如下图：

实现代码如下：

/**
 * 查找node的前驱节点
 * @author ywanzhou
 * @param {RBNode} node
 * @returns {RBNode} 前驱节点
 */
predecessor(node) {
  if (!node) return null
  else if (node.left) {
    let p = node.left
    while (p.right) {
      p = p.right
    }
    return p
  } else {
    // 如果删除寻找前驱节点是保证左右子树都存在的时候才找前驱或者后继
    // 这里的 else 只是为了寻找节点的前驱节点
    let p = node.parent
    let c = node
    while (p.left === c && p) {
      c = p
      p = p.parent
      return p
    }
    return null
  }
}
/**
 * 查找node的后继节点
 * @author ywanzhou
 * @param {RBNode} node
 * @returns {RBNode} 后继节点
 */
sucessor(node) {
  if (!node) return null
  else if (node.right) {
    let p = node.right
    while (p.left) {
      p = p.left
    }
    return p
  } else {
    let p = node.parent
    let c = node
    while (p.right === c && p) {
      c = p
      p = p.parent
      return p
    }
    return null
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

现在我们编写一个查找节点的方法，因为我们的删除是根据值来删除的，所以需要编写一个根据val来查找节点的方法：

/**
 * 根据val查找指定节点
 * @author ywanzhou
 * @param {number} val 要查找的节点的值
 * @returns {RBNode} 找到的节点
 */
findNode(val) {
  if (typeof val !== 'number') throw new TypeError('val is not a number')
  let p = this.root
  while (p) {
    if (val < p.val) {
      p = p.left
    } else if (val > p.val) {
      p = p.right
    } else {
      break
    }
  }
  return p
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

🍑 删除节点

红黑树的删除节点操作我们可以分为两步执行，分为删除节点和调整红黑树的平衡。

我们先来完成删除节点，删除节点可以分为三种情况，如下图所示：

在上面的图中，删除并没有考虑保持红黑树的平衡，现在我们来分别讨论一下：

首先是删除叶子节点的情况：

删除叶子节点分为两种情况，一种是不需要调整的，就是删除红色节点 ，直接删除就好，还有一种就是黑色节点，需要调整后在进行删除 。

然后就是删除存在一个子树的节点的情况，如下所示：

上图中也存在两种情况，一种就是删除红色节点，直接黑色节点代替还是能维护平衡，另一种就是删除黑色节点，需要删除后调整红黑树的平衡；

情况三就是删除具有左右子树的情况，这个时候找到前驱或者后继进行删除后，就会变成上面两种情况。

总之就是删除黑色节点需要调整平衡，红色节点可以直接删除；实现代码如下：

/**
 * 根据 val 删除红黑树中的节点
 * @author ywanzhou
 * @param {number} val 要删除的节点的值
 * @returns {number} 删除的节点中的val值
 */
remove(val) {
  const node = this.findNode(val)
  if (!node) {
    return null
  }
  const oldVal = node.val
  // 删除节点
  this.deleteNode(node)
  return oldVal
}
/**
 *
 * @param {RBNode} node 要删除的节点
 */
deleteNode(node) {
  // 删除节点
  // 1 存在左右子树的情况
  if (node.left && node.right) {
    // 1.1 找到前驱或者后继节点
    const sucessor = this.sucessor(node)
    // 1.2 将我们找到节点的值赋值给要被删除的节点
    node.val = sucessor.val
    // 1.3 将 node 指向后继节点，删除 node 即可（也就是删除前驱或者后继）
    node = sucessor
  }
  // 1.1 删除的节点是根节点，直接将 root 置为 null
  if (node.parent === null) {
    this.root = null
  }
  // 2 找到替换节点
  // 如果前面使用前驱节点则存在左子树，后继存在右子树，这里这么写可以兼容前驱或者后继
  let replacement = node.left ? node.left : node.right
  if (replacement) {
    // 2.1 说明存在左子树或者右子树，则不是叶子节点
    // 2.1.1 将 replacement 的 parent 指向 node 的 parent（认爹）
    replacement.parent = node.parent
    // 2.1.2 建立 left 或者 right 的引用（认儿子）
    if (node.parent.left === node) {
      node.parent.left = replacement
    } else {
      node.parent.right = replacement
    }
    // 2.1.3 清空node节点的所有指针（抛弃了所有人，等待被垃圾机制回收）
    node.left = null
    node.right = null
    node.parent = null

    // 2.1.4 调整红黑树的平衡
    if (this.#getColor(node) === BLACK) {
      // 只有删除黑色节点才需要调整平衡
      /**
       * 这里的replacement节点一定是红色，原因：
       * 红黑树中删除的节点对应 2-3-4 树中的叶子节点
       * 叶子节点只存在三种情况，也就是2节点3节点和4节点
       * 如果是2节点，则 replacement 不存在
       * 如果是3或者4节点，则 replacement 一定为红色节点
       */
      this.#fixAfterDeleteNode(replacement) // 基于前驱或者后继节点进行调整
    }
  }
  // 3 删除叶子节点
  else {
    // 3.1 说明不存在前驱或者后继，也就是叶子节点
    if (this.#getColor(node) === BLACK) {
      // 3.2 如果叶子节点是黑色，则需要调整红黑树的平衡
      this.#fixAfterDeleteNode(node)
    }
    // 3.3 删除叶子节点
    // 3.3.1 不认儿子
    if (node.parent.left === node) {
      node.parent.left = null
    } else if (node.parent.right === node) {
      node.parent.right = null
    }
    // 3.3.2 不认老爹
    node.parent = null
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

由于红黑树是由2-3-4树演变而来，删除时肯定是删除的2-3-4树中的叶子节点，如果不是叶子节点也需要转换为叶子节点删除，2-3-4树的叶子节点对应的就是红黑树的叶子节点以及叶子节点的上一层，所以说在红黑树中的删除永远只会删除叶子节点或叶子节点的上一层 ，如下图所示：

现在我们就正式开始分析：

情况一，当要调整的节点为红色时，直接染黑即可，如下图所示：

情况二，删除的节点没有子节点，可以从兄弟节点借一个过来：

这里的兄弟节点指的时转换为2-3-4树中的兄弟节点，如下图所示：

找到真正兄弟节点过程如下：

这里我们以要调整的节点是左孩子举例 (右孩子的话直接换个方向，逻辑与左孩子相同)；如果兄弟节点存在右孩子处理过程如下：

如果兄弟节点不存在右孩子处理过程如下：

情况三，兄弟节点不存在左右子树，此时需要从要调整的节点和兄弟节点依次减少一个黑色节点，直至黑色平衡为止，如下图所示：

实现代码如下：

代码中注释非常清楚，且经常与2-3-4树对比编写。

/**
 * 删除时调整树结构
 * @author ywanzhou
 * @param {RBNode} x
 */
#fixAfterDeleteNode(x) {
  // 1. 如果 x 节点不是根节点且颜色时黑色
  while (x !== this.root && this.#getColor(x) === BLACK) {
    // x 是左孩子
    if (x === this.#getLeft(this.#getParent(x))) {
      // 1.1 寻找兄弟节点 对应图 删除-02
      let rNode = this.#getRight(this.#getParent(x))
      // 1.1.1 如果兄弟节点为红色，则说明它不是真正的兄弟节点 对应图 删除-03
      if (this.#getColor(rNode) === RED) {
        // 1.1.2 将该节点染黑 父节点染红
        this.#setColor(rNode, BLACK)
        this.#setColor(this.#getParent(rNode), RED)
        // 1.1.3 将x节点的父节点左旋
        this.#leftRotate(this.#getParent(x))
        // 1.1.4 找到真正的兄弟节点
        rNode = this.#getRight(this.#getParent(x))
      }
      // 1.2 x 节点转换为2-3-4树，对应的兄弟节点为3节点或者4节点的情况
      if (this.#getLeft(rNode) !== null || this.#getRight(rNode) !== null) {
        // 如果存在左子树或者右子树则说明转换为2-3-4树为3节点或者4节点
        // 1.2.1 判断是否存在左子树，如果存在则变色旋转
        // 1.2.1.1 因为进入这个说明左右子树必须存在一个，如果右子树不存在则说明左子树一定存在
        if (this.#getRight(rNode) === null) {
          // 对应图 删除-05
          // 1.2.1.2 说明存在，先将左子树变黑
          this.#setColor(this.#getLeft(rNode), BLACK)
          // 1.2.1.3 将原本的黑色节点变红
          this.#setColor(rNode, RED)
          // 1.2.1.4 右旋
          this.#rightRotate(rNode)
          // 1.2.1.5 调整rNode
          rNode = this.#getRight(this.#getParent(x))
        }
        // 对应图 删除-04
        // 1.2.2 将兄弟节点变成父亲的颜色
        this.#setColor(rNode, this.#getColor(this.#getParent(x)))
        // 1.2.3 将父节点变成黑色
        this.#setColor(this.#getParent(x), BLACK)
        // 1.2.4 将兄弟节点的右节点变成黑色
        this.#setColor(this.#getRight(rNode), BLACK)
        // 1.2.5 沿着 x 节点的父节点进行左旋
        this.#leftRotate(this.#getParent(x))
        // 1.2.6 跳出循环
        break
      }
      // 1.3 x 节点转换为2-3-4树，对应的兄弟节点为2节点
      // 对应图 删除-06
      else {
        // 1.3.1 将兄弟节点变成红色
        this.#setColor(rNode, RED)
        // 1.3.2 移动x递归变色
        x = this.#getParent(x)
        // 1.3.3 如果 x 的节点不为黑色，则不会进入循环，而是执行 2 将其变成黑色，然后黑色继续保存平衡
      }
    }
    // x 是右孩子
    else {
      // 代码与上面一致，只是方向换了一下，为了兼容前驱和后继节点
      let lNode = this.#getLeft(this.#getParent(x))
      if (this.#getColor(lNode) === RED) {
        this.#setColor(lNode, BLACK)
        this.#setColor(this.#getParent(lNode), RED)
        this.#rightRotate(this.#getParent(x))
        lNode = this.#getLeft(this.#getParent(x))
      }
      if (this.#getLeft(lNode) !== null || this.#getRight(lNode) !== null) {
        if (this.#getLeft(lNode) === null) {
          this.#setColor(this.#getRight(lNode), BLACK)
          this.#setColor(lNode, RED)
          this.#leftRotate(lNode)
          lNode = this.#getLeft(this.#getParent(x))
        }
        this.#setColor(lNode, this.#getColor(this.#getParent(x)))
        this.#setColor(this.#getParent(x), BLACK)
        this.#setColor(this.#getLeft(lNode), BLACK)
        this.#rightRotate(this.#getParent(x))
        break
      } else {
        this.#setColor(lNode, RED)
        x = this.#getParent(x)
      }
    }
  }
  // 2. 因为要替换的节点一定是需要转换成黑色的，因为删除红色节点不会违反红黑树的平衡，所以不需要调整，凡是要调整的绝对是删除黑色节点需要补充黑色节点
  // 对应图 删除-01
  this.#setColor(x, BLACK)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

{完}

🍓 写在最后

本篇文章终于到这结束了，从头到尾肝了一周多，全文一共56张图片，除了一张是从维基百科上拿的剩下全部都是自己画了，麻烦看官给点个赞支持一下吧~