1.3 树搜索
1.3.1 概述
搜索的前提是需要存储和处理大量的对象，理想的数据结构是使用树来维护一个对象列表，以支持在对象列表中快速地插入和检索对象。
二叉搜索树是一种基础的树结构，有两个基本特点。
● 每个节点最多只有两个子节点。
● 如果左子树非空，则其左子树上所有节点的值小于根节点的值；如果右子树非空，则其右子树上所有节点的值大于根节点的值。
红黑树（Red-Black Tree）是二叉搜索树的一种进化，目的是在不影响基本操作复杂性的前提下保持树的平衡，从而提高搜索效率。它通过给每个节点着色来保持平衡，以确保常见的检索和删除操作的时间复杂度永远不会退化到O(N)。要理解红黑树，必须深入了解二叉搜索树（Binary Search Tree，BST）和2-3-4树，因为红黑树与2-3-4树之间存在着等价关系。分析红黑树平衡操作时，将其转化成2-3-4树进行等价分析将事半功倍。
使用一个简单场景来理解二叉搜索树：当你在字典中查找一个单词时，如果你使用线性搜索，那么你最终将按照顺序搜索每一个单词；如果你使用二分搜索，则是将字典翻到中间部分，然后对比目标单词与字典中间的单词，并选择继续在字典的前半部分或者后半部分搜索。
相比红黑树，二叉搜索树并不是自平衡的。根据你输入的数据顺序，你构建的二叉搜索树将产生完全不同的时间复杂度。
比如，输入数据顺序是{2,3,1}，将获得一个如图1-18所示的平衡的二叉搜索树，它的时间复杂度是O(log N)，其中N是树的节点个数。
图1-18
再比如，输入数据顺序是{1,2,3}，将获得一个如图1-19所示的类似线性链表的结构，它的时间复杂度是O(N)，其中N是链表的节点个数。
图1-19
相反，对于红黑树而言，输入数据的顺序无论是{2,3,1}还是{1,2,3}，都将获得一个如图1-20所示的平衡的红黑树。红黑树的时间复杂度会稳定在O(log N)。
图1-20
简单来说，二叉搜索树在理想情况下的时间复杂度是O(log N)，即树的高度。当在二叉搜索树中频繁执行插入与删除操作后，在极端情况下，二叉搜索树会退化成线性链表结构，时间复杂度会退化成O(N)。红黑树可以用来解决对二叉搜索树频繁执行插入与删除后出现的时间复杂度退化的问题，即红黑树可以提供稳定高效的搜索操作。
顺便提一下，相比红黑树结构，哈希表结构提供O(1)的时间复杂度，但它对内存的要求比较严格，需要事先分配足够的内存来存储它。而红黑树只需要分配存在的节点，占用的内存较小。二者还有一个显著的差别，即红黑树将数据有序存储，支持高效的小范围搜索，而哈希表结构需要遍历整个空间进行大范围搜索。
1.3.2 二叉搜索树
二叉搜索树是一个递归的数据结构，且对二叉搜索树进行中序遍历，可以获得一个递增的有序序列。
代码清单1-8 二叉搜索树节点（Node类）的定义
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int count; // number of nodes in subtree
public Node(Key key, Value val, int count) {
this.key = key;
this.val = val;
this.count = count;
}
}
二叉搜索树是一种非常有用的数据结构，它包含Get、Put、Delete等基本的操作。
1．Get操作
从根节点开始递归搜索，并返回匹配的节点。简单来说，就是将搜索节点的值与根节点的值进行比较，如果搜索节点的值小于根节点的值，则向左子树进行递归搜索，如果大于，则向右子树进行递归搜索，如果等于，则表示搜索命中，返回该值。
2．Put操作
从根节点开始递归搜索，直到找到一个空链接，然后创建一个新的节点与空链接进行连接。如果添加键已经存在，则可以选择直接更新。
3．Delete操作
删除节点包含两个步骤：搜索和删除。搜索到目标节点后，删除这个节点。从二叉搜索树中删除一个节点时，根据节点的类型分3种情况。
Case1：待删除节点没有子节点。
如图1-21所示，待删除节点9没有子节点，可以直接删除。
图1-21
Case2：待删除节点只有一个子节点。
如图1-22所示，待删除节点13只有一个子节点，需要使被删除节点的父节点直接连接被删除节点的子节点。
图1-22
Case3：待删除节点有两个子节点。
待删除节点有两个子节点的情况会稍微复杂一些，需进行如下操作。
● 搜索待删除节点。
● 找到待删除节点的前驱节点，即待删除节点左子树的最大节点。此时的前驱节点至多包含一个子节点。
● 将待删除节点的值与其前驱节点的值进行交换。
● 删除前驱节点。如前所述，前驱节点至多包含一个子节点，删除前驱节点就简化成Case1或者Case2中的简单问题了。
上面的流程实施的是替代操作，将前驱节点与待删除节点交换后，转而删除前驱节点。本质是将复杂问题简单化。
4．二叉搜索树的缺点
图1-23所示为一棵不平衡的树，在最坏的情况下，它会从树退化成一个链表。搜索某个节点的时间复杂度从O(log N)退化成O(N)。相反，一个平衡的二叉搜索树可以避免最坏情况的发生，它的树高，即时间复杂度可以始终保持在对数级别。
图1-23
1.3.3 2-3-4树
红黑树实际上是由2-3-4树进化而来的，如果你希望深入研究红黑树，则需要注意2-3-4树的性质，以及2-3-4树与红黑树之间存在的转换关系。
2-3-4树的性质如下。
● 树中每个节点最多包含3个元素、4个子节点。
● 树中每个节点内的值是有序的。
● 所有的叶子节点都在同一水平，确保完全平衡。
2-3-4树节点类型如下。
● 2-Node：包含1个元素、2个子节点。
● 3-Node：包含2个元素、3个子节点。
● 4-Node：包含3个元素、4个子节点。
图1-24展示了2-Node、3-Node和4-Node的结构。比如3-Node中有两个元素（A和B）和3个子节点，第一个子节点中的节点值小于A，第二个子节点中的节点值介于A与B之间，第三个子节点中的节点值大于B。
图1-24
简单来说，元素是按照顺序进行排列的，这符合二叉搜索树的性质，即所有的父节点的值大于左子节点的值，同时小于右子节点的值。
1．2-3-4树的构建
下面通过一个案例来讲解2-3-4树的构建过程。构建一个2-3-4树，其中包含数据项6、9、10、13、14、16、17、18、19、20、1，构建的过程如下。
● 依次插入数据项6、9、10。
● 插入数据项13后5-Node类型的节点需要分裂，如图1-25所示。
图1-25
● 插入数据项14、16后5-Node类型的节点需要分裂，如图1-26所示。
图1-26
● 插入数据项17、18后5-Node类型的节点需要分裂，如图1-27所示。
图1-27
● 插入数据项19、20后5-Node类型的节点需要分裂；分裂出的数据项18与父节点进行合并后需要递归分裂，如图1-28所示。
图1-28
● 插入数据项1，如图1-29所示。
图1-29
2-3-4树按中序遍历得到的序列是一个递增有序序列。想象一束光自顶向下照射2-3-4树，将在水平面上形成一个递增有序序列，如图1-30所示。
图1-30
2．2-3-4树的删除
下面通过一个案例来讲解2-3-4树的删除过程。对于图1-31中的2-3-4树，依次删除数据项1、7、6、9、3、8，过程如下。
图1-31
● Step1：删除数据项1。
在图1-31中，从根节点8开始向下遍历找到包含数据项1的节点。该节点是一个3-Node类型的节点并且是叶子节点，有两个数据项，可以直接删除，不影响平衡性质，结果如图1-32所示。
图1-32
● Step2：删除数据项7。
在图1-32中，从根节点8开始向下遍历并找到包含数据项7的节点。该节点是一个叶子节点，且是只有一个数据项的2-Node类型的节点。检查发现节点7有一个3-Node类型的兄弟节点（包含元素4和5）。
兄弟节点可以借出一个元素，但不能直接将数据项5移到节点7上，否则父节点6的右子节点会变成5，违反搜索树的性质。因此需要进行右旋操作，即首先将数据项5从兄弟节点移到父节点，然后父节点的数据项6下沉到右子节点7，最后删除数据项7。整个过程包含右旋和删除两步操作，结果如图1-33所示。
图1-33
● Step3：删除数据项6。
在图1-33中，从根节点8开始向下遍历找到包含数据项6的节点。该节点是一个叶子节点，也是只有一个数据项的2-Node类型的节点。检查发现节点6有一个2-Node类型的兄弟节点（4）。将这两个2-Node类型节点的父节点（5）下沉，形成一个新的平衡节点（4、5和6），即有3个数据项的4-Node类型节点，如图1-34所示。然后删掉包含数据项6的节点，结果如图1-35所示。
图1-34
图1-35
● Step4：删除数据项9。
在图1-35中，从根节点8开始向下遍历找到包含数据项9的节点。该节点是一个叶子节点，也是有两个数据项的3-Node类型的节点，可以直接删除，不影响平衡性质，结果如图1-36所示。
图1-36
● Step5：删除数据项3。
在图1-36中，从根节点8开始向下遍历找到包含数据项3的节点。该节点是一个内部节点，它的右子节点有两个数据项（4和5）。使用数据项3的继承项4替换3，然后从叶子节点中删除数据项4，结果如图1-37所示。此时节点4是2-Node类型节点，其兄弟节点11也是2-Node类型节点，父节点仍是2-Node类型节点。将这3个2-Node类型节点合并，结果如图1-38所示。
图1-37
图1-38
● Step6：删除数据项8。
在图1-38中，发现根节点包含待删除的数据项8。数据项8有两个子节点（5和10）且都是2-Node类型节点。将这两个子节点合并后删除数据项8，结果如图1-39所示。
图1-39
2-3-4树的优点在于能存放更多的数据项，并且树的高度能尽量低。它的缺点则是由于存在不同的节点类型，操作较为复杂。
1.3.4 2-3-4树与红黑树的等价关系
二叉搜索树在动态更新过程中，会产生性能退化的问题。红黑树通过保持树的平衡性来避免性能退化，但它的实现逻辑相对复杂。事实上，红黑树与2-3-4树之间存在等价关系，一个2-3-4树对应多个红黑树，但一个红黑树只对应一个2-3-4树。分析红黑树平衡操作时，将其转化成2-3-4树模型进行等价分析将事半功倍。
红黑树是二叉搜索树的一种演化，它通过对每个节点引入两种颜色标记和一组约束规则，以确保树中最深的路径不超过最短路径的两倍，并保持树的平衡性。
红黑树有五大性质：
（1）每个节点要么是红色的，要么是黑色的；
（2）树的根节点必须是黑色的；
（3）不存在两个相邻的红色节点；
（4）从任意一个节点到其后代叶子节点的每条路径都有相同数量的黑色节点；
（5）树的叶子节点必须是黑色的。
相比二叉搜索树，红黑树提供了高效的插入、删除和查找接口，其时间复杂度是 O(log N)，其中N代表红黑树中节点的数量。对于倾斜的二叉树，时间复杂度最高会变成O(N)。红黑树的目的是实现黑色节点数量的平衡。
1．将2-3-4树转化成红黑树的规则
将2-3-4树转化为红黑树的规则，简单归纳有3个。
（1）2-3-4树的2-Node类型的节点包含一个数据项，转化为红黑树的节点时直接变成一个黑色的节点。
（2）2-3-4树的3-Node类型的节点包含两个数据项，转化为红黑树的节点时需要转换成父、子两个节点，上面的父节点为黑色，下面的子节点为红色。
（3）2-3-4树的4-Node类型的节点包含3个数据项，转化为红黑树的节点时需要转换成父、子3个节点，中间的数据项变成黑色的父节点，两边的数据项变成红色的子节点。
图1-40给出了3种情况的图形化示意（书中的浅色节点表示红黑树中的红色节点，读者可以从配套资源中下载彩图）。
图1-40
现在我们分析2-3-4树中的3种节点。
● 2-Node类型的节点。
如图1-41所示，显然可以直接将2-Node类型的节点映射成一个二叉搜索树的节点。
● 3-Node类型的节点。
对于3-Node类型的节点，存在两种不同的方法来进行映射。这个时候对节点引入颜色的概念：将节点分为黑色与红色。永远记住一点：父节点是黑色的，而子节点是红色的，即当你看到一个红色节点的时候，它一定与它的黑色父节点属于等价2-3-4树中的同一个节点。如图1-42所示。
图1-41
图1-42
● 4-Node类型的节点。
4-Node类型的节点的映射更加复杂，存在5种不同的方法，并同样遵循“上黑下红”的组织原则。图1-43中4-Node类型的节点被映射成完全平衡红黑树，而图1-44中4-Node类型的节点被映射成4种不平衡的红黑树，需要调整。
图1-43
图1-44
上面讨论时的思路是尝试将2-3-4树转换成二叉树，而我们知道红黑树即平衡二叉搜索树。下面通过一个例子进行详细讲解，初始2-3-4树如图1-45所示。
图1-45
● 应用规则1：节点9、10、13、14都是2-Node类型的，直接转换成黑色，如图1-46所示。
图1-46
● 应用规则2：节点1、6、16、18都是3-Node类型的，遵循“上黑下红”的转化原则。
上黑下红有两种形态：红色在左边叫作左倾（如图1-47所示），红色在右边叫作右倾（如图1-48所示）。这两种形态都是合理的，这就是为什么一个2-3-4树可以对应多个红黑树。
图1-47
图1-48
● 应用规则3：节点19、20、21是4-Node类型的，遵循“上黑两边红”的转化原则。
能够保持红黑树平衡的表示方式是唯一的。4-Node类型的节点在转化成红黑树后会形成父子两层节点，父节点是黑色的，而它的两个子节点是红色的。如前所述，红黑树中的黑色节点数量是平衡的。
在左倾基础上应用规则3后，从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点，满足红黑树的定义，如图1-49所示。
图1-49
在右倾基础上应用规则3后，从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点，同样满足红黑树的定义，如图1-50所示。
图1-50
简单推导红黑树性质4：从任意一个节点到其后代叶子节点的每条路径都有相同数量的黑色节点。如前所述，红黑树是从2-3-4树根据规则转换过来的，2-3-4树有两个特征。
● 2-3-4树的节点有3种类型：2-Node、3-Node和4-Node类型。比如，2-Node类型的节点转化成红黑树节点后是黑色的，3-Node类型的节点转化成红黑树节点后是父节点黑、子节点红，而4-Node类型的节点转化成红黑树节点后是中间父节点黑、两边子节点红。2-3-4树中任意节点转化成红黑树节点后都包含一个黑色节点。
● 从2-3-4树的根节点到叶子节点经过的路径是相同的。
所以，2-3-4树转化成红黑树后，从任意一个节点到其后代叶子节点的每条路径中都有相同数量的黑色节点。
2．将红黑树转化成2-3-4树的规则
在红黑树中不存在相邻的红色节点。将红黑树转化为2-3-4树的基本规则只有下面一条：
每当遇到红色节点时，将该红色节点向上移动与其黑色父节点进行合并，形成3-Node类型的节点或者4-Node类型的节点。
上面的规则比较抽象，因此通过一个红黑树转化为2-3-4树的例子来进行解释。如图1-51所示，从图1-51（a）到图1-51（b）的过程中，红色节点10和5分别与它们的黑色父节点20和6合并；从图1-51（b）到图1-51（c）的过程中，红色节点15、19和26、32分别与它们的黑色父节点18和30合并。
图1-51
1.3.5 红黑树操作
下面介绍红黑树的操作，包含结构定义、左旋与右旋、插入节点、删除节点。
1．结构定义
红黑树是一种自平衡的二叉树，包含两个体结构：Node（红黑树节点）和Rbtree（红黑树）。
代码清单1-9 红黑树节点结构定义
// Node of the rbtree has a pointer of the node of parent, left, right, also has own color and Item which client uses
type Node struct {
Left *Node
Right *Node
Parent *Node
Color uint
// for use by client
Item
}
const (
// RED represents the color of the node is red
RED = 0
// BLACK represents the color of the node is black
BLACK = 1
)
// Item has a method to compare items which is less
type Item interface {
Less(than Item) bool
}
// Rbtree represents a Red-Black tree
type Rbtree struct {
NIL *Node
root *Node
count uint
}
func less(x, y Item) bool {
return x.Less(y)
}
2．左旋与右旋
红黑树有两种类型的旋转：左旋和右旋。如图1-52所示，将这棵树的节点node左旋之后，它的右子节点right就会成为子树的新的根节点。节点right的左子节点是node，而之前right的左子节点将成为node节点的右子节点。
现在，我们对节点right进行右旋后，它将转换回原始树，如图1-53所示。
图1-52
图1-53
代码清单1-10 红黑树左旋
func (t *Rbtree) leftRotate(x *Node) {
if x.Right == t.NIL {
return
}
//
// The illation of left rotation
//
// | |
// X Y
// / \ left rotate / \
// α Y -------------> X γ
// / \ / \
// β γ α β
//
// It should be note that during the rotating we do not change the Nodes' color
//
y := x.Right
x.Right = y.Left
if y.Left != t.NIL {
y.Left.Parent = x
}
y.Parent = x.Parent
if x.Parent == t.NIL {
t.root = y
} else if x == x.Parent.Left {
x.Parent.Left = y
} else {
x.Parent.Right = y
}
y.Left = x
x.Parent = y
}
3．插入节点
向红黑树中插入节点需要保证红黑树的五大性质。
（1）每个节点要么是红色的，要么是黑色的。
（2）树的根节点必须是黑色的。
（3）不存在两个相邻的红色节点。
（4）从任意一个节点到其后代叶子节点的每条路径都有相同数量的黑色节点。
（5）树的叶子节点也必须是黑色的。
将一个节点插入红黑树中，包含两个步骤。第一步，调用insert接口添加一个节点，就像在普通的二叉搜索树中的操作一样。第二步，在插入节点后调用insertFixup接口来修复插入过程中可能引起的红黑树性质的冲突。
记住一点，新插入的节点要设置成红色节点，以满足红黑树的性质4。插入过程从根节点开始，将插入节点与根节点的值进行比较，若相等，则直接返回；若不等，则当插入节点的值小于根节点的值时，继续在根节点的左子树中查找，否则在根节点的右子树中查找。很显然，这是一个递归过程。
（1）调用insert接口。
向红黑树中插入节点的代码如下：
func (t *Rbtree) insert(z *Node) *Node {
x := t.root
y := t.NIL
for x != t.NIL {
y = x
if less(z.Item, x.Item) {
x = x.Left
} else if less(x.Item, z.Item) {
x = x.Right
} else {
return x
}
}
z.Parent = y
if y == t.NIL {
t.root = z
} else if less(z.Item, y.Item) {
y.Left = z
} else {
y.Right = z
}
t.count++
t.insertFixup(z)
return z
}
插入节点的代码中用到了insertFixup函数，下面分析该函数的细节，可以分成3种情况。
Case1：向红黑树中等价于2-3-4树中的4-Node类型节点的节点下添加新节点。
2-3-4树中的4-Node类型的节点转化为红黑树时会变成一个黑色的父节点和两个红色的子节点，当向其中一个红色子节点下方插入新的节点z时，如图1-54（a）所示，违反了性质3（不存在两个相邻的红色节点）。
在这种情况下，由于新添加的节点z的叔叔节点也是红色的，所以将节点z挪到其叔叔节点之下也不能解决这个问题。如果将新添加的节点z的父亲与叔叔节点设置为黑色，则需同时将z节点的祖先节点设置为红色，如图1-54（b）所示。然而，这可能会导致祖先节点违反性质3（不存在两个相邻的红色节点）。很显然，这是一个递归的染色过程。
图1-54
Case2：向红黑树中等价于2-3-4树中的3-Node类型节点的节点下添加新节点。
2-3-4树中的3-Node类型的节点转化为红黑树时会变成一个黑色的父节点和一个红色的子节点，当向其中的红色子节点下方插入新的节点z时，如图1-55所示，违反了性质3（不存在两个相邻的红色节点）。
图1-55
在这种情况下，根据新添加的节点z与其父节点的左右关系，可以分为两种情况。
● Case2.1：z是父节点的左子节点。
● Case2.2：z是父节点的右子节点。
图1-56中，可以通过在新添加的节点z的父节点上执行左旋来将Case2.2转换成Case2.1。这样我们只需要处理Case2.1一种情况。
图1-56
对于Case2.1，首先将节点z的父节点设置为黑色，祖先节点设置为红色，然后对z的祖先节点进行右旋，如图1-57所示。
图1-57
Case3：向红黑树中等价于2-3-4树中的2-Node类型节点的节点下添加新节点。
2-3-4树中的2-Node类型的节点转化为红黑树时会变成一个黑色的节点，当向其下方插入新的节点z时，可以直接添加，不需要额外的调整操作，如图1-58所示。
图1-58
下面通过一个例子来展示如何解决Case1与Case2的递归染色问题。
● Step1：如图1-59所示，新添加的节点33与其父节点38都是红色的，需要根据Case1进行递归方案调整。
图1-59
● Step2：调整后节点40与其父节点30仍然存在相邻节点皆是红色节点的问题，违反红黑树性质3，需要递归调整。因为节点40是其父节点30的右子节点，所以需要根据Case2.2进行调整，即对节点30执行左旋。如图1-60所示。
图1-60
● Step3：节点30变成了其父节点40的左子节点，因此需要根据Case2.1进行调整，即对节点30的祖先节点（60）执行右旋。如图1-61所示。
图1-61
（2）调用insertFixup接口。
调用insertFixup接口来修复插入过程中可能引起的红黑树性质的冲突。
代码清单1-11 插入节点后调用insertFixup接口进行颜色修正
func (t *Rbtree) insertFixup(z *Node) {
for z.Parent.Color == RED {
//
// However, we do not need the assertion of non-nil grandparent
// because the root is black
//
//
//
// Since the color of the parent is RED, so the parent is not root
// and the grandparent must be exist
//
if z.Parent == z.Parent.Parent.Left {
// Take y as the uncle, although it can be NIL, in that case
// its color is BLACK
y := z.Parent.Parent.Right
if y.Color == RED {
//
// Case 1:
// Parent and uncle are both RED, the grandparent must be BLACK
// due to
//
// 4) Both children of every red node are black
//
// Since the current node and its parent are all RED, we still
// in violation of 4), So repaint both the parent and the uncle
// to BLACK and grandparent to RED(to maintain 5)
//
// 5) Every simple path from root to leaves contains the same
// number of black nodes
//
z.Parent.Color = BLACK
y.Color = BLACK
z.Parent.Parent.Color = RED
z = z.Parent.Parent
} else {
if z == z.Parent.Right {
//
// Case 2:
// Parent is RED and uncle is BLACK and the current node
// is right child
//
// A left rotation on the parent of the current node will
// switch the roles of each other. This still leaves us in
// violation of 4)
// The continuation into Case 3 will fix that
//
z = z.Parent
t.leftRotate(z)
}
//
// Case 3:
// Parent is RED and uncle is BLACK and the current node is
// left child
//
// At the very beginning of Case3, current node and parent are
// both RED, thus we violate 4)
// Repaint parent to BLACK will fix it, but 5) does not allow
// this because all paths that go through the parent will get
// 1 more black node. Then repaint grandparent to RED (as we
// discussed before, the grandparent is BLACK) and do a right
// rotation will fix that
//
z.Parent.Color = BLACK
z.Parent.Parent.Color = RED
t.rightRotate(z.Parent.Parent)
}
} else { // same as then clause with "right" and "left" exchanged
y := z.Parent.Parent.Left
if y.Color == RED {
z.Parent.Color = BLACK
y.Color = BLACK
z.Parent.Parent.Color = RED
z = z.Parent.Parent
} else {
if z == z.Parent.Left {
z = z.Parent
t.rightRotate(z)
}
z.Parent.Color = BLACK
z.Parent.Parent.Color = RED
t.leftRotate(z.Parent.Parent)
}
}
}
t.root.Color = BLACK
}
4．删除节点
因为红黑树是一种特殊的二叉搜索树，因此删除红黑树中的节点和删除二叉搜索树中的节点类似，包含3种情况。
● Case1：待删除节点没有子节点。
● Case2：待删除节点只有一个子节点。
● Case3：待删除节点有两个子节点。
前两种情况的处理方法比较简单。对于Case1，删除没有子节点的节点，只需要简单地从树中删除该节点。对于Case2，删除带有一个子节点的节点，只需要在删除该节点的同时让其子节点代替其。
Case3稍微复杂一些，包含如下步骤。
● 搜索待删除节点。
● 找到待删除节点的后继节点，即待删除节点右子树的最小节点。此时的后继节点至多包含一个子节点。
● 将待删除节点的值与其后继节点的值进行交换。
● 删除后继节点。如前所述，后继节点至多包含一个子节点，删除后继节点后就变成Case1或者Case2的简单问题了。
红黑树的删除节点最终会转换成删除叶子节点（最底下一层），或者删除只有一个子节点的非叶子节点（倒数两层）这两种情况。而红黑树的最底下两层皆对应2-3-4树的叶子节点。
换句话说，删除红黑树中的节点分成3种情况，通过转换可以将Case3转换成Case1和Case2的基本情况，而Case1与Case2的操作等价于删除2-3-4树中的叶子节点。
删除操作涉及删除（delete）、寻找后继（successor）和颜色修正（deleteFixup）。
（1）删除
删除流程遵循先搜索后删除的逻辑，在分布式系统中更是如此。与向红黑树中添加节点相似，删除节点需经历两个步骤：先删除，后调整颜色。删除过程中需要用到t.search函数，这个函数从根节点开始进行递归搜索，类似二分搜索算法。
代码清单1-12 删除红黑树中的节点
func (t *Rbtree) delete(key *Node) *Node {
z := t.search(key)
if z == t.NIL {
return t.NIL
}
ret := &Node{t.NIL, t.NIL, t.NIL, z.Color, z.Item}
var y *Node
var x *Node
if z.Left == t.NIL || z.Right == t.NIL {
y = z
} else {
y = t.successor(z)
}
if y.Left != t.NIL {
x = y.Left
} else {
x = y.Right
}
// Even if x is NIL, we do the assign. In that case all the NIL nodes will
// change from {nil, nil, nil, BLACK, nil} to {nil, nil, ADDR, BLACK, nil},
// but do not worry about that because it will not affect the compare
// between Node-X with Node-NIL
x.Parent = y.Parent
if y.Parent == t.NIL {
t.root = x
} else if y == y.Parent.Left {
y.Parent.Left = x
} else {
y.Parent.Right = x
}
if y != z {
z.Item = y.Item
}
if y.Color == BLACK {
t.deleteFixup(x)
}
t.count--
return ret
}
删除后，需要调整平衡，但只有当删除的节点是黑色节点时才需要调整平衡，因为红黑树是基于黑色节点的数量平衡的。当完成节点删除后，我们继续研究deleteFixup函数的细节。
红黑树转换成等价的2-3-4树的规则为，任何时候遇到红色节点都将它向上移动与黑色父节点合并成3-Node或者4-Node类型的节点。1.3.4小节中讲解的将一个红黑树转化为2-3-4树的例子如图1-62所示。
图1-62
如前所述，红黑树的删除最终会转换成删除叶子节点（最底下一层），或者删除只有一个孩子的非叶子节点（倒数第二层）这两种情况。本质上删除红黑树可以转化为删除与红黑树等价的2-3-4树的叶子节点。很显然，2-3-4树的叶子节点只有3种情况：2-Node、3-Node和4-Node类型的节点。
Case1：删除红黑树中等价于2-3-4树中4-Node类型节点的数据项（不用向兄弟节点借）。
图1-63中，删除4-Node类型节点中的数据项的操作是安全的，分析如下。
● 如果删除4-Node类型的节点（15、18、19）中的数据项15，删除的是红色节点，没有破坏红黑树的性质，可以安全地删除红色数据节点15。
● 如果删除4-Node类型的节点（15、18、19）中的数据项19，删除的是红色节点，没有破坏红黑树的性质，可以安全地删除红色数据节点19。
● 如果删除4-Node类型的节点（15、18、19）中的数据项18，删除的是黑色节点，也可以安全地删除，只需要从同级的两个红色数据项中随机选择一个从红色修改成黑色并结合旋转操作即可。
图1-63
Case2：删除红黑树中等价于2-3-4树中3-Node类型节点的数据项（不用向兄弟节点借）。
图1-63中，删除3-Node类型节点中的数据项的操作也是安全的，分析如下。
● 如果删除3-Node类型的节点（5、6）中的数据项5，删除的是红色节点，没有破坏红黑树的性质，可以安全地删除红色数据节点5。
● 如果删除3-Node类型的节点（5、6）中的数据项6，删除的是黑色节点，也可以安全地删除，只需要将同级的红色数据项5从红色变成黑色就能继续保持性质。
Case3：删除红黑树中等价于2-3-4树中2-Node类型节点的数据项（需要向兄弟节点借）。
图1-64中，删除2-Node类型的节点（6）会导致黑色节点的数量不平衡而失去安全性。应该怎么处理？
图1-64
是不是可以直接向3-Node类型的兄弟节点（15、18）借一个数据项呢？答案是不能直接从兄弟节点借数据项，这将导致数据无序，如图1-65所示。
图1-65
Case3.1：待删除节点是2-Node类型的，兄弟节点是4-Node类型的，可以借一个节点给待删除节点。
如图1-66所示，调整策略是将father与brother交换颜色，然后对father执行左旋。
图1-66
Case3.2：待删除节点是2-Node类型的，兄弟节点是3-Node类型的，可以借一个节点给待删除节点。
删除2-Node类型的节点（6）后，需要向兄弟节点借一个数据项，但不是直接借而是间接借，需要通过左旋操作由父节点来借一个数据项，从而保持树中各节点的数据项的有序性。比如，图1-67中，删除节点6，并间接向兄弟节点借15，即父节点10下沉，兄弟节点15上移至父节点。
图1-67
● Case3.2.1：待删除节点是2-Node类型的，其兄弟节点brother是3-Node类型的（可以借数据项），并且brother有一个与其方向一致的红色节点son。
与brother方向一致，是指brother为father的左子节点，son节点也是brother的左子节点；或者brother为father的右子节点，son节点也是brother的右子节点。调整策略就是对father实施左旋，保持红黑树的平衡性质，如图1-68所示。
图1-68
● Case3.2.2：待删除节点是2-Node类型的，其兄弟节点brother是3-Node类型的（可以借数据项），并且brother有一个与其方向不一致的红色节点son。
调整策略分两步。第一步如图1-69所示，对brother执行右旋，此时红黑树中father、son、brother 3个节点在一个方向上，问题就简化成了Case3.2.1。第二步是遵循Case3.2.1规则对father执行左旋。
图1-69
Case3.3：待删除节点是2-Node类型的，兄弟节点也是2-Node类型的，不可以借一个节点给待删除节点。
如图1-70所示，删除2-Node类型的节点（10）后，需要向兄弟节点借一个数据项，兄弟节点（18）本身也是2-Node类型的，所以无法借出。
图1-70
● Case3.3.1：待删除节点是2-Node类型的，兄弟节点本身也是2-Node类型的（不能借数据项），并且待删除节点的父节点father是红色的。
调整策略特别简单：只需要将待删除节点与brother节点从黑色修改成红色，同时将父节点father从红色修改成黑色，就可以完成调整工作，如图1-71所示。
图1-71
● Case3.3.2：待删除节点是2-Node类型的，兄弟节点本身也是2-Node类型的（不能借数据项），并且待删除节点的父节点是黑色的。
如图1-72所示，调整策略是将待删除节点与brother节点同时从黑色调整成红色。由于father节点已经是黑色的了，接下来的问题就转移到了对father、father的father以及father的brother3个节点的关系判断，这是一个完全相似的子问题（即father为节点的子树中黑色节点数量减1，如何平衡？），通过不断地向上递归来解决。如果一直是这种情况，最终会转化为root的层面。
图1-72
（2）寻找后继
如果一个节点有右子树，那么它的后继节点就是其右子树下值最小的节点。如果一个节点没有右子树，则需要向上查找当前节点是哪个节点的左子节点。
代码清单1-13 在红黑树中寻找后继节点
func (t *Rbtree) successor(x *Node) *Node {
if x == t.NIL {
return t.NIL
}
if x.Right != t.NIL {
return t.min(x.Right)
}
y := x.Parent
for y != t.NIL && x == y.Right {
x = y
y = y.Parent
}
return y
}
func (t *Rbtree) min(x *Node) *Node {
if x == t.NIL {
return t.NIL
}
for x.Left != t.NIL {
x = x.Left
}
return x
}
（3）颜色修正
对红黑树进行颜色修正时，需要将红黑树还原成2-3-4树。每当遇到红色节点时，将它向上移动与黑色父节点进行合并，构成3-Node或者4-Node类型的节点。
代码清单1-14 删除节点后颜色修正算法
func (t *Rbtree) deleteFixup(x *Node) {
for x != t.root && x.Color == BLACK {
if x == x.Parent.Left {
w := x.Parent.Right
if w.Color == RED {
w.Color = BLACK
x.Parent.Color = RED
t.leftRotate(x.Parent)
w = x.Parent.Right
}
if w.Left.Color == BLACK && w.Right.Color == BLACK {
w.Color = RED
x = x.Parent
} else {
if w.Right.Color == BLACK {
w.Left.Color = BLACK
w.Color = RED
t.rightRotate(w)
w = x.Parent.Right
}
w.Color = x.Parent.Color
x.Parent.Color = BLACK
w.Right.Color = BLACK
t.leftRotate(x.Parent)
// this is to exit while loop
x = t.root
}
} else { // the code below is has left and right switched from above
w := x.Parent.Left
if w.Color == RED {
w.Color = BLACK
x.Parent.Color = RED
t.rightRotate(x.Parent)
w = x.Parent.Left
}
if w.Left.Color == BLACK && w.Right.Color == BLACK {
w.Color = RED
x = x.Parent
} else {
if w.Left.Color == BLACK {
w.Right.Color = BLACK
w.Color = RED
t.leftRotate(w)
w = x.Parent.Left
}
w.Color = x.Parent.Color
x.Parent.Color = BLACK
w.Left.Color = BLACK
t.rightRotate(x.Parent)
x = t.root
}
}
}
x.Color = BLACK
}
1.3.6 红黑树典型应用场景
在Linux系统中，每个进程有4GB的虚拟内存空间，该空间包含多个虚拟内存区域（Virtual Memory Area，VMA），比如代码段，数据段、Heap段、Stack段。每个VMA都代表一个连续的虚拟地址空间，并且这个空间具有相同的内存属性，比如读写权限。从进程角度分析，虽然一个VMA的虚拟地址是连续的，但它映射的物理内存空间区域可能并不连续。当进程需要申请新的物理空间时，首先需要申请分配虚拟地址空间。
对于Linux内核中频繁的内存操作，需要追求极致的效率。因此Linux的进程内所有VMA通过红黑树进行管理，允许内核高效遍历进程地址空间中的所有VMA。