红黑树——以无厚入有间（插入）
首先说一下，关于红黑树有一篇很棒的论文《A dichromatic framework for balanced trees》，作者之一的Robert Sedgewick，想必大家不会陌生。如果有兴趣可以仔细研读一下，里面讲了更多细节的分析，而本文也借鉴了其中的一些思路和配图。
回顾一下之前的结构分析，经验指出：平均而言红黑树大约和AVL树一样深，如此保证了查找效率接近最优。另外他的优点有两个，插入所需要的开销比之前更低，再有就是实践中发生的旋转相对比较少。
而红黑树的具体实现是比较复杂的，这不仅因为可能会发生大量的旋转，还因为一些子树可能是空的（比如10这个节点的右子树），以及处理根的特殊情况（因为没有父节点）。因此我们要用两个标记节点：一个是根；一个是NullNode，类似在伸展树里指示NULL的指针。根标记用来储存$-\infty $和一个真正指向根的右指针。先给出类型声明，因为旋转操作还需要用到，所以继续沿用。
1 #ifndef RB_Tree_h 2 #define RB_Tree_h 3 4 typedef enum{ red,black} Color; 5 6 const int Infinity = 0x3f3f3f3f; 7 const int NegINF = -Infinity -1; 8 struct RedBlackNode; 9 typedef RedBlackNode* RedBlackTree; 10 typedef RedBlackNode* Position; 11 12 struct RedBlackNode { 13 int value,Height; 14 RedBlackTree left; 15 RedBlackTree right; 16 Color col; 17 }; 18 19 Position NullNode=NULL; //needs initialization 20 int max(int a,int b){ return a>b?a:b;} 21 RedBlackTree Insert(int Item,RedBlackTree T); 22 RedBlackTree Delete(int Item,RedBlackTree T); 23 #endif /* RB_Tree_h */ 24 25 static int 26 Height( Position P ) 27 { 28 return P==NULL?-1:P->Height; 29 } 30 31 static Position 32 SingleRotateWithLeft( Position p ) //左-左的情况 33 { 34 Position temp; 35 36 temp = p->left; 37 p->left = temp->right; 38 39 temp->right = p; 40 41 p->Height = max( Height( p->left ), Height( p->right ) ) + 1; 42 temp->Height = max( Height( temp->left ), p->Height ) + 1; 43 44 return temp; /* New root */ 45 } 46 47 static Position 48 SingleRotateWithRight( Position g ) //右-右的情况 49 { 50 Position temp; 51 52 temp = g->right; 53 g->right = temp->left; 54 55 temp->left = g; 56 57 g->Height = max( Height( g->left ), Height( g->right ) ) + 1; 58 temp->Height = max( Height( temp->right ), g->Height ) + 1; 59 60 return temp; /* New root */ 61 }
NullNode标记含义有所变化，为此调整一下打印函数，用一个隐藏的递归过程，这样就很巧妙了，因为不会强迫用户传入T-> right，这留给机器去做。
1 static void DoPrint(RedBlackTree T){ 2 if (T != NullNode) { 3 DoPrint(T->left); 4 printf("%d ",T->value); 5 DoPrint(T->right); 6 } 7 printf("\n"); 8 } 9 10 void Display(RedBlackTree T){ 11 DoPrint(T->right); 12 }
除此之外我们还需要通过初始化来指定头节点。构造第一棵树时，初始化程序要为NullNode分配内存，此后的树可以共享NullNode。
1 RedBlackTree Initialize() 2 { 3 RedBlackTree T; 4 if (NullNode == NULL) { //如果NullNode不存在，就让它成为一个空闲仓库，并且保证合乎红黑树规则 5 NullNode=(Position)malloc(sizeof(struct RedBlackNode)); 6 NullNode->left=NullNode->right=NullNode; 7 NullNode->col=black; 8 NullNode->value=Infinity; 9 } 10 11 //Create the header node 12 T=(Position)malloc(sizeof(struct RedBlackNode)); 13 T->value=NegINF; 14 T->left=T->right=NullNode; 15 T->col=black; 16 17 return T; 18 }
首先是插入操作，与理解红黑树的定义一样，这里我们也必须借助B树的模型才能更好地了解相关算法的原理和过程。也就是说在我们考察每一棵红黑树的时候，在脑海中总是要有一棵对应的B树如影随形，本来红黑树就是4阶B-树嘛。就像“降临：暴君巴拉克”一样2333
与所有的BBST一样，在经过了动态变化之后，红黑树的组成成员不仅发生了变化，而且它们之间的拓扑连接关系也可能发生变化。然而这种变化并不容易直接理解，为此我们需要借助B树的影子。就像理解红黑树的定义一样，我们会发现，红黑树与其对应的影子B树之间的关系非常好理解，而且反之亦然。而更重要的是，站在新的视角来看，前后两棵影子B树之间的关系也将变得一目了然。这样一种理解的方式，看似迂回，但很快就会感受到它的效率反而是最高的。
假设我们要插入e这个数，不妨先用BST常规插入算法看看，然后予以改进。插入后相应的会生成一个新的末端节点x，平凡情况的树根就不考虑了。这意味着 它的父亲必然是存在的，接下来将x染为红色（除非是根）。这样做的好处是：红黑树的各条规则能够尽量满足。来逐条考察一下
- 树根是黑色的，叶子（即使是NULL）也是黑色的
- 除了root和leaf，每一个节点或红或黑
- 如果一个节点是红色的，那子节点必须是黑色
- 从某个节点到叶子的路径上必须包含相同数目的黑色节点
树根节点和所有的外部节点依然是黑的，在通往各个外部节点的路径上，黑节点的数目因为没有变化，我们染的红色，所以依然保持全局的一致性。然而第三条规则却未必满足。考察这个新插入的红色节点x，作为末端的叶节点，它的2个孩子都是外部节点，所以都是黑的。然而父节点颜色不确定，此时p就是这样一个可黑可红的节点，如果它的确是黑的那第三条规则也同时满足，整个插入就成功返回。然而问题在于p的确可能原本就是红的，比如这样：
关于边的虚实，作如下约定：凡是指向黑色节点或者颜色不定的节点的边，都用实线来表示。所有指向红色节点的边，都用虚线表示。这种方式可以更好地帮助我们思考和分析，因为这类虚边在经过提升变换之后都会变成是水平方向。新插入的节点x与它的父亲p如果同时为红色，是红黑树规则所禁止的，这样一种非法的情况也因此称作双红缺陷。如何修复呢？我们首先要考察x的祖父节点g，注意，此时的g必然存在，否则作为树根的节点p是不可能为红色的。然后，作为红色节点p的父亲，节点g也必然是黑色的。此外我们还需要考查g的另一个孩子u（uncle of x），当然节点u的颜色也是不定的。因此以下就根据这个节点u的颜色分2种情况分别处理。
首先假设u是黑色（而且约定NULL都是黑色）。举个例子，还是那幅图，插入3 or 8这种情况是允许的，而插入99就不行了（双红）。
现在抽象地考虑，我们分别有Grandparent，Parent，Sibling和待插入节点X，用伸展树中的术语，他们之间可以构成一字链or之字链，可以采用旋转解决。
一字形分布，采用单旋转
之字形分布，双旋转。（这两个图待会讲u是红色的时候还会提到，记得翻回来）
以上两种情况还分别有另外的镜像对称情形，分别是右右，和右左。用原论文中的图表示如下，不难理解：
而他们4种都说明了如果u（或者说是下图的S）是黑色，那么可以旋转解决。而编写程序时我们必须记录父节点，祖父节点以及为了重新连接而记录的曾祖父（Great-GrandParent）节点。在这两大种情况下，子树的新根（P，X）都被涂成黑色，因此即使原来的曾祖父是red，我们也排除了两个相邻节点都是red的可能。最重要的是，经过旋转后保持了路径上黑节点数目不变。
所以旋转微调和总体双红修复的步骤如下：
//在X处执行旋转 static Position Rotate(int Item,Position par) { if (Item < par->value) return par->left = Item < par->left->value ? SingleRotateWithLeft(par->left) : SingleRotateWithRight(par->left); else return par->right = Item < par->right->value ? SingleRotateWithLeft(par->right) : SingleRotateWithRight(par->right); } //双红修复 static Position X,P,GP,GGP; void HandleReorient(int Item,RedBlackTree T) { X->col=red; //默认染红，下面孩子还是得遵守规则，保证是黑 X->left->col=black; X->right->col=black; if (P->col == red) { //引发双红缺陷 GP->col=red; if ((Item < GP->value) != (Item < P->value)) //两者异或为真，意味着是之字形，要在父节点多做一次旋转，否则以曾祖父为轴做单旋转 P = Rotate(Item, GP); X = Rotate(Item, GGP); X->col=black; } T->right->col=black; //让新根染黑 }
为了进一步加深理解，我们从B树角度看一看两种情况：
此时的x p g下属应该共有4个子树，尽管它们都有可能是外部节点（NULL），但是根据红黑树红色节点只能有黑色孩子的规则——包括u在内，它们都必然是黑的。而且既然在此前，这是一棵合法的红黑树，那这4个黑节点的黑高度也应该是一样的。现在借助提升变换，将此前指向红色节点的所有虚边都收缩起来，局部的这祖孙三代节点就会合并为一个4阶B树中的内部节点。貌似这样的超级节点并没有违规？因为它们下属的分支都不超过4阶B树的上限。确切的说，唯一的缺陷是在每个超级节点居中的这个关键码不是黑色。因此从B树的角度看这种调整就很简明了：并不需要调整B树的拓扑结构，而只需在违规的超级节点中对关键码重新的染色。a的情况，只需交换p和g的颜色。
而b的情况只需交换x和g的颜色。
整个调整过程以及效果从B树的角度来看，是非常清晰的。双红缺陷之所以是非法的，从B树的角度可以认为是，因为在某个原本是3叉的节点中，插入了一个红色的关键码，从而使得原先的黑关键码不再居中。对照所有的4种情况不难验证这点。而调整之后的效果相当于，B树的拓扑结构不变，而在对应的4叉节点中3个关键码的颜色已经改为合法的红黑红模式。请要注意的是在这种情况下，即使红黑树的拓扑结构有所调整，但也仅限于局部。而更重要的是，这种调整是一步到位的，不用后续其他的调整了。因此就全树的拓扑连接关系的变化量而言，必然是不超过$O\left( 1 \right)$。
到这一步一切顺利，下面考虑u是红色的情况，比如说在下图插入79。
这种情况下从子树的根到C的路径上有一个黑色节点（翻到上面旋转的例图）。旋转之后必然还是只有一个，但两种情况下，通向C的路径上都有三个节点（新根，G，S），这里面只有一个可能是黑的，为了保证不能有连续的红色节点，就必须把S和子树的新根都涂成红色，而把G和GGP都涂成黑色。
这么说我都感觉有点绕，现在从B树的角度再考虑一下。这里也只给出了两种情况，忽略掉对称的另两种情况。
图 M
图 N
同样借助提升变换，将所有指向红色节点的虚边收缩起来。于是从B树的角度来看 局部的这4个节点将合并为一个包含4个关键码的内部节点。4个关键码，对应于5个分支。这无论是a,b哪种情况，这样的内部节点在4阶B树中都是非法的。而用B树的语言来说，它们之所以非法，是因为上溢。因此，与其说我们是在红黑树中修复双红缺陷，不如说是在对应的4阶B树中修复上溢缺陷，这二者完全是一回事。那B树中如何修复上溢？回忆一下。
需要在出现问题节点中找到居中的那个关键码，并且以它为界将原先的大节点分裂为左右两个新的节点，而居中分界的这个关键码则应被取出来，上移并插入到父节点中的适当位置，这样一个转换，只是B树中的基本操作，很好理解。
因此总体看来，将此前的红黑树转换为对应的4阶B树，从提升变换的角度来看 也非常好理解。从变换之后的B树到红黑树通过提升变换，也非常易于理解，这样迂回的过程，比我们试图直接去理解红黑树的调整过程反过来更为简明。也印证了前面的那幅示意图。
从红黑树的角度对于这种情况，只需将节点p由红转黑，同时节点g，u由黑转红。而从B树的角度来看，等效于对一个刚刚发生上溢的节点实施一次分裂操作，同时居中的关键码被提升并加入到父节点之后将转为红色。当然在g的左或右至少应该有一个黑色的关键码，如果有红色，就再次发生了双红缺陷，没关系，继续套用这个方法即可。因为这个过程是逐层向上蔓延，因此顶多复杂度是$O\left( h \right)$。最后需要强调的一点是：尽管调整过程从B树的角度来看，发生了拓扑结构的变化。但是从红黑树的角度来看，除了节点的颜色会变，全树的拓扑连接关系并没有任何变化。也就是说，尽管重染色操作的次数可能会高达$O\left( \log n \right)$次，但拓扑结构的变化却依然控制在常数的范围。
概括来讲，自顶向下的过程中，当我们看到一个节点X有两个红色儿子，就让X成为红色，而两个儿子变成黑色。
当叔父节点u为红色时，修正双红缺陷导致的红黑树拓扑结构没有变化。
综上所述，旋转和旋转和结构调整的步骤如下：
1 RedBlackTree 2 Insert(int Item,RedBlackTree T) 3 { 4 X=P=GP=T; 5 NullNode->value=Item; //此时经过初始化，NullNode已经是一个空闲节点，存入指定的数值 6 while (X->value != Item) //自树根拾级而下，扫除一切uncle为红的情况 7 8 { 9 GGP=GP; GP=P; P=X; 10 if(Item < X->value ) 11 X=X->left; 12 else 13 X=X->right; 14 //节点的两个孩子都是红色，转换成B树意味着内部节点上溢，如图M，N，需要进行修复 15 if( X->left->col == red && X->right->col == red ) 16 HandleReorient(Item, T); 17 } 18 //走到这一步时，X->value已经是期望的Item了 19 if(X != NullNode) 20 return NullNode; //重复 21 22 //否则就创建新的节点接入 23 X=(Position)malloc(sizeof(struct RedBlackNode)); 24 X->value=Item; 25 X->left = X->right = NullNode; 26 27 if(Item < P->value) 28 P->left=X; 29 else 30 P->right=X; 31 HandleReorient(Item, T); 32 33 return T; 34 }
最后分析一下插入的复杂度。首先这里无非牵涉到两种基本的操作：旋转和对节点颜色的重新定义。二者都是局部的基本操作，单次只需$O\left( 1 \right)$，因此我们只需统计在整个的修正过程中，二者各自总共执行了多少次。这是整个修正算法的流程图：
可以看到通过判断u节点的颜色，无非两个分支。其中u节点为黑的这个分支相对简单
我们只需做一次局部的旋转调整，再做常数次的染色操作就完成了。也就是说在这种情况下，旋转至多一轮2次。而染色呢？至多牵涉到两个节点，都是常数。当然u节点为红色的情况比较复杂，因为尽管在每一个节点处我们只需做常数次的重新染色，但是事情未必彻底解决，因为由此可能导致在更高的节点处进而出现双红缺陷，此时我们还需要重新回到算法的入口，再来一次。在最坏的情况下，这种情形有可能会出现多达$O\left( \log n \right)$次。总结如下：
要注意的是，在右半侧循环中，我们只需做重新染色，而不用做结构调整
而另外半边，一旦做过结构的调整，整个算法就会随即结束。因此总体而言，整个修复过程中可能会执行很多次染色操作，但ReOrient在整个修复过程中至多只会执行$O\left( 1 \right)$次。还记得吧，上一篇讲过我们为什么会更加在意拓扑重构——因为这类操作对于可持久化结构而言是至关重要的。当然对于插入操作的这些性能要求，AVL树同样满足，然而正如我们在前文所指出的，AVL的删除操作却不具有这样的性能。那么红黑树呢？让我们拭目以待。