文章来源

红黑树的定义

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点是黑色。
4. 如果一个节点是红色的，则它的子节点必须是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的。

平衡二叉查找树

我们以这样一个数组为例 [42，37，18，12，11，6，5] 构建一棵二叉搜索树，由于数组中任意一点都可以作为二叉搜索树的根节点，因此这棵二叉搜索树并不唯一，我们来看一个极端的例子（以 42 作为根节点，顺序插入元素）

在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。

为了让二叉搜索树不至于太“倾斜”，我们需要构建一棵 平衡二叉搜索树。

可以看出，平衡二叉搜索树的搜索时间复杂度为 O(log n)，避免了因为随机选取根节点构建二叉搜索树而可能造成的退化成链表的情况。它具有如下几个性质：

• 性质 1 可以是空树。
• 性质 2 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过

2-3 树

经过上面的例子，我们可以知道，构建一棵平衡的二叉搜索树的关键在于选取“正确”的根节点，那么我们如何在每次构建平衡二叉搜索树时都能选取合适的根节点呢，这里就要用到另一种重要的树：2-3 树（读作二三树），2-3 树和红黑树是等价的，理解 2-3 树对理解红黑树以及 B 类树都有很大的帮助。

所谓 2-3 树，即满足二叉搜索树的性质，且节点可以存放一个元素或者两个元素，每个节点有两个或三个孩子的树。

• 性质 1：满足二叉搜索树的性质
• 性质 2：节点可以存放一个或两个元素
• 性质 3：每个节点有两个或三个子节点

2-3 树本质上也是一棵搜索树，和二叉搜索树的区别在于，2-3 的节点可能存放 2 个元素，而且每个节点可能拥有 3 个子节点。

2-3 树存在以下两种节点：2-节点（存在两个子节点）和 3-节点（存在 3 个子节点）

下面我们来看如何创建一棵 2-3 树，创建 2-3 树的规则如下：

• 规则 1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上
• 规则 2. 四节点可以被分解三个 2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合

我们依然使用上面的示例数组[42，37，18，12，11，6，5]，依然使用顺序插入的方式来构建 2-3 树，看看是否会出现退化成链表的情况。

我们可以注意到，在创建 2-3 树的每一步中，整棵树始终保持平衡。

既然 2-3 树已经能够保持自平衡，为什么我们还需要一棵红黑树呢，这是因为 2-3 树这种每个节点储存 1~2 个元素以及拆分节点向上融合的性质不便于代码操作，因此我们希望通过一些规则，将 2-3 树转换成二叉树，且转换后的二叉树依然能保持平衡性。

2-3 树和红黑树的等价性

本小节我们以一棵 2-3 树为例，将其从 2-3 树转换成为一棵红黑树，从而学习了解 2-3 树和红黑树的转换规则，并体会 2-3 树和红黑树之间的等价性。

对于 2-3 树中的 2-节点来说，本身就和二叉搜索树的节点无异，可以直接转换为红黑树的一个黑节点，但是对于 3-节点来说，我们需要进行一点小转换：

1. 将 3-节点拆开，成为一棵树，并且 3-节点的左元素作为右元素的子树
2. 将原来的左元素标记为红色（表示红色节点与其父节点在 2-3 树中曾是平级的关系）

我们来转换一棵复杂点的 2-3 树，根据上边的两条转换规则，我们将 2-节点直接转换为黑色节点，将 3-节点拆成一棵子树，并给左元素标上红色，这个过程应该不难理解，另外我们可以注意到，由于红色节点是由 3-节点拆分而来，因此所有的红色节点都只会出现在左子树上。

红黑树的性质和复杂度分析

在完成了 2-3 树到红黑树的转换之后，我们重新审视红黑树的五条性质：

(1) 每个节点或者是黑色，或者是红色

这是红黑树的定义，没什么好说的。

(2) 根节点是黑色

根节点要么对应 2-3 树的 2-节点或者 3-节点，而这两者的根节点都是黑色的，因而根节点必然是黑色。从上图 2-3 树节点和红黑树节点对应关系就能很容易看出来

(3) 每个叶子节点是黑色

注意，这里的叶子是指的为空的叶子节点，上图的红黑树的完整形式应该是这样的：

(4) 如果一个节点是红色的，则它的子节点必须是黑色的

由于红黑树的每个节点都由 2-3 树转换而来，红色节点连接的节点必然是一个 2-节点或者 3-节点，而无论是 2-节点还是 3-节点，其根节点都是黑色的，因此红色节点的子节点必然是黑色的

(5) 从任意一个节点到叶子节点，经过的黑色节点是一样多的

这是红黑树最重要的一条性质，也是红黑树的价值所在。由于红黑树是由 2-3 树转换而来，因此每一个黑色节点必然对应 2-3 树的某个 2-节点或者 3-节点，因此红黑树的黑节点也能拥有 2-3 树的平衡性。

如果对这条性质还不够理解，可以对着上文 2-3 树和红黑树的转换图再理解理解。

红黑树时间复杂度分析

我们可以简单思考一下，对于一棵普通的平衡二叉搜索树来说，它的搜索时间复杂度为 O(log n)，而作为红黑树，存在着最坏的情况，也就是查找的过程中，经过的节点全都是原来 2-3 树里的 3-节点，导致路径延长两倍，时间复杂度为 O(2log n)，由于时间复杂度的计算可以忽略系数，因此红黑树的搜索时间复杂度依然是 O(log n)，当然，由于这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL 树）搜索效率要低一些。

既然红黑树的效率比 AVL 树的效率低，那么红黑树的优势体现在哪呢？

事实上，红黑树的优势体现在它的插入和删除操作上，红黑树的插入和删除相较于 AVL 树的性能会高一些，在后续红黑树的创建章节中，读者应该能够体会到红黑树在调整树平衡操作上的优势。

红黑树的创建

上文中我们讲解了如何由 2-3 树转换一棵红黑树，下面我们就来看看如何不经过 2-3 树直接创建一棵红黑树，毕竟我们写代码的时候不能先创建一棵 2-3 树再转化成红黑树吧。

我们回想一下 2-3 树的创建规则：

• 规则 1. 加入新节点时，不会往空的位置添加节点，而是添加到最后一个叶子节点上
• 规则 2. 四节点可以被分解三个 2-节点组成的树，并且分解后新树的根节点需要向上和父节点融合

简单来说，2-3 树的创建分为「融合」和「拆分」两步，为了实现这两步，我们需要在创建二叉树的基础操作上增加另外几个操作，分别是：

1. 保持根节点黑色
2. 左旋转
3. 右旋转
4. 颜色翻转

保持根节点黑色和左旋转

由于我们往 2-3 树插入节点时做的都是融合，因此新加入的节点和原位置的节点是平级关系，所以我们往红黑树里增加节点的时候，增加的都是红色节点。

我们插入第一个红色节点 42，哦吼，第一步就与红黑树的性质 2「根节点是黑色」冲突，为了解决这种冲突，我们将根节点变成黑色。

下面我们继续插入节点 37，同样的，新插入的节点都为红色

这里我们要思考一下，如果我们颠倒顺序，先插入 37 再插入 42 呢，是直接把 42 加到 37 的右子树上么，这显然是错误的，因为在前边 2-3 树转红黑树的过程中，我们已经了解到，所有的红色节点都只会出现在左子树上，因此我们需要进行左旋转，将节点的位置和颜色旋转过来。

上面是两个独立的节点，如果节点拥有左右子树，在旋转后仍然能满足二叉搜索树的性质吗，我们需要推广到一般情形。

我们来看一个例子：

经过以上几步，我们就完成了一般情形下的左旋转，我们可以对应地写几句伪代码，这里把 37 称作 node，42 称作 target

function leftRotate(node) {
  node.right = target.left;
  target.left = node;
  target.color = node.color;
  node.color = RED;
}
function flipColors(node) {
  node.color = RED;
  node.left.color = BLACK;
  node.right.color = BLACK;
}
function rightRotate(node) {
  node.left = T1;
  target.right = node;
  target.color = node.color;
  node.color = RED;
}
function add(node) {
  //如果右节点为红色,左节点为黑色, 那么进行左旋转, 对应情况2
  if (isRed(node.right) && !isRed(node.left)) node = leftRotate(node);

  //如果左节点为红色,左节点的左节点也为红色, 那么进行右旋转, 对应情况3
  if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node);

  //如果左右节点都为红色, 那么进行颜色翻转, 对应情况4
  if (isRed(node.left) && isRed(node.right)) flipColors(node);
}