平衡的关键
书接前文。
在前文《二叉搜索树的本质》中我们提到，二叉搜索树在实践中有个很大的问题：树倾斜。按如下顺序插入数据会让二叉搜索树退化成普通链表，进而相关操作的时间复杂度退化到 O(n)：
怎样让这棵树在写操作后仍然保持平衡呢？
R 教授一边呷着黑咖啡，一边盯着这棵“畸形”的二叉树发愣。
“要怎样才能在添加新节点的时候不会破坏树的平衡性呢——或许应该这样问：添加新节点的过程是如何破坏树的平衡性的？”R 教授紧锁双眉喃喃道。
忽然，他两眼放光，好像发现了什么！
“对！问题就出现在这：向下生长。”R 教授发现，每次添加新节点，都会给现有的叶节点生成新的孩子节点，如此，每次添加一个新节点，都使得树的高度加 1，最终变成上图中的链表。
“那么，如果不让这棵树向下生长呢？”这是个大胆的想法。
比如，添加元素 2 时，不是作为节点 1 的孩子节点，而是和 1 放在一起（按序）呢？像这样：
如此，树便不再生长了，继续：
树高度是不再生长了，但有个问题：整棵树只有一个节点了，不就退化成数组了吗？
既然它叫树，就必然需要生长。
“既然它要生长，又不能向下长，便只能向上长了。”
如何让树向上生长呢？
回想一下前文《二叉搜索树的本质》中我们如何通过二分法将有序数组构造成二叉树？
我们取有序数组的中间元素作为父节点 P，将左右子数组分别作为 P 的左右子树，通过这种方式我们最终构造出了一棵平衡二叉树。
这里我们不妨也借鉴这种思想试试。
当节点中元素数量达到 3 个时，我们取中间的元素作为父节点 P，两边的元素分别作为 P 的左右子节点。
如上图，原来包含 3 个元素的节点裂变成了 三个节点，以该节点为根的子树高度加 1。
为啥选择在包含 3 个元素的时候裂变，而不是 2 个或者更多呢？我们选择在奇数元素数的时候裂变，好进行左右对称操作。3 是自然数中除 1 以外最小的奇数，操作起来足够简单（至少理论上是）。
我们当然可以选择在节点包含 n 个元素的时候裂变。
也就是说，在我们设计的这种裂变型的搜索树中，一个节点最多可以包含 2 个元素，最少包含一个元素。当元素数超过 2 个时便会发生裂变，导致树（可能）向上生长——向上生长的含义是，裂变过程产生的父节点 P 总是向上冒泡，它可能在上层生成一个新节点（当原本上层没有节点时），也可能和上层的节点合并（当原本上层有一个单元素节点时），也可能导致上层节点继续裂变（当上层原本是 2 元素节点时）。
在二叉搜索树中，每个节点 P 最多可以有两个孩子节点：左孩子的值小于等于 P 的值，右孩子的值大于等于 P 的值。在我们新型搜索树中，一个节点最多可以有两个元素，当有两个元素 a, b 时，是可以表示三个区间的：小于 a 的元素集合 [,a)、介于 a,b 之间的元素集合 [a,b) 以及大于等于 b 的元素集合 [b,)。所以，当某节点 P 有两个元素时，它最多可以有三个子节点（想象成有序数组中两个元素分割开的三个区域）。
因而，在这种新型搜索树中，一个节点最多可能有 2 个或者 3 个子节点，我们“望文生义”地给它起个名字就叫 2-3 树。
我们按照上面的思想按序插入 1 ~ 11 的元素，看看最终生成的 2-3 树是怎样的。
在上图中，我们总是将新元素添加到已有的叶节点中，而不是直接创建新节点，所以添加元素本身并不会导致树高度发生改变（甚至不会导致节点数量发生改变）。只是在添加新元素后，可能导致既有节点分裂，进而导致节点数以及数高度发生变化。
进一步，我们发现，只有一种情况会导致树高度增加：根节点分裂——当根节点填入第三个元素时，会将中间的元素提升作为新根，而该元素左右两边的元素分别裂变成左右子树。该过程是对称的（左右子树高度同时加 1），因而无论如何裂变，整棵树都是平衡的。
也就是说，通过自下而上裂变式生长，真的能保证搜索树的平衡性（至少插入元素时是这样）——发现这点后，R 教授乐坏了，赶紧开瓶香槟以示庆祝。
2-3 树的问题
R 教授一边呷着香槟一边试图实现这种神奇的搜索树。
不过在实现上他遇到了问题。
他发现这种看似很简单的数据结构，实现起来特复杂，需要分别考虑 2 节点和 3 节点的情况，写出来的代码又臭又长。
他在写删除逻辑的时候终于忍无可忍，将一大瓶香槟扔进了垃圾桶里。
“难道喝高了？不能啊，真理应该是简单的才对，这坨 SHIT 算个什么东西！”
于是他找来 L 教授帮忙。
“我觉得问题就出现在 2-3 上，它给人一种摇摆不定感。完美的设计应该是对称的。” L 教授故弄玄虚。
“但我没有什么好办法让它变成二叉树或者三叉树，一个节点在成为 3 节点之前必然要先成为 2 节点，所以这两种节点都必然会实际存在。”
“嗯，所以两类节点并存属于逻辑事实。” L 教授盯着面前的 2-3 树若有所思。
“不过我们能否在实现上消除一类节点呢——我的意思是，能否用 2 节点来表示 3 节点？”
“这是什么鬼？” R 教授疑惑地望着 L 教授。
L 教授解释道：“无论是 2 节点还是 3 节点，它们在逻辑上都是等价的：都是表示有序序列（有序数组），而且相互之间很容易转化。”
我们可以用如下三种代码来说明情况：
/**
* 最基本的数组表示法
*/
var arr = [...[-∞, a), a, ...[a, b), b, ...[b, ∞)]
/**
* 2-3 搜索树的 3 节点表示法
*/
var node = {
// 本节点元素数量
size: 2,
// 元素数组，升序排列
elements: [a, b],
// 子节点数组
// node1 子树中元素范围：[-∞, a)
// node2 子树中元素范围：[a, b)
// node3 子树中元素范围：[b, ∞)
children: [node1, node2, node3]
}
/**
* 二叉搜索树表示法
*/
var nodeB = {
element: b,
left: nodeA,
// nodeZ 子树的元素范围：[b, ∞)
right: nodeZ
}
var nodeA = {
element: a,
// nodeX 子树的元素范围：[-∞, a)
left: nodeX,
// nodeY 子树的元素范围：[a, b)
right: nodeY
}
L 教授画出如下草图：
“如此，便可以用 2 节点来表示 3 节点，只不过我们将 a、b 之间的连线用特殊颜色标记以示区分。也就是说，我们完全可以用二叉树来表示 2-3 树！” L 教授语调高亢，得意之神情溢于言表。
为了着重表示左边的 3 节点如何拆分成右边的 2 节点，L 教授将 a、b 之间的连线用红色笔画出。
“有点意思！” R 教授看到这里两眼放光，不知是因为喝高了，还是因为兴奋。
“所以待分裂的 4 节点可以用两条红线来表示。” R 教授顺着 L 教授的思路画了下图：
如上图，四节点可以用连续两条红线表示 a、b、c 之间的关系，不过由于最终不可能存在 4 节点，也就意味着不可能存在两条连续的红线，它最终会裂变成 3 个 2 节点。
“不过，这种转换有何用？我们不过是把 2-3 树又变成了二叉树而已。” R 教授兴奋过后两眼又泛起了疑惑。
“我们可以将 2-3 平衡二叉树的特性应用于等价二叉搜索树上，如此，理论上便能保持二叉树的平衡性——既然它是由 2-3 树转换来的。”
“不过在继续之前，我们先做个小小的优化。” L 教授继续道，“因为我们编码的时候是基于节点（而不是边）来编码的，所以我们可以将边的颜色转移给两端之一的节点——我们决定统一转给下端节点。”
如下图：
至此，这棵转换来的二叉搜索树中存在两种节点：红色节点和黑色节点。为了避免每次都叫“转换后的二叉树”，我们给它起个名字，不妨就叫红黑树吧。
“很形象的名字！”
红黑树的特性
我们前面已经得到了一个特性：由于 2-3 树中不可能存在 4 节点（拥有 3 个元素，4 个子节点的节点），对应地，红黑树中不可能存在两个连续的红节点。
“对，这是个显而易见却十分重要的特性。” R 教授接茬道，“另一个重要问题是：红黑树中如何表示 2-3 树的平衡特性，即所有的叶子节点到根节点的简单路径相等。”
L 教授盯着 2-3 树和转换后的红黑树思索良久，道：“2-3 树中所有叶子节点到根节点形成的简单路径上拥有的节点数量都相等。对于 2 节点，由于和红黑树中的（黑色）节点一一对应，不难处理；对于 3 节点，它在红黑树中其实由两个节点——一红一黑——构成，如果我们将这两个节点合二为一，那么红黑树中从任何叶节点到根节点的简单路径上节点数量也应该都是相同的。”
“也就是说，红黑树中，从任何叶节点到根节点的简单路径上，忽略掉所有红色节点后，剩下的节点——也就是黑色节点——数量是相同的。”
至此，我们得到了红黑树两条最重要的特性（核心特性）：
特性 1: 不能存在两个连续的红节点；
特性 2: 从任何叶节点到根节点的简单路径上的黑节点数量是相同的；
因为 2-3 搜索树的任何子树也是 2-3 搜索树，所以以上两条性质对于红黑树的任何子树也都成立。
另外，显而易见，树根节点一定是黑色的——因为它的上游不可能有节点跟它组成 2-3 树中的 3 节点。
特性 3: 树根节点是黑色的。
L 教授继续道：“我想再加个人为的限制。前面我们将 2-3 树转成二叉树的时候发现，那条红线既可以往左倾，也可以往右倾。为了处理方便，我们限制只能往左倾，也就是让两个元素中大的那个作为父节点（黑色），小的作为左子节点（红色）。这样的红黑树不妨叫左倾红黑树。”
特性 4: 红节点必须是其父节点的左子节点。
最后，我们将一棵 2-3 树用红黑树完整表示出来：
“嗯，性质 1 和 2 确实满足，不过有个大问题：转成红黑树后，树的平衡性被破坏了！” R 教授盯着这棵红黑树大失所望。
“的确。3 节点转成二叉树中的两个 2 节点后，有可能增加树高度。因为二叉树本质上仍然是自上而下生长的（而非自下而上裂变的），所以注定了它不可能是一棵完美的平衡树。我们所追求的是实践意义上的近似平衡性。” L 教授略显尴尬地解释道。
“嗯，那就将真理交给实践去检验吧。现在我们不妨探索如何添加和删除元素。”
插入元素
先看看插入元素 1.5。
在 2-3 树中的插入操作：
转成红黑树：
貌似很简单（先不管红黑树中为何 1 和 1.5 调换了位置）。
再看看插入元素 11。
首先找到相关叶节点 node(9,10)，插入 11 得到 node(9,10,11)，这是个 4 节点，会发生分裂，将 10 提升到上层构成 node(6,8,10)，这仍然是个 4 节点继续发生分裂，最终波及到根节点。如图：
在这个例子中，无论 2-3 树还是红黑树的结构都发生了很大的变化，看来这“级联炸弹”威力不小。
“虽然我们总能够先操作 2-3 树，然后将结果映射到红黑树，但这在实现上并不可行——到目前为止我尚未发现将 2-3 树转换成红黑树其实现意义何在。” R 教授一本正经。
“的确，如果红黑树不能降低 2-3 树在实现上的复杂性，便没有半毛钱的意义。所以我们必须从二叉搜索树本身来解决元素操作问题。不过，先容我喝杯咖啡提提神。” L 教授说着走向咖啡机。
神奇的三板斧
喝完咖啡，听了段莫扎特，两位教授继续研究红黑树。
插入或者删除节点后，必须对红黑树执行一系列操作来维护红黑树的特性。由于红黑树是二叉搜索树，所以操作后必须同时满足二叉搜索树的性质。
“我发现前面插入元素 11 后，虽然导致整棵红黑树结构变化很大，不过还是有规律的。我感觉好像将节点 4 围绕节点 8 逆时针旋转了一下，将 4 和 8 调换了父子关系，然后将 8 的左子节点给 4，整个二叉搜索树性质并未改变。” R 教授惊喜的说到。
“对！这真是个奇怪但有用的性质，我们不妨称它为左旋吧——因为被旋的节点在轴的左边。” L 教授补充道。
对应地就有右旋：
左右旋能保证二叉搜索树性质不变（请仔细分析上两图中字母大小关系，其中椭圆节点表示子树），如果在旋转中同时保证所涉及路径上的黑色节点数量不变，则旋转操作便可以用于维护红黑树性质。
另外还有一种显而易见的操作：颜色翻转。如图：
上图左侧，假设所有叶节点到根节点构成的简单路径上黑节点数量都相同，但 9 和 10 都是红节点，不符合特性 1。由于黑节点 8 的两个子节点都是红节点，我们将黑节点 8 和它两个子节点颜色交换，整棵树仍然满足红黑树性质。
接下来我们看看能否通过上面介绍的左旋、右旋和颜色翻转来维护红黑树的性质（包括二叉搜索树的性质）。
细谈插入
当我们向红黑树中插入一个新元素时，首先要决定该元素的初始颜色。
假设新节点初始化为黑色，那么它必然会导致某条路径的黑色节点数加 1，进而破坏红黑树性质。
如果初始化为红色，那么它本身不会导致黑节点增加（不违反特性 2），但可能会违反特性 1，即出现两个连续的红色节点（当其父节点也是红色时），但也有可能不违反任何特性。
所以我们决定让新节点初始化为红色，然后试图通过“三板斧”来修复特性 1。
场景一：待插入节点的父节点是黑色（有两种情况）：
注意上图第二种情况，左旋后，由于 x 原本的黑色转移给了其父节点 y，自己变成了红色，所有经过 x 的简单路径（也必然经过 y）上的黑节点数并没有发生变化。
场景二：待插入节点的父节点是红色（也有两种情况，不过我们可以通过左旋操作让其变成一种情况）：
我们将 x 的父节点 P 围绕 x 右旋看看情况：
如上图，右旋并适当调整节点颜色后，在保持二叉搜索树性质的前提下， α 子树和 β 子树中任何叶节点到根节点简单路径上的黑节点数量并没有发生变化，而且就图中几个节点而言，不再有两个连续的红节点了。
不过，我们得考察一下 α 子树和 β 子树。
由于原先 x 是红节点，所以 β 子树的树根必然是黑节点。然而 α 子树的树根既可能是黑节点也可能是红节点。
如果 α 子树的树根是红节点，则节点 P 的颜色违反了特性 1。
我们再观察节点 x、a、P 的颜色关系，发现可以翻转：
如图，翻转颜色后，不会改变 x 子树中任何一条路径上黑节点数量，而且解决了 P 和 α 子树可能的颜色冲突。
不过，细心的你肯定发现问题了。颜色翻转并没有解决问题，只是将可能的冲突从下面转移到了上面：翻转后，x 的颜色有可能跟其父节点颜色冲突（同为红色）。
另外，如果 x 是 x.parent 的右子节点，则违反了特性 3——不过这一点倒可以通过左旋解决。
因而，翻转颜色后，我们还要判断 x.parent 的颜色，如果是黑色则万事大吉，倘若是红色，则需要递归处理，直到整棵树的根节点。
透过现象看本质，场景二（连续两个红节点）情况下，我们的目的是让两个红节点向上合并成一个红节点以消除冲突。向上合并的过程有可能造成新的冲突（新的连续红节点），所以处理过程是递归的，有可能一直递归到整棵树的根节点。该向上合并的过程，类比到 2-3 树就是向上裂变的过程（因为连续两个红节点对应到 2-3 树上就是一个待裂变的 4 节点），裂变也是递归的，最终可能波及到根节点。
红节点合并与裂变的对应关系如下：
上图中一些特殊情况：
- 如果 P 节点不存在，则 b 会成为新的根（在红黑树中，需要将它再变成黑色）；
- 否则，在 2-3 树中，b 提升后至少会形成 3 节点，对应红黑树中红色 b 节点；
- b 提升后也可能形成 4 节点（当原本的 P 就是 3 节点时），此时会继续裂变，对应到红黑树中就是红色 b 的父节点仍然是红色；
最后一个问题是，当红色合并操作递归到整棵树的根节点时会发生什么？
答案是：直接将根节点变成黑色，然后结束战斗。
我们看看递归到根节点时的几种情况：
无论是哪种情况，将根节点变成黑色后都仍然满足红黑树的性质：
- 不存在连续的红节点；
- 当原本根节点是黑色时，自然没问题；
- 当原本根节点时红色时，变成黑色后，所有路径上黑节点数都加 1，仍然满足红黑树的性质；
再谈三板斧
从上面例子可知，当我们想将右倾红节点变成左倾红节点以满足特性 4 时要用到左旋，旋转后，父节点位置的颜色保持不变，原先右边的红色跑道左边去了。如图：
代码实现（TypeScript）：
/**
* 将 h 围绕其右子节点左旋。
* @returns 返回新的父节点
*/
function rotateLeft(h: Node): Node {
assert(h && h.right)
const x = h.right
h.right = x.left
x.left = h
x.color = h.color
h.color = 'RED'
return x
}
对称地，右旋如下：
代码实现：
/**
* 将 h 围绕其左子节点右旋。
* @returns 返回新的父节点
*/
function rotateRight(h: Node): Node {
assert(h && h.left)
const x = h.left
h.left = x.right
x.right = h
x.color = h.color
h.color = 'RED'
return x
}
颜色翻转代码实现：
/**
* 将 h 和其两个子节点执行颜色翻转
* 要求 h 的两个子节点颜色相同而且和 h 的颜色不同
*/
function flipColors(h: Node) {
assert(h && h.left && h.right)
assert(h.left.color === h.right.color && h.left.color !== h.color)
const hColor = h.color
h.color = h.left.color
h.left.color = hColor
h.right.color = hColor
}
经分析发现，以上三种操作既不会破坏二叉搜索树的性质，也不会导致任何一条“叶-根”路径上黑节点数量发生改变，近乎完美——除了可能导致出现两个连续的红节点（破坏特性 1），因而实际使用中需要自下而上递归处理。
插入操作的代码实现
至此，我们完整实现一下红黑树的元素插入代码：
interface Value {
key: number;
val: unknown;
}
/**
* 定义树的节点
*/
interface Node extends Value {
left: Node | null;
right: Node | null;
color: 'RED' | 'BLACK';
}
class RedBlackTree {
protected root: Node | null
// 树节点数量
protected _size: number
public constructor() {
this.root = null
this._size = 0
}
/**
* 插入元素
* 从根节点往下找，直到找到合适的位置后插入
*
* @param key - 关键字
* @param val - 卫星数据
*/
public insert(key: number, val: unknown) {
this.root = this.innerInsert(this.root, { key, val })
// 处理完成后，将根节点变成黑色，结束战斗
this.root.color = 'BLACK'
this._size++
}
/**
* 递归地往 p 子树插入元素 value，并维护红黑树性质
* @param p
* @param value
* @returns 返回子树 p 新的根（插入并维护红黑性质后，新的根节点不一定还是原来的那个节点了）
*/
private innerInsert(p: Node | null, value: Value): Node {
if (p === null) {
// p 子树是个空指针（空树），创建并返回新节点
return this.newNode(value.key, value.val)
}
// p 是非空子树，则视情况将 value 插入到 p 的左子树或者右子树中
if (value.key 删除
树形数据结构中，删除操作总是最复杂的，红黑树也不例外。
“初步看，删除得分两种情况：被删除的节点是叶子节点，或者是非叶子节点……”
“你等等，我好像发现了个重大问题！” R 教授突然打断了 L 教授的滔滔不绝。
“啥？”被这样硬生生地打断，L 教授显然有些不爽。
“你说叶子节点——这里有问题！” R 教授指着下面这棵红黑树：
现在删掉叶子节点 7，会怎样？
“嗯……不会怎样，仍然满足红黑树全部特性，换句话说，它仍然是一棵红黑树。” L 教授若有所思，他好像也意识到了什么。
“这正是问题所在，这棵树删掉节点 7 后仍然是一棵合法的红黑树，但它却无法转换成 2-3 树！” R 教授道。
所以我们必须保证任何一条路径不会因为删掉一个节点而消失。上图中如果路径（7-6-8-4）不因删除 7 而消失，那么删掉 7 以后这个路径便少了一个黑节点，从而不再满足红黑树的性质。
“或许我们可以引入哨兵——具体来说，我们让每个实节点都必须有两个子节点，如果没有，则用哨兵节点代替。为了不让哨兵的颜色影响实节点的颜色，哨兵节点必须是黑色（如实节点是红色，如果哨兵也是红色，则会违反特性 1）。” L 教授说道。
“这是个好主意。既然这些哨兵都出现在空节点的位置上，不妨就称这些哨兵为 nil 节点吧。” R 教授说着画出添加哨兵后的红黑树：
也就是说，特性 2 所提及的“叶节点”实际上是指哨兵节点（nil），而不是最下面的实节点。
2-3 树必须是完全平衡的搜索树，而上面这个（删掉节点 7 后）有问题的 2-3 树并不是一棵平衡树，不过这点从图中并不能明显地看出来，如果转成代码则较明显：
var node = { // 本节点元素数量 size: 2, // 元素数组，升序排列 elements: [6, 8], // 子节点数组 // node1 的值是 [5] // node2 是 null // node3 的值是 [9, 10] children: [node1, null, node3] }如上表示节点 node(6,8)，从 children 可见，第二个子节点是 null，而其它两个均有实际子节点，因而这里不再平衡。
所以，实际上在设计 2-3 树的时候就应该引入哨兵节点的概念了，如果 2-3 树引入了哨兵节点，那么转换为红黑树后，自然将哨兵的概念带过来了。
那么，我们如何删除上面的节点 7 呢？
我们知道，对于一条路径，删除路径上的红色节点不会影响路径上黑色节点数量。
所以，如果我们能先将节点 7 变成红色，然后再删除就行了。
如果节点 7 本身就是红色的，那么直接删除就行了。
如果节点 7 是黑色的（如上图所示），怎样将 7 变成红色节点呢？
我们只看节点 7 到根节点这条路径：
我们从这条路径的上游找一个红色节点（图中的 6）和节点 7 互换颜色，如此节点 7 变成了红色，且整条路径上黑色节点数量不变，然后再删除 7 即可。
不过，由于节点 6 变成了黑色，6 的左子树中所有路径的黑色节点数都多了一个，因而需要将节点 6 的左子结点也变成红色（即对节点 6 和其子节点执行 flipColors 操作）。
然而，如果整条路径上本来一个红节点都没有咋办呢？
可以将根节点变成红色——这相当于整棵树所有“叶-根”路径中黑节点数都减 1，红黑性质不变。然后在向下转移的过程中，根节点自然又变成黑色了。
如果要删除的节点不是叶子节点呢？比如如何删除节点 8？
在前文二叉搜索树中我们提过如何删除非叶子节点：将待删除节点和其后继节点（即比它大的最小节点）互换值，然后问题变为删除该后继节点——红黑树中后继节点是可以转换为叶子节点（这里指没有任何子节点的实节点）的。
此处只是描述了节点删除的大体逻辑思想，具体实现仍然是用前面提到的“三板斧”，而且实现代码要比插入逻辑复杂，此处不再给出完整代码实现，感兴趣可参见本人 github https://github.com/linzier/algo-ts 中红黑树的实现。
搜索
由于红黑树是二叉搜索树，所以可以直接用二叉搜索树的搜索逻辑实现。也就是说，节点的颜色并不影响搜索逻辑——这正是红黑树的一大优势。
总结
至此，我们在两位教授的帮助下，大体厘清了红黑树的演化过程：
- 找到二叉树倾斜的原因：向下生长；
- 阻止倾斜的策略：改变生长方向——采用裂变式向上生长策略；
- 基于 2，演化出 2-3 树；
- 由于 2-3 树实现上的复杂性，引出用二叉树表示 2-3 树的想法——红黑树；
- 基于 2-3 树的相关特性，总结出左倾红黑树的 4 条特性，其中特性 1 和特性 2 是核心特性；
- 基于二叉搜索树的特性，发现三个核心操作：左旋、右旋和颜色翻转——有了这三板斧，便可以完全脱离 2-3 树来处理红黑树的平衡性，至此红黑树有了实现上的可能；
红黑树的完整实现（TypeScript 版本）见本人 github：https://github.com/linzier/algo-ts。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
