rbtree.jpg

一. 算法之变，结构为宗

计算机在很多情况下被应用于检索数据，比如航空和铁路运输业的航班信息和列车时刻表的查询，都要求快速地找到用户所需要的信息。所以，对于存储大量信息的计算机来说，能“大量存”固然好，但同时还必须能“快速取”才行。又比如，我们在使用C++或者Java这样的编程语言时，都会用到标准模版类库，因为它们简洁高效，能提供动态增长的各类数据结构，极大地提高了开发效率，同时又保证了健壮性。那么，再深入一点看这个问题，究竟是什么“神秘的力量”，在持续地彰显这些卓越的“行为”呢？
答案是：“结构模式影响行为”。

“当置身于同一个系统时，其中的事物无论有多大差别，都倾向于产生相似的行为结果。”

所以你看，在这些高效卓越的检索能力背后，一定存在着一个隐藏在事物表面以下的“结构”，正是因为这个内部结构的存在影响着外部行为的表现，不同的结构产生不同的影响力，当然也就有好坏之分。

“万变不离其宗”，很多时候我们在学习和积累的过程中，特别是遇到很多很“复杂”的问题时，总是有着一种深深的挫败感，这种巨大的挫败感，来自于我们无法把握瞬息万变的外在行为。变化的永远是外部的行为，不变的永远是内部影响这些行为的结构。因此，我们必须抛开让人眼花缭乱的外部行为，去洞察事物的内部结构，去把握这个“宗”，这往往有着意想不到的收获。

为了提高搜索效率，人们想到了用二叉搜索树（Binary Search Tree）这样的非线性数据结构来存储数据，每次检索数据时根据关键字的大小选择是往左子树走还是往右子树走，这样每次都少比较了一半的数据，这样就比线性搜索效率高了。但是，采用“树”的数据结构，就产生了这样一种行为影响：检索的过程是跟着树的路径往下走的，因此树的高度会对效率产生影响，如果恰巧某个搜索路径比较“深”，那么查找就比较费时间了，因此不能保证在所有情况下都有很好的效率，打个比方，如果将事先已排好序的序列作为输入建立一棵二叉搜索树，那么得到的结构可能就变成了图1所示这个样子：

图1-1 极不平衡的二叉搜索树

如果在这样的BST上搜索数据，其效率就变成了O(n)，就变得很坏。那么自然就有了一种想法：能不能在BST的结构上进行某种“改进”，让它的根结点到树中任意叶结点的路径都差不多一样长呢？如果能做到这样的优化结构，那么其所表现出来的行为（也就是搜索效率）必然会得到改善和提高。2-3-4树正是在这样的背景下提出的。

二. 平衡之美：2-3-4树

2-3-4树有完美的平衡性能——根结点到任意叶子结点的路径长度相等。“2-3-4树”名称的来历是因为这棵树包含了三种结点：2-node、3-node和4-node。

• 2-node：有1个关键字，2个子结点；
• 3-node：有2个关键字，3个子结点；
• 4-node：有3个关键字，4个子结点。

图2-1 2-node 图2-2 3-node 图2-3 4-node

如图2-1，2-node的左孩子关键字小于W，右孩子关键字大于W；图2-2中孩子结点从左到右，分别是小于C，介于C和E之间以及大于E的；图2-3中的4-node类似。

2.1 2-3-4树的查找操作

先看查找操作，查找的过程就是比对关键字大小，然后沿着某一路径向下搜索，直到找到对应结点，或者当找不到时返回“空”，如图2-4所示。

图2-4 查找关键字为L的结点

2.2 2-3-4树的插入操作

现在来看看插入操作：首先仍然是按照关键字大小沿着树的路径向下，当到达2-node或者3-node时，直接“扩充”这个结点——2-node扩充成3-node，3-node扩充成4-node，如图2-5，2-6，2-7，2-8所示。

图2-5 插入关键为B的结点之前 图2-6 插入关键字为B的结点之后 图2-7 插入关键字为X的结点前 图2-8 插入关键字为X的结点后

但是，如果插入的位置落在一个4-node内，就出现问题了，因为我们既不能把4-node再扩充成5-node，也不能把新加入的结点直接挂在这个4-node下，因为这样就破坏了2-3-4树完美的平衡性质——根到任意叶结点的路径相同，如图2-9所示。

图2-9 既不能继续扩充4-node，也不能直接将关键字为H的结点直接挂在下面

那么遇到这种情况怎么办呢？我们的解决办法是采取分解（split）策略——将4-node的3个关键字中间那个“向上提”，把它合并到这个4-node的父结点中，这个4-node被分解为两个2-node，如图2-10所示。

图2-10 包含关键字“FGJ”的4-node被分解，关键字为G的结点“上提”

然后，我们再将关键字为H的结点插入，即得到了图2-11所示的样子，注意，此时2-3-4树的完美性质仍然保持。

图2-11 插入关键字为H的结点后

但是新的问题又产生了喔！仔细想想，如果图2-12这种两个4-node连接在一起的情况发生了该怎么办。

2-12 两个4-node连接在了一起

有两种策略解决这个问题——分别称为Top-down和Bottom-up。
Bottom-up策略是，如果分解4-node时发现它的父结点仍然是4-node，就继续分解，如果有必要的话，这个过程一直持续往上走，直到到达根结点为止，它是“自底向上”的分解策略。
Top-down策略是，在执行插入操作时，沿树往下走的路径上，只要发现4-node，就对其进行分解，并在底部插入新结点，它是“自顶向下”的策略。
这里我们采用Top-down策略，也就是说，在沿着树向下的过程中，只要发现4-node就将其分解，因此我们就保证了当前结点一定不是4-node，这样就保证了图8这种情况不会出现，并且我们最后能落在2-node和3-node中，如图2-13所示。

图2-13 分解遇到的4-node

这样的分解操作只涉及当前结点和其父结点，因此是局部的操作，不会将调整结点的影响扩散到其他地方，这里的这个“分解”的概念很重要，一定要认真体会和理解，这牵涉到后面对红黑树很多调整操作的理解，其实红黑树的各种调整操作其本质都来源于2-3-4树。
好了，写到这里，如果你真正理解了“分解”的概念以及为什么要分解，那么我们就来看一个具体的例子，如图2-14，2-15所示，输入序列为“ASERCDINBX”,建立一棵2-3-4树的过程，注意在插入R，N，B和X这四个关键字时都发生了4-node的分解，其中前三个关键字是因为所插入的结点落在4-node中，必须分解；最后一个关键字是因为在沿着树根向下的过程中遇到4-node了，对其进行分解（还记得Top-down策略吗）。

2-14 一棵2-3-4树的成长 2-15 一棵2-3-4树的成长

2.3 完美平衡的2-3-4树

一棵稍微复杂一些的2-3-4树如图2-16所示，这种完美的平衡感，保证了根到任一叶结点的路径不会比其他路径长得太多，也就保证了搜索和插入操作能够在对数时间内完成，最坏情况下（全是2-node），其渐进时间复杂度为lgN，最好情况下（全是4-node），其渐进时间复杂度为log4(N)=1/2lgN，10到20次操作就能完成对100，0000个结点的搜索和插入操作。这就是“优美”的结构所产生的卓越能力。

2-16 完美平衡的2-3-4树

但是，不要高兴得太早了，凡事有得必有失，2-3-4树的性能虽然接近完美，但是实现起来却很困难，原因很简单——要实现这三种结点，还要实现三种结点之间的相互转换相当困难。实际上，2-3-4树的理论意义要强于实际意义，因为还有一种著名的数据结构也是从2-3-4树衍生出来的，那就是在数据库领域使用非常多的“B树”，那么，面对这样一种完美的数据结构，我们是不是束手无策了呢？也不见得，下面，就轮到红黑树登场了。

三. 红黑树的崛起

从某种意义上说，红黑树是2-3-4树的一种“精神表达”，其实这也不奇怪，只有神才能创造出完美无瑕的事物，作为人类，要将完美的东西变成现实，必须根据实际情况稍作修改和牺牲。不先弄懂2-3-4树，是很难理解红黑树的各种操作的，但是如果理解了2-3-4树，你就能明白，纷繁复杂的红黑树旋转和颜色翻转的操作其实就是为了恢复因插入或删除结点而造成的2-3-4树性质的破坏，所以，在我们进入具体的红黑树讨论之前，如果你对2-3-4树还有什么不了解的地方，请不要急躁，再回过头去好好看看前面的叙述；如果你准备好了，那么我们开始走进红黑树吧。

3.1 红黑树的基本性质

《算法导论》一书叙述了红黑树的经典五条性质：

“一棵二叉查找树如果满足下面的红黑性质，则为一棵红黑树：

1. 每个结点是红的，或是黑的；
2. 根结点是黑的；
3. 每个叶结点（NIL）是黑的；
4. 如果一个结点是红的，则它的两个儿子都是黑的；
5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。”

其实，如果自己总结一下，红黑树的性质大概可以归纳成以下4条：

1. 要么红，要么黑；
2. 一头一尾都是黑；
3. 有红必有黑；
4. 任意路径上黑结点个数稳定。

你也许会认为，这就是红黑树的本质了，的确《算法导论》一书对红黑树所有操作的叙述，其实就是在保持上面红黑树的五条性质，但是这本书却没有回答两个问题：

1. 为什么要对结点进行染色？
2. 为什么染色后的二叉查找树的效率就提高了？

3.2 红黑树的本质

不搞懂2-3-4树，你永远无从知晓这个问题的答案。现在，让我来告诉你什么是红黑树的本质。

红黑树的真正本质是要将2-3-4树“表达”成二叉搜索树，2-3-4树有三类不同的结点，二叉搜索树只有一类结点——2-node，因此主要的问题，就是考虑怎么把3-node和4-node“表达”成2-node，而“红边”的引入，使这个问题的解决成为可能。事实上，在一棵红黑树中，结点是无所谓红色还是黑色的，被染色的不是结点，而是连接结点的边！，读过《算法导论》的同学都知道，书上对红黑树的描述都是说对结点染色，但是真正的红黑树其实是对边区分红色和黑色，因为我们在实现具体的数据结构时，主要是实现结点的数据域，而边的关系是通过指针来描述的，因此就把边的颜色值放到结点的域中。

• 当我们说一个结点是红色时，实际上是指连接它的边是红色；
• 当我们说一个结点是黑色时，实际上是指连接它的边是黑色。

3.3 红黑树与2-3-4树的基本对应关系

好了，前面的铺垫有了，我们回到正题——红黑树是怎么把2-3-4树中的3-node和4-node表达成2-node的？答案是：通过“红边”。也就是说，红边是“内部边”，黑边是“外部边”，红黑树中的黑边与2-3-4树中的边一一对应；而红黑树中的红边在2-3-4树中看不见——因为红边是3-node和4-node的内部边。这个概念很重要，后面还要再次提到它，所以请你把她记在心里。引入红边后，3-node和4-node就被表达成如图3-1，3-2这样的BST结构。

图3-1 3-node的BST表示 图3-2 4-node的BST表示

于是，通过红边和黑边的帮助，我们就在红黑树和2-3-4树之间建立了一个对应关系（请注意，只是对应关系，我没有说是“一一对应”关系，其实如果细心观察的话，这个从图3-1中你就可以看出来了，这会引出后面一个问题的讨论）。一棵2-3-4树在经过红黑边的诠释过后，就成了图3-3中的这个样子。

图3-3 用红黑诠释的2-3-4树

（*注：我觉得这张图是错的，右子树应该是G在上面，F在左下，J在右下才对，下图也是同样的问题，不过将就用吧，心里有数就好了。）

这并不是唯一的表达方式，事实上，同一棵2-3-4树还有以下三种表达，如图3-4所示。

图3-4 同一棵2-3-4树的另外三种不同表达

这可就麻烦了啊，2-3-4树和红黑树居然没有一一对应！那得考虑多少种不同的等价情况啊，有的情况完全是左右对称的——这也是《算法导论》一书让人费解的原因，因为大量的代码都用来处理各种情况了，所以读起来让人甚是费解和疑惑。但是仔细观察，这四种不同表达的关键因素在哪？就是红边！红边可以左斜（Left-Leaning），又可以右斜（Right-Leaning），所以导致4种情况的组合（根据概率论的乘法原理），所以，为了消除这些不必要的复杂情况，我们只研究其中一种：左旋红黑树。

四. 左旋红黑树（LLRB）

于是左斜红黑树（Left-Leaning Red Black Tree）登场了。左斜红黑树中，所有的3-node其内部的红边都是向左倾斜的，这就是LLRB名称的由来，如图4-1所示。

图4-1 3-node的左旋表示

这样我们不仅保证了完美的黑边平衡（因为它本质上是2-3-4树），同时也保证了2-3-4树与其红黑表示的一一对应关系，如图4-2所示。

图4-2 2-3-4树的LLRB表示

呃，读到这里大家肯定会有个疑问，2-3-4树看起来是挺漂亮的，但是咋一看红黑树里的红边怎么这么扎眼啊？2-3-4树的红黑表示似乎让树“变高”了，那么同学们肯定会问：红黑树还能保持2-3-4树的对数时间效率么？

4.1 搜索效率的数学证明

让我们用一点点数学分析来回答这个问题吧。
引理：一棵有n个内结点的红黑树的高度至多为2lg(n+1)。
这个定理由《算法导论》一书引出 ，看起来特别的抽象，不好理解，不过没关系，下面就由我带领各位来体验一把书上的证明，我会把书上一些写的不清不楚、一笔带过的东西重新诠释一下，这样这个定理就不难理解啦！
那么要证明这个定理呢，我们需要另外一个工具，描述如下：
“对以x为根的子树，它所包含的内部结点数至少为2^[bh(x)]-1（2的bh(x)次方然后再减一）。”这里bh(x)被定义为结点x的黑高度，就是说，从结点x（不包括它本身）到它任一个叶结点的路径上所有黑色结点的个数。
这里我们用数学归纳法来证明这个工具。

1. 基本步：若x高度为0，那么它就是一叶子结点，它确实至少包含2^0-1=0个内部结点，基本步证明完毕；
2. 归纳步：假设x为红黑树的某一内部结点，且它高度h>0，那么它的黑高度就是bh(x)，但是它的两个孩子结点呢？这个就根据它们的颜色来判断了：
   如果x有一个红色的孩子y，那么y的黑高度bh(y)=bh(x)，看看上面对黑高度的定义你就明白了——既然它是红色的，那么它的黑高度就应该和它父亲的黑高度是一样的；
   如果x有一个黑色的孩子z，那么z的黑高度bh(z)=bh(x)-1，这个怎么解释呢，因为它自己就是个黑结点，那么在计算它的黑高度时，必须把它自己排除在外（还是根据定义），所以它是bh(x)-1。
   现在关键的来了：x的孩子结点所构成的子树的高度肯定小于x这颗子树，那么对于这两个孩子，不管它们颜色如何，一定满足归纳假设的，所以，对x来说，它所包含的内部结点个数“至少”为两个孩子结点所包含的内部结点数，再加上它自己，于是就为2^{[bh(x)-1]-1+2}[bh(x)-1]-1+1=2^[bh(x)]-1，归纳证明完毕。好了，工具拿到手上了。

现在该干什么呢？对！现在该完成对原引理的证明啦，不过在此之前，我们先来回顾一下红黑树的五个性质。

1. 每个结点或者是红的，或者是黑的；
2. 根结点是黑的；
3. 每个叶结点（NIL）是黑的；
4. 如果一个结点是红的，则它的两个儿子都是黑的；
5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

相信不断地重复能让人记得更牢，从特性4）我们知道，如果有一个红结点存在，那么它的两个子结点一定是黑的，最极端的情况下，该路径上所有的结点就被红、黑两种结点给平分了，所以，我们可以说，对于任意一棵红黑树，从它根结点到任一叶结点的路径上黑结点的个数至少占到了一半，不知这个问题我解释清楚没有，因为这是往下理解的关键。
如果一棵红黑树的高为h，那么在这个高度上（不包括根结点本身）至少有1/2h的黑结点，再结合上面对“黑高度”的定义，我们说，红黑树根结点的黑高度至少是1/2h，好了，现在拿出上面那个工具，设n为该红黑树所包含的内部结点数，我们得出如下结论：
n>=2^(1/2h)-1

我们把它整理整理，就得到了h<=2lg(n+1)，就是我们要证明的结论：红黑树的高度最多也就是2lg(n+1)。

现在明白为啥红黑树的效率还是很高了吧，因为这些操作在一棵高度为h的二叉查找树上运行时间为O(h)，而包含n个结点的红黑树是高度为O(lgn)的查找树，所以相关的操作还是能在对数时间内完成，这下我们就可以放心了。

4.2 必须要避免的两种情况

刻意地让红边向左倾斜，就要考虑新结点插入后的边的调整问题，因为可能会产生两种不允许的情况出现。稍后将会看到，每次插入的新结点都是用红边去连接它的（就是说插入的默认都是红结点，然后再根据情况进行调整），那么如果插入的结点恰好作为其父结点的右子结点的话，树中就有右斜的红边了，这是第一种不允许的情况，如图4-3所示。

图4-3 右斜的2-node

第二种不允许的情况是，如果插入的新结点，其父结点也是红边连接的，那么在一条路径上就出现了两个连续的红边，这叫“two reds in a row”，这也是不允许的（回忆一下《算法导论》一书经典的红黑定义——红结点的孩子必定是黑结点），四种不允许的情况如图4-4所示。

图4-4 Two Reds In A Row

好了，这里总结一下，我们的LLRB是一棵特殊的红黑树结构，它不允许下面两种情况出现：

1. 右斜的红边；
2. 两个连续的红边出现在一条路径上。

注意喔！标准的红黑树是允许情况1出现的，因为这里实现的是LLRB，是红边向左倾斜的，所以这种情况也不允许了——这可以简化很多对称结构的讨论！好了，理论准备足够充分之后，我们下面要展开对具体编程实现的讨论，在具体的编程语言实现中结合代码来分析红黑树的各种旋转和调整操作，在此之前，仍然希望你先看懂上面的讨论，如果你准备好了，那么我们继续深入到代码层吧！

五. LLRB的Go语言实现

5.1 数据结构

我们先来看看红黑树的数据结构，这里设计的红黑树的结点由6个域组成：键、值、颜色（红或者黑）、父结点，左子结点和右子结点，即一个六元组<key, value, color, parent, left, right>。其中为了提高程序的通用性，我们把关键字和对应值的类型分别定义为KeyType和ValType，并将颜色值（RED和BLACK）和布尔值（TRUE和FALSE）定义成常量。然后我们使用一个head指针作为整个红黑树的头部，head指针的右子结点指向红黑树的树根。

type rbnode struct {
  key, value interface{}
  red bool
  left, right *rbnode
}

type RBTree struct {
  root *rbnode
  length int
  less func(a, b interface{}) bool
}

5.2 debug方法论

只要跟编程打交道，就绝对少不了debug，不论你考虑得再怎么仔细，bug总是存在的，不过呢，我们总是有方法来尽量减少bug的出现，尽量提高程序的健壮性，下面就来介绍一下我debug的三件法宝吧。

5.2.1 防御性编程（Defensive Programming）

工程师最有力的武器，永远是自己的大脑。不要急着编写代码，写之前一定要仔细地考虑好，借用莫扎特那句名言：

“Everything has been composed, just not yet written down.”

思想应该是先在大脑中构思充分并反复推敲之后，再考虑它在现实世界的成形。至少考虑好三件事，首先我这个函数要实现什么功能？如果你发现你的函数完成了两个或以上的功能，那还是重构一下好一些，最好一个函数只做好一件事，这符合UNIX的设计哲学；其次，这个函数的执行需要满足什么先决条件（precondition）？是不是一定要保证在某些指针变量不为空的前提下执行？注意喔，在执行具体操作之前检查先决条件就是防御性编程的精髓！否则如果不满足条件就执行，最后可能会得到一些莫名奇妙的结果，到时候再调试，你找都找不到问题出在哪儿，所以，考虑清楚先决条件不仅减少了很多不必要的麻烦，同时也为后来的单元测试提供便利：认真检查先决条件就是了；最后，就是后置条件（postcondition）——你这个函数执行了什么改变？函数执行后得到什么结果？把这三个因素都考虑清楚了，能极大地提高代码的健壮性，一般呢，我会将函数的一个简短的描述以及先决条件和后置条件写成注释放在函数的开头。

func function(/* parameter list*/) {
  /*
  * DESC: function described here
  * PRE: function's preconditions
  * POST: function's postconditions
  */

  // CODE...
}

5.2.2 测试驱动开发（Test-Driven Development）

此方法来源于敏捷思想，具体地说，就是先写测试，然后用测试来驱动开发。在构思好模块的功能后，我们可以先将测试代码写出来，然后我们剩下的工作就是围绕测试代码来展开：编写正确的代码，使得测试通过。Bob大叔在他的大作《敏捷软件开发——原则、模式与实践》一书中谈到了TDD的好处有如下几点：

程序中的每一项功能都有测试来验证它的操作的正确性；
迫使我们站在调用者的观察角度，关注功能的同时也关注了接口；
迫使自己把程序设计为可测试的，可测试性使得程序与其他部分解耦合；
测试代码是一种无价的文档形式。

因此，往后对红黑树的讨论就采取TDD的方法，先写测试，再写代码，每完成一个功能就运行测试代码看看结果，直到能够正常结束并得到正确的结果为止，然后再编写新的测试和新的功能并与以前的测试代码一起运行，这个过程一直持续到整个开发结束，这样保证了新添加的功能不会影响到以前编写的代码，。

5.2.3 gdb调试器

这个是每一个Linux程序员必知必会的强大工具了，使用它，可以反汇编、单步执行、设置断点、设置观察点.

5.2.4 创建红黑树、新建结点和判断结点颜色

对于创建红黑树的操作，我们希望该树在创建时是一棵“空树”。然后我们就着手编写NewRBTree()的代码吧，如下所示。

func NewRBTree(less func(a, b interface{}) bool) *RBTree {
  return &RBTree{
    less: less,
  }
}

然后是判断结点颜色和创建红黑树结点的操作。要注意当相应结点为nil时，返回FALSE，这个nil结点代表叶子结点。本文中所画的红黑树都是内结点，即含有键值对的结点，而真正的叶结点是空结点，不含键值对。回忆一下，按照红黑树的定义叶子结点必须是黑结点（性质3），故返回false。

func isRed(node *rbnode) bool {
  return node != nil && node.red
}

func newRBNode(k, v interface{}) *rbnode {
  return &rbnode{
    key: k,
    value: v,
  }
}

5.2.5 左旋、右旋和颜色翻转

对红黑树的相关操作（如插入，删除）本质上都是基于对二叉查找树的操作，但是，在红黑树的上下文中，相关操作有可能会破坏红黑性质，因此，必须对被破坏的性质进行“修复”，而左旋（left-rotating）、右旋（right-rotating）和颜色翻转（color flip）就是对红黑树进行修复的操作。但是修复并不是毫无章法的，对于不同的情况要采取不同的修复策略，相应情况和对应修复策略如图4-5所示。

图5-1 三种情况及对应修复策略

理解为什么要旋转调整的关键，在于将2-3-4树与其相应的红黑表示联系起来看。这里以插入操作为例（删除操作类似），图25中红圈所示情况为我们有一个新插入的结点插入到了2-node的右孩子处，此时在对应的红黑表示中红边被右旋，于是我们就用左旋操作来恢复LLRB“红边左斜（left-leaning）”的性质；当插入的结点作为3-node的最左孩子时，对应的红黑表示如图中蓝圈所示，此时我们只要将其右旋即可；而当新插入结点作为3-node的中间孩子插入时，此时对应的红黑表示如图中黄圈所示，这时我们先执行一个左旋操作转换成蓝圈所示情况，然后再执行一个右旋即可。那么为什么要执行颜色翻转呢？回忆一下，上面我们在讨论2-3-4树的时候，谈到了4-node的分解，而颜色翻转的操作，就是为4-node准备的。理解的关键，还是要把2-3-4树和它对应的红黑表示联系起来，如图4-6所示。

图5-2 颜色翻转的演示

颜色翻转之后，图4-6中原本由M、E和Q共同组成的4-node就被拆分了，E和Q分别形成一个2-node，而M结点由于被红边连接而“融入”到了上面的结点中——如果M的父结点是2-node，则此时该父结点变成3-node，这一共有2种情况；如果M的父结点是3-node，那么此时该父结点变成4-node，这一共有3种情况，如图4-7、图4-8所示。

图5-3 当父结点是2-node时的两种情况 图5-4 当父结点是3-node时的三种情况

好了，理论到此为止，下面开始贴代码，注意，旋转操作只旋转红边。

func rotateLeft(node *rbnode) *rbnode {
  rightChild := node.right
  node.right = rightChild.left
  rightChild.left = node
  rightChild.red = node.red
  node.red = true
  return rightChild
}

func rotateRight(node *rbnode) *rbnode {
  leftChild := node.left
  node.left = leftChild.right
  leftChild.right = node
  leftChild.red = node.red
  node.red = true
  return leftChild
}

func colorFlip(node *rbnode) *rbnode {
  node.red = !node.red
  if node.left != nil {
    node.left.red = !node.left.red
  }
  if node.right != nil {
    node.right.red = !node.right.red
  }
  return node
}

六. 红黑树的插入操作

有了上述的三个辅助函数，我们现在可以来讨论一下红黑树的插入操作，红黑树的插入算法可以分成两个基本部分：一是以二叉查找树为基础的结点递归插入操作，这里对已经存在的关键字更新其相应的值，而对于原来树中没有的关键字新建红结点进行插入；二是对树进行“修复”操作。

6.1 插入操作的分情况讨论

为了方便理解，还是把插入操作分解成以下六种情况吧：
情况1：若新插入的红黑结点关键字并不存在于原来的红黑树中，那么将该结点插入到树的底部（否则更新对应关键的值），如图6-1所示；

图6-1 插入新结点（可能在左边也可能在右边，后者破坏LLRB性质）

情况2：在沿树根向下递归的过程中若发现当前结点是4-node，则分解它，判断当前结点是否为4-node，就是看它的左子和右子结点是不是都是红色，如图6-2所示；

图6-2 分解4-node

情况3：若新插入结点的关键字小于当前结点关键字，则插入其左子树中（递归）；
情况4：若新插入结点的关键字大于当前结点关键字，则插入其右子树中（递归）；
情况5：遇到向右倾斜的红边，将其向左旋转，如图6-3所示；

图6-3 左旋以修复LLRB性质

情况6：遇到两条红边在一条路径上，对其进行平衡，如图6-4所示；

图6-4 平衡4-node

这六种情况是按顺序安排的——即我们的插入算法即按照情况1到情况6的先后顺序来执行代码的。

6.2 红黑状态修复

情况2、情况5和情况6都是对插入新结点后红黑树性质的修复，考虑到后面的删除操作也需要进行相应的修复操作，这里就使用了一个小技巧，我们把2，5和6三种情况稍微调整一下顺序，并重构到一个函数中，统称为“fixUp”。

func fixUp(node *rbnode) *rbnode {
  if isRed(node.right) {
    node = rotateLeft(node)
  }
  if isRed(node.left) && isRed(node.left.left) {
    node = rotateRight(node)
  }
  if isRed(node.left) && isRed(node.right) {
    node = colorFlip(node)
  }
  return node
}

注意，这里有一个非常重要的细节上的不同就产生了。本来，如果我们按照先前介绍的顺序执行情况1到情况6，那么我们就是在自顶向下地边插入新结点边修复红黑树性质，而当我们将修复的操作重构成fixUp()函数并在插入操作完成后执行，就变成了自底向上地“事后修复”红黑性质了！非但如此，我们还引入了两个细微但是至关重要的不同点，仔细观察上面的代码，你会发现两个问题——首先是对4-node的拆分操作被放到了两个旋转调整操作的后面，这样一来，我们的LLRB就不再是对2-3-4树的表示了，而是对2-3树的表示！因为沿路径向上的4-node全部被提前分解，不存在4-node了！这是只看代码不容易察觉的差别；然后就是多了个语句判断该结点的父结点是不是head，若是的话就将其染黑，这是因为在我们沿路径向上不断修复红黑性质的时候根结点有可能被染红，而为了防止这种情况的发生，我们在修复的最后都会强制染黑根结点。好了，前面铺垫了这么多分析，就是怕大家不好理解，看到这里，插入算法也该隆重登场了，其实只有很简单的几行，只要结构组织得好，编写的代码就能体现出简洁的美，如图40所示。

func (r *RBTree) insert(node *rbnode, k, v interface{}) (*rbnode, bool) {
  ok := false
  if node == nil {
    return &rbnode{key: k, value: v, red: true}, true
  }
  if r.less(k, node.key) {
    node.left, ok = insert(node.left, k, v)
  } else if r.less(node.key, k) {
    node.right, ok = insert(node.right, k, v)
  } else {
    node.value = v
    ok = true
  }
  return fixUp(node), ok
}

相信我不用再做过多解释，大家也能看懂它在做什么了，无非是一个二叉插入操作，然后返回一个修复过的结点。如果插入操作弄懂了，下面我们就要进入，更加复杂的——删除操作啦！

七. 红黑树的删除操作

从这里开始，我们就正式介绍LLRB的删除操作，删除操作比插入操作要复杂一些，但也不是完全没有规律可循，我们甚至还可以从插入操作中获得一些启示，因此，对删除操作的介绍分为两个部分：首先进行一下热身，先给出删除最大元素和删除最小元素的实现，然后再正式讨论删除任意元素的操作。不过在展开介绍之前，先让我们提纲挈领地讨论一下红黑树的删除操作，介绍一些基本的，起关键作用的思想，这样能够增进对后面所讨论内容的理解。回想一下刚才的插入操作，我们在插入新结点的时候最害怕什么？最害怕红黑树性质的破坏，和碰到4-node，对吧？红黑树性质被破坏了，我们就要采用相应措施修复，遇到4-node的时候，新结点根本插不进去——因为4-node已经“满”了，没有空间插入新结点了——这也是我们不遗余力地分解4-node的原因（还记得“颜色翻转”吗）。
删除操作只不过是插入操作的“反操作”，一个增加结点，一个减少结点，因此插入操作中肯定有东西值得删除操作借鉴，因为相互矛盾的事物往往又是相互联系的。首先很明显的一点是，删除操作也可能会破坏红黑性质，特别是你删到黑结点的时候，所以删除之后还是要修复的，这也是为什么会有fixUp()函数的原因。其次，如果说当执行插入操作时，我们害怕遇到4-node，那么对称地看，在删除操作时，我们最怕遇到的是2-node，因为对于3-node和4-node，删除操作只是分别将它们变成2-node和3-node，如图7-1所示。

图7-1 删除之于3-node和4-node

但是针对2-node删除操作则把这个结点给删没了，更严重的是，删除2-node就相当于删除红黑树中的黑结点，这就会破坏红黑树的性质5）。所以，删除操作成功的关键就是看我们是否善于转化——当我们遇到2-node时，将其转化成3-node或4-node？这本质上是一种数学思维（即将未解决的问题转化成已经解决的问题）。怎么转化？答案是要么进行“合并”，要么就“借”。当遇到2-node时：

1. 如果2-node的兄弟结点是2-node，那么我们就把这两个2-node合并成4-node，如图7-2所示；
2. 如果2-node的兄弟结点是3-node或者4-node，那么我们就向它们“借”一个结点过来将这个2-node转化为3-node，如图7-3所示。

图7-2 合并策略 图7-3 借取策略

这里要提一点，我们要感谢伟大的LLRB，正是因为它向左倾斜红结点的表示方法让我们省去了很多对称情况的讨论，保持了代码的简洁高效，易于理解。

7.1 删除最大关键字

好了，言归正传，让我们用递归的思想来思考删除红黑树最大关键字结点的过程，由于二叉查找树本身的性质，要删除一棵红黑树的最大关键字结点，就是删除它的右子树的最大关键字结点，然后这个过程又可以看成删除右子树的右子树的最大关键字结点……就这么一直递归下去，直到我们走到那个其右子树为“空”的结点，就是我们要删除的结点了。可是刚才说了，如果删除了黑结点是会破坏红黑性质的，且要删除的结点右子树为空，并不代表左子树就为空，删除结点的同时还要考虑其左结点的连接问题，怎么办呢？
这里我们采用一个小技巧——把红边往右搬，即当我们在沿右子树不断递归向下的过程中,遇到向左倾斜的红边（这是肯定会遇到的）就把它往右搬，并且当遇到2-node时，就按照上面所说的，或采用合并策略，或采用借取策略来将2-node转化成3-node或4-node，这样最终能保证最后被删除的结点是红结点，并位于整棵树的底端。具体说来，处理两种情况：遇到向左倾斜的红边，就将其旋转成向右倾斜（保证较大元素被“推”到右子树去），如图7-4所示。

图7-4 将红边右斜

若发现当前结点h的右子结点和右子结点的左子结点都是黑结点（注意，这说明当前结点的右子结点是2-node），那么：

1. 那么，当h的左子结点的左子结点是黑结点时（这说明h的左子结点是2-node），就采取合并策略，如图7-5所示；
2. 否则，当h的左子结点的左子结点是红结点时（这说明h的左子结点一定不是2-node），就采取借取策略，如图7-6所示。

图7-5 合并左边的2-node（注意结合2-3-4树理解） 图7-6 向左边借取结点（注意结合2-3-4树理解）

这里的情况2是有点复杂，不好理解，但是我反复强调，理解红黑树的关键不在红黑树本身，而在2-3-4树，因此，你把这两种情况和图4-2，图4-3对2-3-4树较为抽象的讨论进行对比，就能理解为什么会这样做了。好了，下面我们来看代码。

func moveRedRight(node *rbnode) *rbnode {
  node = colorFlip(node)
  if node.left != nil && isRed(node.left.left) {
    node = rotateRight(node)
    node = colorFlip(node)
  }
  return node
}

如果看懂了上面的分析，理解这里的代码应该不是问题，由此看来，某些“看上去简单”的代码，其背后的原理不一定也简单，所以，真正发自内心地掌握原理才是理解和解决问题的关键。删除红黑树中最大结点的代码如下所示。

func deleteMax(node *rbnode) *rbnode {
  if isRed(node.left) {
    node = rotateRight(node)
  }
  if node.right == nil {
    return nil
  }
  if !isRed(node.right) && !isRed(node.right.left) {
    node = moveRedRight(node)
  }
  node.right = deleteMax(node.right)
  return fixUp(node)
}

有基本知识的读者应该马上就能发现，这是一个递归调用的函数，递归终结的条件就是当目标结点h的right指针指向的右子树为“空”，此时h就是包含最大关键字的结点，故使用deleteNode（）函数删除之；否则在沿树的右子树不断向下递归的过程中，若发现h结点左子树是红色，就右旋；发现h的右孩子是黑结点，就调用moveRedRight()进行处理，最后返回修复过的红黑树（注意，修复操作也是自底向上递归进行的）。图7-7和图7-8给出两个删除最大关键字结点的示例。

图7-7 删除最大关键字结点示例1 图7-8 删除最大关键字结点示例2

7.2 删除最小关键字

弄明白了删除最大关键字结点的操作，那么删除最小关键字结点的操作其实也很好理解——对称地理解就可以了，根据BST的性质，最小关键字结点一定存在于左子树中，我们要删除最小关键字结点，只要沿左子树一路递归向下即可。由于这里讨论的是LLRB，所以红边本来就是向左倾斜的，所以如果跟上面删除最大关键字结点要考虑的那两种情况对比的话，情况1就不用考虑了，而情况2需要对称地考虑如下。若发现当前结点h的左子结点和该左子结点的左子结点都是黑结点（注意，这说明当前结点的左子结点是2-node），那么：

1. 若h的右孩子的左孩子是黑结点，那么采取“合并”策略，如图7-9所示。
2. 否则，若h的右孩子的左孩子是红结点，那么采取“借取”策略，只不过这里是从右边往左边“借”红结点，跟上面的情况恰好相反，如图7-10所示。

图7-9 合并策略 图7-10 借取策略（一定要结合2-3-4树理解，再次强调）

下面我们先来看关键的moveRedLeft()函数。

func moveRedLeft(node *rbnode) *rbnode {
  node = colorFlip(node)
  if isRed(node.right.left) {
    node.right = rotateRight(node.right)
    node = rotateLeft(node)
    node = colorFlip(node)
  }
  return node
}

不多做解释了，直接看删除最小结点的代码，如图54所示。

func deleteMin(node *rbnode) *rbnode {
  if node.left == nil {
    return nil
  }
  if !isRed(node.left) && !isRed(node.left.left) {
    node = moveRedLeft(node)
  }
  node.left = deleteMin(node.left)
  return fixUp(node)
}

图7-11给出一个删除操作的示例。

图7-11 删除最小关键字结点的示例

以上就是两个删除特殊元素的操作，算是一个热身运动，因为我们下面要开始分析真正的删除操作了——即删除任意元素的操作，在此之前一定要弄清楚上面两个特殊过程，因为下面的分析将会在上面两个特殊情况的基础上完成——本来就该这样嘛，因为从特殊到一般，是科学研究的基本方法。

7.3 一般删除操作

如果说删除最大关键字结点的操作是向右搬运红边，删除最小关键字的操作是向左搬运红边，那么删除任意结点的操作，可以被称为“混合搬运”——在查找被删除结点的过程中沿树向下递归，若是向左走，就把红边向左搬运，若是向右走，则把红边向右搬运，在删除的时候考虑两种情况：

1. 被删除的结点没有子结点——直接删除；
2. 被删除的结点有子结点——用该结点的直接后继覆盖它，然后删除它的后继元素（这里跟二叉查找树的操作相同）

func (r *RBTree) delete(node *rbnode, k interface{}) (*rbnode, bool) {
  ok := false
  if r.less(k, node.key) {
    if root.left != nil {
      if !isRed(node.left) && !isRed(node.left.left) {
        node = moveRedLeft(node)
      }
      node.left, ok = delete(node.left, k)
    }
  } else {
    if isRed(node.left) {
      node = rotateRight(node)
    }
    if !r.less(k, node.key) && !r.less(node.key, k) && node.right == nil {
      return nil, true
    }
    if node.right != nil {
      if !isRed(node.right) && !isRed(node.right.left) {
        node = moveRedRight(node)
      }
      if !r.less(k, node.key) && !r.less(node.key, k) {
        smallest = min(node.right)
        node.key = smallest.key
        node.value = smallest.value
        node.right = deleteMin(node.right)
        ok = true
      } else {
        node.right, ok = r.delete(node.right, k)
      }
    }
  }
  return fixUp(node), ok
}

func min(node *rbnode) *rbnode {
  for node.left != nil {
    node = node.left
  }
  return node
}

我们来分析一下这个过程：这个函数在一开始执行时传递给h指针的是红黑树的树根，因此删除操作是从树根开始的。一开始先将h的关键字与key进行对比：1）若发现当前结点关键字大于key，说明目标结点在其左子树上，于是根据情况先将红边向左搬运，然后调用h->left = delete(h->left, key)向左递归这个过程；2）否则，若当前结点关键字不大于key，那么就是小于或等于key了，这就意味着下一步要么向右子树递归这个删除过程（如果小于），要么就地删除这个结点（如果等于），所以，若h结点左子结点是红色，就先将其往右倾斜（以防万一），然后检查它是不是有子结点，如果没有，直接删除并返回空，否则，将红边往右搬，最后根据情况2）删除它（此时被删除的结点有子结点），并在函数的最后返回修复过的结点。这里提醒一点，也许你会有疑问，为啥判断该结点是否有子结点只判断了右子结点而不考虑左子结点？（if((key == h->key) && (h->right == NULL))），这是因为左子结点已经被我们向右旋转了，所以不用考虑，这里一定要想明白。

八. 知行合一

好了，红黑树的基本操作，到这里算是讨论完了，这篇文章花了很大的篇幅，从2-3-4树的完美平衡性开始介绍，再到后来的红黑树的各种性质和操作的分解讨论，一点一点向你展示了红黑树的前因后果，为什么它有这么高的效率。这里，要感谢Princeton的Sedgewick教授，本文的所有截图均来自于Sedgewick先生的PPT和《C算法》一书，在此对您表示最为诚挚的敬意！其实人的思维是无限的，想象力也是无限的，但是思维世界中近乎完美的事物在现实世界中是不容易构建的，它需要我们做出某种“改造”，才能很好地和现实情况结合起来。我觉得红黑树对我最大的启发就是——一个真正的理想主义者应该是面对现实的，我们既不该沉沦在自己的幻想中逃避现实；也不该让外部世界成为奴役心灵的囚笼。就像阳明先生说的，“知行合一”。