红黑树
在上文中，我们介绍了二叉搜索树，其插入、搜索和删除操作的复杂度为\(O(h)\)，\(h\)是二叉树的高度。 在平均情况下树的高度与树的节点数量\(n\)成对数关系\(h \sim O(log(n))\)。但是在一些极端的情况下，比如说连续插入了一段有序的元素，将导致二叉树处于一种非平衡的状态， 二叉树退化为一个线性表，其各种操作的复杂度就成为了\(O(n)\)。
为了保证系统的效率，我们应当尽可能的保证所构建的二叉树是平衡的。人们为之提出了很多解决方案。红黑树是其中一种实现简单、应用广泛的方案。它仍然是一种二叉树，只是增加了颜色属性和一些约束:
- 每个节点不是黑色就是红色;
- 根节点是黑色的;
- 每个叶子节点(NIL)都是黑色的;
- 如果一个节点是红色的，那么它的两个孩子都是黑色的;
- 对于每个节点，从该节点到其叶子后代节点的所有简单路径上具有相同数目的黑色节点。
上面右图是从《算法导论》中截取的红黑树示例图。图中深色表示黑色，浅色表示红色。 其叶子节点是一类特殊节点(NIL)，它只有颜色属性，不记录键值。可以证明，红黑树中从根节点出发的简单路径中不存在一条路径长于其他路径的两倍，所以红黑树是一种近似平衡的二叉树。
本文中，继承自C++模板BinaryTree.hpp和 BinaryTreeNode.hpp 实现了红黑树RBTree.hpp和 RBTreeNode.hpp。对于红黑树而言，它本身就是一种二叉树，所以二叉树的遍历等操作对其都是成立的。 只是插入和删除操作的过程中，可能破坏红黑树的属性，所以我们需要重写插入和删除函数。在介绍这两个函数之前，我们先介绍一个辅助操作——旋转。它用于调整红黑树节点，以恢复红黑树特性。
1. 旋转
/*
* y x
* / \ left_rotate @x / \
* x c <----------------- a y
* / \ -----------------> / \
* a b right_rotate @y b c
*/
旋转操作实际上是一种针对二叉树的操作，它可以在不破坏二叉树的特性的情况下，改变二叉树的结构。二叉树的特性是指，对于二叉树中的某个节点，其左子树中的节点键值一定不大于考察节点的键值， 右子树则一定不小于考察节点键值。
根据转动方向的不同，有左旋和右旋两种操作方式，这两种旋转互为逆运算。如右边的注释所示，从左往右，我们对节点x进行左旋，其右孩子y将替代它成为整个子树的根节点，而x将作为y的左孩子存在。 此外由于b的键值一定不小于x，不大于y，所以旋转后将之放置在y的左子树x的右子树中。
类似的，从右往左，对接点y进行右旋，其左孩子x将成为整个子树的根节点，y成为x的右孩子，b则被放置在x的右子树y的左子树中。下面的左边是左旋操作的代码实现，对称的互换x和y的身份以及左右， 就可以得到右边所示的右旋操作。
|
|
2. 插入
对于一个红黑树的插入操作可以拆分为两个子过程。首先按照二叉树的形式插入一个红色的节点，由于插入操作有可能破坏红黑树的属性，所以还需要对树进行调整，以恢复被破坏的特性。 整个过程可以由下面的代码描述。
RBTreeNode<T> * insert(T const & data) {
RBTreeNode<T> *re = new RBTreeNode<T>(data);
re->color = RBNodeColor::RED;
BinaryTree<T>::insert(re);
insert_fixup(re);
return re;
}
在介绍函数insert_fixup修正红黑树特性之前，我们先来讨论一下插入一个红色节点，可能打破哪些规则。第一个约束，每个节点不是黑色就是红色的，稳定的好像一句废话，一定不会破坏的。 同样的还有第三条，每个叶子节点(NIL)都是黑色的。由于我们插入的是一个红色的节点，所以不会改变任何简单路径上黑色节点的数量，所以第5条约束也是满足的。 只有第二条和第四条规则可能被触犯。我们的insert_fixup就是来处理如下两个问题的，由于代码较长，这里只解释其思想， 具体实现参考源码。
- 考察的节点n是根节点，但它是红色的;
- 考察的节点n和它的父节点p都是红色的。
针对第一个问题，很容易解决，只需要修改根节点的颜色为黑色就可以了。针对第二个问题有6种可能的情形，根据父节点p是祖父节点的左孩子还是右孩子，可以将之分为两大类。 这两大类的形式是对称的，也就是说，通过简单的左右互换，就可以从一类情形得到另一类情形。对于每一类的三种情况，我们做如下的处理：
Case 1: 节点n的叔叔u是红色的
/* p = G->left | p = G->right
* G g | G g
* / \ / \ | / \ / \
* p u --> P U | u p --> U P
* / / | \ \
* n n | n n
*/
如右边的注释所示，其中大写字母表示黑色节点，小写字母表示红色节点。根据问题2的描述和该情况的定义，我们知道其中n、p、u分别是三个红色的节点。而n的祖父节点G一定是一个黑色节点。 这点可以由红黑树的属性4的逆否命题保证：如果一个节点的任何孩子节点是红色的，那么该节点一定是黑色的。
对于这类问题，我们直接反转p、u和G的颜色。这样对于节点n来说，它的父节点p就变成了黑色，不再违背规则4了。由于我们反转了祖父节点和父辈节点的颜色，所以不会改变从g到其叶子节点路径上黑色节点的数目， 所以不会违背规则五。
但是，这一改变将使得祖父节点g变成红色，而g有可能是整棵树的根节点，也可能它的父节点是红色的。所以，我们需要继续调整节点g让其满足红黑树特性。
Case 2: 节点n的叔叔U是黑色的，而n是其父节点p的右(左)孩子
/* p = G->left | p = G->right
* G G | G G
* / \ / \ | / \ / \
* p U --> n U | U p --> U n
* \ / | / \
* n p | n p
*/
右边的注释分别描述了父节点p是祖父节点G的左孩子和右孩子时的情况2。这种情况下，节点n的叔叔是黑色的。我们通过一个简单的旋转操作，处理这一情况。如果p是G的左孩子，就对p左旋； 如果p是G的右孩子，就对p右旋。
这一旋转操作并不能够改变节点n和p违背规则4的问题，但如果我们交换节点n和p的角色，就可以将此类情况转换为Case 3来处理。
旋转操作并没有引入其它违背项。因为节点n和p都是红色的，并且旋转操作并没有改变两者的颜色，也没有在两者之间引入任何节点，所以不可能改变G到根节点路径上的黑色节点数量。
Case 3: 节点n的叔叔U是黑色的，而n是其父节点p的左(右)孩子
/* p = G->left | p = G->right
* G P | G P
* / \ / \ | / \ / \
* p U --> n g | U p --> g n
* / \ | \ /
* n U | n U
*/
对于这种情况，如右边注释所示，我们需要旋转祖父节点G，并修改相关节点的颜色。如果p是G的左孩子，就对G右旋；如果p是G的右孩子，就对p左旋。
因为G本身是黑色的节点，直接对其旋转将导致经过节点n的简单路径上的黑色节点数量减一。这将打破红黑树的规则五，是我们所不期望的。此时，我们只需要交换G和p的颜色，就可以修复这一问题。
实际上，Case 3是一种终结情况。我们可以看到变换之后的子树中，不存在一个红色的节点n，其父节点也是红色的情况。而且子树的根节点是黑色的，也不会像Case 1那样， 在子树的根节点处产生违背红黑树特性的问题。
3. 删除
对于红黑树的删除节点操作，大体上也可以分为两个阶段。首先，像操作二叉树那样将目标节点从树中将之移除。相比于二叉树的删除操作，这个移除过程还需要记录和跟踪被移除的节点及其父节点。 移除之后，我们还需要根据实际移除的节点颜色对可能违背的红黑树规则做些调整。
下面是删除节点操作的代码片段。在remove函数的一开始，我们定义了三个指针n, x, 和xp。其中n用于记录实际从树中移除的节点，x记录实际填补节点n的节点。 xp则是节点n的父节点，也是替换之后x节点的父节点。
void remove(RBTreeNode<T> * node) {
RBTreeNode<T> *n, *x, *xp;
在实际移除之前，我们先记录下移除目标节点node以及它的颜色nc。
n = node;
RBNodeColor nc = n->color;
如果目标节点node只有一个孩子，我们就可以用它唯一的孩子替代它本身。如果node没有孩子，就直接用叶子节点(NIL)替代之。替代过程通过父类成员函数replace_subtree实现， 并用指针x和xp记录下替代节点和替代之后的父节点。
if (NULL == node->l) {
x = node->right();
this->replace_subtree(node, node->r);
xp = node->parent();
} else if (NULL == node->r) {
x = node->left();
this->replace_subtree(node, node->l);
xp = node->parent();
}
如果目标节点有两个孩子，我们需要用目标节点的后继来替代该节点。我们对其右子树求取最小节点，记录为n，并记录下实际被移除的节点颜色nc。
else {
n = (RBTreeNode<T>*)node->r->subtree_min_node();
nc = n->color;
后继节点有两种情况：其一，后继节点n是目标节点的孩子。对于这种情况，我们只需要用后继节点直接替换目标节点就可以达到移除目标节点的目的。其二， 后继节点n不是目标节点的孩子，那么我们可以先用n的右孩子替代后继节点，再将移除后的后继节点替换目标节点。实际上第一种情况也可以差分成第二种情况的两部分。 两者本质的不同在于指针xp的取值不同。
x = n->right();
if (node == n->p)
xp = n;
else {
this->replace_subtree(n, n->r);
xp = n->parent();
n->r = node->r;
n->r->p = n;
}
this->replace_subtree(node, n);
n->l = node->l;
n->l->p = n;
n->color = node->color;
}
最后，我们需要根据实际移除节点的颜色对可能违背的红黑树特性进行修复。我们只需要在移除黑色节点的时候进行修复。因为对于只有单个孩子的目标节点，移除红色的节点并不会改变红黑树的特性， 而黑色节点将改变树中部分路径的黑色节点数量，以致于违背规则五。而右两个孩子的目标节点，我们用后继节点替代了目标节点，并且在上面的第29行中赋予了目标节点的颜色，所以如果该后继节点是黑色的， 也会导致规则五的破坏，而红色则没有影响。
if (RBNodeColor::BLK == nc)
remove_fixup(x, xp);
delete node;
}
当我们实际移除了一个黑色节点之后，将可能产生如下三个问题。
- 被移除的节点n是根节点，而替换之的节点x是红色的，将违背规则二;
- 用红色的节点x替代节点n，导致替换后x和xp都是红色的，将违背规则四;
- 由于节点n本来是黑色的，所以用x替换了n之后，将导致经过x的简单路径比其它路径少一个黑色节点，这将违背规则五。
其中问题2和问题3是同时出现的，问题1不会与其它两个问题同时出现。我们可以简单地给节点x赋予黑色，来解决问题1和问题2，同时可以解决伴随着问题2一起出现的问题5。而如果节点x本身是黑色的， 情况就会复杂一些，需要分类讨论。
/* x = p->left | x = p->right
* P W | P W
* / \ / \ | / \ / \
* X w --> p D | w X --> C p
* / \ / \ | / \ / \
* C D X C | C D D X
*/
Case 1: 节点X的兄弟w是红色的
如右边的注释所示，由于节点w是红色的，根据规则四及其逆否命题，我们可以确定w的父节点和孩子节点都是黑色的。
对于这种情况，我们对节点P进行旋转，如果X是P的左孩子就右转，如果是右孩子就左转。同时交换节点w和P的颜色。这一操作并不能改变任何红黑树的特性，它存在的意义纯粹是为了将这一情形转换为其它三种Case。
Case 2: 节点X的兄弟W是黑色的,并且W的两个孩子都是黑色的
/* x = p->left | x = p->right
* p p | p p
* / \ / \ | / \ / \
* X W --> X w | W X --> w X
* / \ / \ | / \ / \
* C D C D | C D C D
*/
这种状态下，节点p的颜色已经无关紧要了。我们只需要将节点W的颜色改为红色，就可以修复以p为根节点的子树中的规则五。
因为W的两个孩子都是黑色的，所以修改w的颜色为红色是满足规则4的。在p为根节点的子树中，经过X的简单路径中的黑色节点数量比经过W的少1。我们直接将W改为红色，可以降低经过w的简单路径的黑色节点数量。
此时，我们能够保证子树p是满足红黑树特性的，下面还需要以p作为新的X节点重新考察移除节点后的三个问题。
/* x = p->left | x = p->right
* p p | p p
* / \ / \ | / \ / \
* X W --> X C | W X --> D X
* / \ \ | / \ /
* c D w | C d w
* \ | /
* D | C
*/
Case 3: 节点X的兄弟W是黑色的,并且W只有右(左)孩子是黑色的
如右边的注释所示，这种情况下节点c(d)是红色的。我们对节点W进行旋转，并且交换c(d)和W的颜色。如果X是p的左孩子则右转，如果是右孩子则左转。
这个转动操作实际上并没有改变红黑树的颜色特性。它只是在处理以X的兄弟节点W为根节点的子树，经过旋转操作之后，看似增加了该子树的深度， 但是并没有改变该子树的左右两个分支的黑节点数量。
这一操作的目的是要将Case 3转换为Case 4进行处理。转换完之后我们将C(D)看作是新的W节点，此时新W节点的右(左)孩子就是红色的。
/* x = p->left | x = p->right
* p(P) w(W) | p(P) w(W)
* / \ / \ | / \ / \
* X W --> P D | W X --> C P
* / \ / \ | / \ / \
* c d X c | c d d X
*/
Case 4: 节点X的兄弟W是黑色的,并且W的右(左)孩子是红色的
这是一种终结状态。如右边的注释所示，我们对节点p进行旋转。如果X是p的左孩子则左转，如果是右孩子则右转。同时我们需要保证转动后的子树根节点w(W)具有和原来根节点p(P)相同的颜色。
我们将旋转后X的父节点p，和w的右(左)孩子设定为黑色。如此以来经过X的简单路径的黑色节点数量就增加了，同时还能保证其它简单那路径的黑色节点数量不变。至此解决了问题3，修复了规则五。
4. 完
本文中，我们详细描述了红黑树的插入和删除操作。相比于二叉树的实现，它的插入和删除操作相对复杂一些，主要是在修复因为节点的变动而破坏的红黑树规则。 虽然操作是复杂了一些，但是其时间复杂度仍然是\(O(h)\)，其中\(h\)是树的高度。因为红黑树的五条规则的存在，使得它是一种近似的平衡二叉树，对于较大的数据量而言， 复杂的实现方式所带来的系统效率的提升是值得的。