算法导论红黑树的探讨 | Fogsail
第一部分：红黑树表示与旋转红黑树是一种平衡二叉树，其性质不再赘述。红黑树的数据结构如下：
123456789101112131415161718192021222324struct RB_node{
RB_node * //右孩子
RB_node * //父节点
//结点的颜色
RB_node(RB_node* init,int c_init,int num):left(init),right(init),parent(init),color(c_init),key(num){}};struct RB_tree{
nil=new RB_node(NULL,BLACK,INFINITY);
//树的哨兵必然为黑色
}};
值得特别说明的是，这里的T-&nil表示的是哨兵结点，是为了方便之后的运算。
红黑树的旋转过程，如下图所示：
注意旋转的前后，从左到右，子树依次是y-&left y-&right x-&right，但是y-&right的parent变成了x了！
红黑树旋转的过程如下给出：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455void left_rotate(RB_tree *T,RB_node *x){
RB_node *y=x-&
//左孩子结点
x-&right=y-&
//这一部处理的是加在x，y之间的“内结点”，y-&left原先
//夹在x-&left和y-&right之间，旋转之后子树的相对顺序不变，最外边的结点是
//x-&left和y-&right，注意是围绕x和y进行的旋转，所以子树的相对位置保持不变
if(y!=NULL && y-&left!=NULL)
y-&left-&parent=x;
//旋转之后需要重新更新parent结点信息
y-&parent=x-&
//这个时候y作为子树的根了，y要连到祖先中！
if(x-&parent==NULL)
T-&root=y;
else if(x-&parent-&left==x)
x-&parent-&left=y;
x-&parent-&right=y;
//保证x与祖先结点相连接
//最后处理x和y的关系
y-&left=x;
x-&parent=y;}//右旋，对称的代码void right_rotate(RB_tree *T,RB_node *x){
//只需要把上述代码的相对位置，right和left互换就可以了
RB_node *y=x-&
x-&left=y-&
if(y!=NULL && y-&right!=NULL)
y-&right-&parent=x;
//旋转之后需要重新更新parent结点信息
y-&parent=x-&
if(x-&parent==NULL)
T-&root=y;
else if(x-&parent-&left==x)
x-&parent-&left=y;
x-&parent-&right=y;
//保证x与祖先结点相连接
//最后处理x和y的关系
y-&right=x;
x-&parent=y;}
红黑树的旋转左旋和右旋是对称的。
第二部分：红黑树的插入和性质的维护具体程序：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485void RB_insert_fixup(RB_tree *T, RB_node *z);void RB_insert(RB_tree *T, RB_node *z){
RB_node *y=NULL;
//y作为遍历指针的双亲
RB_node *x=T-&
while(x!=NULL)
if(z-&key&x-&key)
else x=x-&
z-&parent=y;
//y作为遍历指针x的母结点，x遍历寻找合适的插入位置
if(y==NULL)
T-&root=z;
else if(z-&key&y-&key)
y-&left=z;
else y-&right=z;
z-&left=NULL;
z-&right=NULL;
z-&parent=RED;
RB_insert_fixup(T,z);
//最后插入的结点是红色的，与此同时进行红黑树性质的调整}void RB_insert_fixup(RB_tree *T,RB_node *z){
while(z-&parent-&color==RED)
if(z-&parent==z-&parent-&parent-&left)
RB_node *y=z-&parent-&parent-&
//设置叔结点
if(y-&color==RED)
z-&parent-&color=BLACK;
//父节点的黑色可以下放给两个结点
y-&color=BLACK;
z-&parent-&parent-&color=RED;
z=z-&parent-&
//z沿树上升
if(z==z-&parent-&right)
//内结点先旋转成外节点
left_rotate(T,z);
z-&parent-&color=BLACK;
//改变颜色之后，z的兄弟结点和z颜色相同
z-&parent-&parent-&color=RED;
//红黑树局部恢复平衡
right_rotate(T,z-&parent-&parent);
//这个技巧是：改变颜色之后，然后旋转，这样不破坏红黑树性质
//与此同时，结点沿树上升
RB_node *y=z-&parent-&parent-&
if(y-&color==RED)
z-&parent-&color=BLACK;
y-&color=BLACK;
z-&parent-&parent-&color=RED;
z=z-&parent-&
if(z==z-&parent-&left)
right_rotate(T,z);
z-&parent-&color=BLACK;
z-&parent-&parent-&color=RED;
left_rotate(T,z-&parent-&parent);
T-&root-&color=BLACK;}
实现过程说明：红黑树的插入是比较容易理解的，下面着重来讨论红黑树插入的调整：
情形一：这个时候只要把根部A这个点的黑色，下放给两个孩子结点，这样红黑树的性质得到保持，这个时候刚插入的节点沿树上升就可以了。
情形二：如果z是内节点，要首先旋转成外结点，因为外节点的相对位置是不变的，内节点在旋转的过程中还会更换parent！所以用外节点处理方便，值得注意的是，在旋转过程中，z的相对高度要保持不变，所以要执行z=z-&parent，然后再旋转！这样沿树上升的时候，保证所有的结点都得到处理！
最后一步改变颜色，做到了红黑树的局部平衡，这个时候改变颜色之后再执行旋转，不破坏红黑树的平衡性，与此同时，z结点沿树上升，这样局部平衡得到保持。最后只要树根置为black就可以了。
第三部分：红黑树的删除红黑树删除的代码和普通二叉树的删除没有多少区别，主要是要关注：删除一个结点之后，记得寻找这个结点的后继，后继不一定是right，而是min(x-&right)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141//删除调整，这个时候x有两重黑色void RB_delete_fixup(RB_tree *T, RB_node *x){
RB_node *w=NULL;
while (x!=T-&root && x-&color==BLACK)
if(x==x-&parent-&left)
w=x-&parent-&
//w为x的兄弟结点
if(w-&color==RED)
w-&color=BLACK;
//将这种情况划归为下面一种情况
w-&parent-&color=RED;
left_rotate(T,x-&parent);
w=x-&parent-&
if(w-&left-&color==BLACK && w-&right-&color==BLACK)
W-&color=RED;
//x和w的黑色沿树上升，注意到x有双重黑色，所以x的颜色不变
//变得是w，x-&parent的颜色
if(w-&right-&color==BLACK)
w-&left-&color=BLACK;
w-&color=RED;
//同样，内节点变为外节点
right_rotate(T,w);
w=x-&parent-?
w-&color=x-&parent-&
//这里x-&parent的颜色不确定，但是w的颜色是黑色
//x有双重黑色，通过改变颜色加上旋转，可以将双重黑色表现在图中，这样完成了红黑树的局部平衡
x-&parent-&color=BLACK;
w-&right-&color=BLACK;
left_rotate(T,x-&parent);
//红黑树局部平衡了
w=x-&parent-&
if(w-&color==RED)
w-&color=BLACK;
x-&parent-&color=RED;
right_rotate(T,x-&parent);
w=x-&parent-&
if(w-&left-&color==BLACK && w-&right-&color==BLACK)
w-&color=RED;
if(w-&left-&color==BLACK)
w-&right-&color=BLACK;
W-&color=RED;
left_rotate(T,w);
w=x-&parent-&
w-&color=x-&parent-&
x-&parent-&color=BLACK;
w-&left-&color=BLACK;
right_rotate(T,x-&parent);
x-&color=BLACK;}void transplant(RB_tree *T, RB_node *u, RB_node *v){
if(u-&parent==T-&nil)
T-&root=v;
else if(u==u-&parent-&left)
u-&parent-&left=v;
else u-&parent-&right=v;
if(v!=NULL)
v-&parent=u-&}RB_node *tree_minimum(RB_tree *T,RB_node *x){
while (x-&left!=NULL) {
return}void RB_delete(RB_tree *T, RB_node *z){
RB_node *y=z, *x;
int y_original_color=y-&
if(z-&left==NULL)
transplant(T,z,z-&right);
else if(z-&right==NULL)
transplant(T,z,z-&left);
y=tree_minimum(T,z-&right);
//这里是查找z的后继，为y，用y来代替z的位置
y_original_color=y-&
if(y-&parent==z)
x-&parent=y;
transplant(T,y,y-&right);
y-&right=z-&
y-&right-&parent=y;
transplant(T,z,y);
y-&left=z-&
y-&left-&parent=y;
y-&color=z-&
if(y_original_color==BLACK)
RB_delete_fixup(T,x);
//x为y的孩子结点，y的删除会影响x的相关性质}
具体来看红黑树删除的调整：
情形一这个时候x的兄弟节点w是red，一个红节点必然跟着两个黑节点，这个时候改变颜色，并且执行旋转，可以将这种情况划归为第二种情况，就是x和w都是黑色。为什么要这么做？主要的原因是x有双重黑色，我们需要让x的黑色沿树上升，w的黑色也沿树上升，w为白色，要想办法让它变成黑色。改变颜色+旋转是常用的方法。
这个时候需要让x和w的黑色都沿树上升。注意到这个时候x有双重黑色，所以x的黑色不改变。
这个时候和插入调整一样，内节点要转化成外节点。值得注意的是，这个时候w-&left的颜色一定是red，因为不是的话就变成了第二种情况啦！这个时候红色的结点是内结点，要将它旋转成外节点处理，理由在插入调整的过程中已经说了很清楚了。
这个时候要注意的是：x-&parent的颜色没有确定下来，但是w的颜色一定是black。交换颜色的代码是：123w-&color=x-&parent-&x-&parent-&color=BLACK;w-&right-&color=BLACK;
如图所示，改变颜色+完成旋转之后，x的双重黑色已经体现出来了。这个时候红黑树达到了局部平衡。所以将x置为根节点，确定颜色就可以了。
第四部分：算法导论课后习题解答13.1红黑树的性质13.1-1
13.1-21、不行，违反性质42、不行，违反性质5
13.1-3是，我们在调整过程中就是利用松弛红黑树的性质，最后将T-&root-color置为black。
13.1-4红黑树的黑高为从该点开始，所含有的黑节点的个数，所以红黑树的黑高保持不变。可能的度为：2
这个时候它的两个子节点原来都是黑色3
这个时候一个子节点为红色，另一个为黑色，红色子节点又跟随两个黑色子节点，度为34
两个子节点都是红色
$rh(x) \leq bh(x)$$h(x) = rh(x)+bh(x) \leq 2bh(x)$其中，rh(x)表示红高，bh(x)表示黑高
所以最长的一条最多是最短一条的两倍
黑高为k，内部节点最少为：$2^k-1$最多为：由13.1-5的结论，最长路径$ \leq 2k+1$最多节点为： $2^ {2k+1} -1$
比值最小为0，结点全部为黑色。比值最大为2：1参见13.1-1图，一个black两个结点都是红的，每个红节点又有两个黑节点，红节点和黑节点的比值为：4：2=2（内部节点，不算根节点）
13.2旋转13.2-1已写出
n个节点有n-1条边，所以可能有n-1种旋转
可以发现b的深度不变，a的深度增加，c的深度减少
最坏的情况，仅有左子树，假设左子树有n个节点，可以看出左子树旋转成右子树需要n-1次。这样左子树变成一条右侧伸展的链。
从左侧伸展的链旋转成为右侧伸展的链，最坏需要n-1的时间，其余任何一种情况，所需时间均少于n-1
T1可以右转成T2，可知若有i个结点，需要旋转i-1条边
$\sum_{i=1}^n i = O(n^2)$
13.3插入13.3-1
如果将z染色成黑色，很显然违反红黑树性质5，违反红黑树性质5，做调整的时候是针对高度来调整。这个时候红黑树还必须满足一种高度平衡：就是任意路径，从root到nil，红黑树的黑高差恒等于0在调整的时候比较麻烦。实际上这是属于类AVL树了。
高度平衡的二叉树，是AVL树，这是另外一种平衡二叉树。
z为叶子节点，则z-&parent为根节点。根节点的颜色肯定恒为黑色，这个时候退出循环while(z-&parent-&color==RED)那么也就遍历不到z-&parent-&parent了。
插入的n-1个节点都为black，当插入第n个节点的时候，新插入的节点为红色，满足红黑树性质。
123456789101112131415161718192021222324252627RB_node *tree_search(RB_tree *T, RB_node *x, int k, RB_node *par, RB_node *p_par){
//人为定义一个tree_search函数，从根节点遍历，寻找x的parent和parent-&parent
while(x!=T-&nil && k!=x-&key)
if(k&x-&key)
else x=x-&
if(k!=x-&key)
//如果没有找到待查找的值，此时x=x-&child
//记录下遍历前的x=p_par，遍历后的x=par，返回x，此时用par和p_par表示
return x；}void RB_insert_fixup(RB_tree *T, RB_node *z){
//相关代码
RB_node *par=T-&nil, *p_par=T-&
tree_search(T,T-&root,z-&key,par,p_par);
//将原来的z-&parent用par代替，z-&parent-&parent用p_par代替}
13.4删除13.4-1在执行RB_delete_fixup之后，可以发现，x=root, x-&color=BLACK，所以树根一定是黑色的
此时不进入循环，x-&color=BLACK，恢复性质4
1) 1、4、5行检查哨兵，因为被删除的节点没有孩子，所以检查T-&nil的情况2) 左旋，右旋的时候，w的兄弟没有孩子，此时检查哨兵
13.4-5检查在稿纸上进行
情况一，w的颜色为红色，所以x-&parent的颜色一定是黑色
不一样如下图
其中，灰色的节点代表刚刚插入又删除的节点。
如果文章对您有用，请随意打赏，谢谢支持！
支付宝打赏学习笔记之红黑树 -
学习笔记之红黑树
目录(?)[+]
红黑树的平衡红黑树的旋转操作红黑树上结点的插入
红黑树上结点的删除
介绍另一种平衡二叉树：红黑树（Red Black Tree），红黑树由Rudolf Bayer于1972年发明，当时被称为平衡二叉B树（symmetric binary B-trees），1978年被Leonidas J. Guibas&和Robert Sedgewick改成一个比较摩登的名字：红黑树。
红黑树和之前所讲的AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。不过在我了解了红黑树的实现原理后，并不相信这是真的，关于这一点我们会在后面进行讨论。
红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时，已经领教过AVL树的复杂，但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。
首先来一个Silverlight做的红黑树的动画，它有助于帮你理解什么是红黑树。这里需要注意，必须安装Silverlight 2.0 RTW&才能正常运行游戏，下载地址：
/silverlight/resources/install.aspx?v=2.0
使用注意事项：
l&&&&&&&&&结点只接收整数，如果在添加和删除操作中输入非法字串，则会随机添加或删除一个0~99之间的整数。
l&&&&&&&&&可以不在编辑框中输入数字，直接单击添加和删除按钮进行添加和删除操作。
l&&&&&&&&&可以拖动拖动条控制动画速度。
红黑树的平衡
红黑树首先是一棵二叉查找树，它每个结点都被标上了颜色（红色或黑色），红黑树满足以下5个性质：
1、&每个结点的颜色只能是红色或黑色。
2、&根结点是黑色的。
3、&每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。
4、&如果一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、&对于每个结点来说，从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。
红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看图1中的左边这张图，如果不使用黑哨兵，它完全满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。
要看真正的红黑树请在以上动画中添加几个结点，看看是否满足以上性质。
红黑树的旋转操作
红黑树的旋转操作和AVL树一样，分为LL、RR、LR、RL四种旋转类型，差别在于旋转完成后改变的是结点的颜色，而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画：
/abatei/archive//1335031.html
红黑树上结点的插入
在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。
为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点；使用“父”字表示新插入点的父结点；使用“叔”字表示“父”结点的兄弟结点；使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况：
如图3所示，如果新点的父结点为黑色结点，那么插入一个红点将不会影响红黑树的平衡，此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见，从而使红黑树需要旋转的几率相对AVL树来说会少一些。
如果新点的父结点为红色，这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示，由于父结点为红色，此时可以判定，祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作，而每次进行不平衡判断的起始点（我们可将其视为新点）都不一样。所以我们在此使用一个蓝色箭头指向这个起始点，并称之为判定点。
当叔父结点为红色时，如图4所示，无需进行旋转操作，只要将父和叔结点变为黑色，将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色，从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。
需要注意，无论“父”在“叔”的左边还是右边，无论“新”是“父”的左孩子还是右孩子，它们的操作都完全一样。
当叔父结点为黑色时，需要进行旋转，以下图示了所有的旋转可能
可以观察到，当旋转完成后，新的旋转根全部为黑色，此时不需要再向上回溯进行平衡操作，插入操作完成。需要注意，上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。
其实红黑树的插入操作不是很难，甚至比AVL树的插入操作还更简单些。但删除操作就远远比AVL树复杂得多，下面就介绍红黑树的删除操作。
红黑树上结点的删除
红黑树本身是一棵二叉查找树，它的删除和二叉查找树的删除类似。首先要找到真正的删除点，当被删除结点n存在左右孩子时，真正的删除点应该是n的中序遍在前驱，关于这一点请复习二叉查找树的删除。如图9所示，当删除结点20时，实际被删除的结点应该为18，结点20的数据变为18。
所以可以推断出，在进行删除操作时，真正的删除点必定是只有一个孩子或没有孩子的结点。而根据红黑树的性质可以得出以下两个结论：
1、&删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点。
2、&如果真正的删除点是一个红色结点，那么它必定是一个叶子结点。
理解这两点非常重要，如图10所示，除了情况(a)外，其他任一种况结点N都无法满足红黑树性质。
在以下讨论中，我们使用蓝色箭头表示真正的删除点，它也是旋转操作过程中的第一个判定点；真正的删除点使用“旧”标注，旧点所在位置将被它的的孩子结点所取代（最多只有一个孩子），我们使用“新”表示旧点的孩子结点。删除操作可分为以下几种情形：
1、旧点为红色结点
若旧点为红色结点，则它必定是叶子结点，直接删除即可。如图11所示
2、一红一黑
当旧点为黑色结点，新点为红色结点时，将新点取代旧点位置后，将新点染成黑色即可（如图12所示）。这里需要注意：旧点为红色，新点为黑色的情况不可能存在。
当旧点和新点都为黑色时（新点为空结点时，亦属于这种情况），情况比较复杂，需要根据旧点兄弟结点的颜色来决定进行什么样的操作。我们使用“兄”来表示旧点的兄弟结点。这里可分为红兄和黑兄两种情况：
由于兄弟结点为红色，所以父结点必定为黑色，而旧点被删除后，新点取代了它的位置。下图演示了两种可能的情况：
红兄的情况需要进行RR或LL型旋转，然后将父结点染成红色，兄结点染成黑色。然后重新以新点为判定点进行平衡操作。我们可以观察到，旋转操作完成后，判定点没有向上回溯，而是降低了一层，此时变成了黑兄的情况。
黑兄的情况最为复杂，需要根据黑兄孩子结点（这里用“侄”表示）和父亲结点的颜色来决定做什么样的操作。
3.2.1&黑兄二黑侄红父
如图14所示，这种情况比较简单，只需将父结点变为黑色，兄结点变为黑色，新结点变为黑色即可，删除操作到此结束。
3.2.2&黑兄二黑侄黑父
如图15所示，此时将父结点染成新结点的颜色，新结点染成黑色，兄结点染成红色即可。当新结点为红色时，父结点被染成红色，此时需要以父结点为判定点继续向上进行平衡操作。
3.2.3&黑兄红侄
黑兄红侄有以下四种情形，下面分别进行图示：
由以上图例所示，看完以上四张图的兄弟有可能会有一个疑问，如果情形1和情形2中的两个侄子结点都为红色时，是该进行LL旋转还是进行LR旋转呢？答案是进行LL旋转。情形3和情形4则是优先进行RR旋转的判定。
&& &教你透彻了解红黑树
作者&July、saturnman&&&日
本文参考：Google、算法导论、STL源码剖析、计算机程序设计艺术。
本人声明：个人原创，转载请注明出处。
推荐阅读：Left-Leaning Red-Black Trees,&Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.
------------------------------
红黑树系列，四篇文章于今日已经完成。[二零一一年一月九日]
教你透彻了解红黑树：
http://blog.csdn.net/v_JULY_v/archive//6105630.aspx
红黑树算法的层层剖析与逐步实现& [此文被推荐]
http://blog.csdn.net/v_JULY_v/archive//6109153.aspx
教你彻底实现红黑树：红黑树的c源码实现与剖析
http://blog.csdn.net/v_JULY_v/archive//6114226.aspx
一步一图一代码，一定要让你真正彻底明白红黑树 [最后更新]
http://blog.csdn.net/v_JULY_v/archive//6124989.aspx
------------------------------
一、红黑树的介绍
先来看下算法导论对R-B Tree的介绍：
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其
他路径长出俩倍，因而是接近平衡的。
前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。
下面，在具体介绍红黑树之前，咱们先来了解下 二叉查找树的一般性质：
1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。
&&& 因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。
&&& //至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树 第12.4节。
2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。
而红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。
ok，我们知道，红黑树上每个结点内含五个域，color，key，left，right。如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
下图所示，即是一颗红黑树：
此图忽略了叶子和根部的父结点。
二、树的旋转知识
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行
插入、删除结点等操作时，红黑树依然能保持它特有的性质（如上文所述的，五点性质）。
树的旋转，分为左旋和右旋，以下借助图来做形象的解释和介绍：
如上图所示：
当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为树内任意右孩子而不是NIL[T]的结点。
左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树新的根，而y的左孩子b则成为pivot的右孩子。
来看算法导论对此操作的算法实现（以x代替上述的pivot）：
&LEFT-ROTATE(T,&x)
1&&y&←&right[x]&?&Set&y.
2&&right[x]&←&left[y]&&&&&&?&Turn&y's left subtree into&x's right subtree.
3&&p[left[y]]&←&x
4&&p[y]&←&p[x]&&&&&&&&&&&&&?&Link&x's parent to&y.
5&&if&p[x] =&nil[T]
6&&&&&then&root[T]&←&y
7&&&&&else if&x&=&left[p[x]]
8&&&&&&&&&&&&&then&left[p[x]]&←&y
9&&&&&&&&&&&&&else&right[p[x]]&←&y
10&&left[y]&←&x&&&&&&&&&&&&&?&Put&x&on&y's left.
11&&p[x]&←&y
右旋与左旋差不多，再此不做详细介绍。
对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，
在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。
至于有些书如 STL源码剖析有对双旋的描述，其实双旋只是单旋的两次应用，并无新的内容，
因此这里就不再介绍了，而且左右旋也是相互对称的，只要理解其中一种旋转就可以了。
三、红黑树插入、删除操作的具体实现
&&&三、I、ok，接下来，咱们来具体了解红黑树的插入操作。
向一棵含有n个结点的红黑树插入一个新结点的操作可以在O（lgn）时间内完成。
算法导论：
RB-INSERT(T, z)
&1& y ← nil[T]
&2& x ← root[T]
&3& while x ≠ nil[T]
&4&&&&& do y ← x
&5&&&&&&&& if key[z] & key[x]
&6&&&&&&&&&&& then x ← left[x]
&7&&&&&&&&&&& else x ← right[x]
&8& p[z] ← y
&9& if y = nil[T]
10&&&& then root[T] ← z
11&&&& else if key[z] & key[y]
12&&&&&&&&&&&& then left[y] ← z
13&&&&&&&&&&&& else right[y] ← z
14& left[z] ← nil[T]
15& right[z] ← nil[T]
16& color[z] ← RED
17& RB-INSERT-FIXUP(T, z)
咱们来具体分析下，此段代码：
RB-INSERT(T, z)，将z插入红黑树T 之内。
为保证红黑性质在插入操作后依然保持，上述代码调用了一个辅助程序RB-INSERT-FIXUP
来对结点进行重新着色，并旋转。
14& left[z] ← nil[T]
15& right[z] ← nil[T]& //保持正确的树结构
第16行，将z着为红色，由于将z着为红色可能会违背某一条红黑树的性质，
所以，在第17行，调用RB-INSERT-FIXUP（T,z）来保持红黑树的性质。
RB-INSERT-FIXUP(T, z)，如下所示：
&1 while color[p[z]] = RED
&2&&&& do if p[z] = left[p[p[z]]]
&3&&&&&&&&&& then y ← right[p[p[z]]]
&4&&&&&&&&&&&&&&& if color[y] = RED
&5&&&&&&&&&&&&&&&&&& then color[p[z]] ← BLACK&&&&&&&&&&&&&&&&&&& ? Case 1
&6&&&&&&&&&&&&&&&&&&&&&&& color[y] ← BLACK&&&&&&&&&&&&&&&&&&&&&& ? Case 1
&7&&&&&&&&&&&&&&&&&&&&&&& color[p[p[z]]] ← RED&&&&&&&&&&&&&&&&&& ? Case 1
&8&&&&&&&&&&&&&&&&&&&&&&& z ← p[p[z]]&&&&&&&&&&&&&&&&&&&&&&&&&&& ? Case 1
&9&&&&&&&&&&&&&&&&&& else if z = right[p[z]]
10&&&&&&&&&&&&&&&&&&&&&&&&&& then z ← p[z]&&&&&&&&&&&&&&&&&&&&&& ? Case 2
11&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LEFT-ROTATE(T, z)&&&&&&&&&&&&& ? Case 2
12&&&&&&&&&&&&&&&&&&&&&&&&&& color[p[z]] ← BLACK&&&&&&&&&&&&&&&& ? Case 3
13&&&&&&&&&&&&&&&&&&&&&&&&&& color[p[p[z]]] ← RED&&&&&&&&&&&&&&& ? Case 3
14&&&&&&&&&&&&&&&&&&&&&&&&&& RIGHT-ROTATE(T, p[p[z]])&&&&&&&&&&& ? Case 3
15&&&&&&&&&& else (same as then clause
&&&&&&&&&&&&&&&&&&&&&&&& with &right& and &left& exchanged)
16 color[root[T]] ← BLACK
ok，参考一网友的言论，用自己的语言，再来具体解剖下上述俩段代码。
为了保证阐述清晰，我再写下红黑树的5个性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
在对红黑树进行插入操作时，我们一般总是插入红色的结点，因为这样可以在插入过程中尽量避免对树的调整。
那么，我们插入一个结点后，可能会使原树的哪些性质改变列?
由于，我们是按照二叉树的方式进行插入，因此元素的搜索性质不会改变。
如果插入的结点是根结点，性质2会被破坏，如果插入结点的父结点是红色，则会破坏性质4。
因此，总而言之，插入一个红色结点只会破坏性质2或性质4。
我们的策略很简单，
其一、把出现违背红黑树性质的结点向上移，如果能移到根结点，那么很容易就能通过直接修改根结点来恢复红黑树的性质。直接通过修改根结点来恢复红黑树应满足的性质。
其二、穷举所有的可能性，之后把能归于同一类方法处理的归为同一类，不能直接处理的化归到下面的几种情况，
&//注：以下情况3、4、5与上述算法导论上的代码RB-INSERT-FIXUP(T, z)，相对应：
情况1：插入的是根结点。
原树是空树，此情况只会违反性质2。
& 对策：直接把此结点涂为黑色。
情况2：插入的结点的父结点是黑色。
此不会违反性质2和性质4，红黑树没有被破坏。
& 对策：什么也不做。
情况3：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。
此时父结点的父结点一定存在，否则插入前就已不是红黑树。
与此同时，又分为父结点是祖父结点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。
在此，我们只考虑父结点为祖父左子的情况。
同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。
& 对策：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。
针对情况3，变化前（图片来源：saturnman）[插入4节点]：
情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
如下图所示，变化前[插入7节点]：
情况5：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子
解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋
如下图所示[插入2节点]
==================
&&&三、II、ok，接下来，咱们最后来了解，红黑树的删除操作：
算法导论一书，给的算法实现：&
RB-DELETE(T, z)&& 单纯删除结点的总操作
&1 if left[z] = nil[T] or right[z] = nil[T]
&2&&& then y ← z
&3&&& else y ← TREE-SUCCESSOR(z)
&4 if left[y] ≠ nil[T]
&5&&& then x ← left[y]
&6&&& else x ← right[y]
&7 p[x] ← p[y]
&8 if p[y] = nil[T]
&9&&& then root[T] ← x
10&&& else if y = left[p[y]]
11&&&&&&&&&&& then left[p[y]] ← x
12&&&&&&&&&&& else right[p[y]] ← x
13 if y 3≠ z
14&&& then key[z] ← key[y]
15&&&&&&&& copy y's satellite data into z
16 if color[y] = BLACK
17&&& then RB-DELETE-FIXUP(T, x)
18 return y
RB-DELETE-FIXUP(T, x)& &恢复与保持红黑性质的工作
&1 while x ≠ root[T] and color[x] = BLACK
&2&&&& do if x = left[p[x]]
&3&&&&&&&&&& then w ← right[p[x]]
&4&&&&&&&&&&&&&&& if color[w] = RED
&5&&&&&&&&&&&&&&&&&& then color[w] ← BLACK&&&&&&&&&&&&&&&&&&&&&&& ?& Case 1
&6&&&&&&&&&&&&&&&&&&&&&&& color[p[x]] ← RED&&&&&&&&&&&&&&&&&&&&&& ?& Case 1
&7&&&&&&&&&&&&&&&&&&&&&&& LEFT-ROTATE(T, p[x])&&&&&&&&&&&&&&&&&&& ?& Case 1
&8&&&&&&&&&&&&&&&&&&&&&&& w ← right[p[x]]&&&&&&&&&&&&&&&&&&&&&&&& ?& Case 1
&9&&&&&&&&&&&&&&& if color[left[w]] = BLACK and color[right[w]] = BLACK
10&&&&&&&&&&&&&&&&&& then color[w] ← RED&&&&&&&&&&&&&&&&&&&&&&&&& ?& Case 2
11&&&&&&&&&&&&&&&&&&&&&&& x p[x]&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& ?& Case 2
12&&&&&&&&&&&&&&&&&& else if color[right[w]] = BLACK
13&&&&&&&&&&&&&&&&&&&&&&&&&& then color[left[w]] ← BLACK&&&&&&&&& ?& Case 3
14&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& color[w] ← RED&&&&&&&&&&&&&&&&& ?& Case 3
15&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& RIGHT-ROTATE(T, w)&&&&&&&&&&&&& ?& Case 3
16&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& w ← right[p[x]]&&&&&&&&&&&&&&&& ?& Case 3
17&&&&&&&&&&&&&&&&&&&&&&&& color[w] ← color[p[x]]&&&&&&&&&&&&&&&& ?& Case 4
18&&&&&&&&&&&&&&&&&&&&&&&& color[p[x]] ← BLACK&&&&&&&&&&&&&&&&&&& ?& Case 4
19&&&&&&&&&&&&&&&&&&&&&&&& color[right[w]] ← BLACK&&&&&&&&&&&&&&& ?& Case 4
20&&&&&&&&&&&&&&&&&&&&&&&& LEFT-ROTATE(T, p[x])&&&&&&&&&&&&&&&&&& ?& Case 4
21&&&&&&&&&&&&&&&&&&&&&&&& x ← root[T]&&&&&&&&&&&&&&&&&&&&&&&&&&& ?& Case 4
22&&&&&&& else (same as then clause with &right& and &left& exchanged)
23 color[x] ← BLACK
为了保证以下的介绍与阐述清晰，我第三次重写下红黑树的5个性质
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
（相信，重述了3次，你应该有深刻记忆了。:D）
&saturnman：
红黑树删除的几种情况：
-------------------------------------------------
博主提醒：
以下所有的操作，是针对红黑树已经删除结点之后，
为了恢复和保持红黑树原有的5点性质，所做的恢复工作。
前面，我已经说了，因为插入、或删除结点后，
可能会违背、或破坏红黑树的原有的性质，
所以为了使插入、或删除结点后的树依然维持为一棵新的红黑树，
那就要做俩方面的工作：
1、部分结点颜色，重新着色
2、调整部分指针的指向，即左旋、右旋。
而下面所有的文字，则是针对红黑树删除结点后，所做的修复红黑树性质的工作。
&二零一一年一月七日更新。
------------------------------------------------------------
(注：以下的情况3、4、5、6，与上述算法导论之代码RB-DELETE-FIXUP(T, x) 恢复与保持
中case1，case2，case3，case4相对应。)
情况1：当前节点是红色
&&& 解法，直接把当前节点染成黑色，结束。
&&& 此时红黑树性质全部恢复。
情况2：当前节点是黑色且是根节点
&&& 解法：什么都不做，结束
情况3：当前节点是黑色，且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
&&& 解法：把父节点染成红色，把兄弟结点染成黑色，之后重新进入算法（我们只讨论当前节点是其父节点左孩子时的情况）。
&&& 然后，针对父节点做一次左旋。此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况。
&&&&&&&&&&&&&&&&&&& &3.变化前：
&&&&&&&&&&&&&&&&&&&&&3.变化后：&
情况4：当前节点是黑色，且兄弟是黑色，且兄弟节点的两个子节点全为黑色。
&&&&& 解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。（此变换后性质5不变）
&&&&&&&&&&&&&&&&&&&&&&&&4.变化前
&&&&&&&&&&&&&&&&&&&&&&& 4.变化后
情况5：当前节点颜色是黑色，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。
&&& 解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，
之后重新进入算法。此是把当前的情况转化为情况6，而性质5得以保持。
&&&&&&&&&&&&& 5.变化前：
&&&&&&&&&&&&&&&&&&5.变化后：
情况6：当前节点颜色是黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。
&&& 解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，
之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。
&&&&&&&&&&&&&&&&&&&&6.变化前：
&&&&&&&&&&&&& 6.变化后：
限于篇幅，不再过多赘述。更多，可参考算法导论或下文我写的第二篇文章。
July、二零一零年十二月二十九日初稿。三十日凌晨修订。行文3个小时以上。
----------------
今下午画红黑树画了好几个钟头，贴俩张图：
& 红黑树插入的3种情况：
& 红黑树删除的4种情况：
ok，只贴俩张，更多，参考我写的关于红黑树的第二篇文章：
红黑树算法的层层剖析与逐步实现[推荐]
http://blog.csdn.net/v_JULY_v/archive//6109153.aspx
这篇文章针对算法实现源码分十层，层层、逐层剖析，相信，更清晰易懂。
//尤其文末针对红黑树的删除情况，层次清晰。
&&&&&&&&&&&& July、二零一零年十二月三十一日、最后更新。
更多相关文章
红黑树是一棵二叉搜索树,它在每个结点上增加一个存储位来表示结点的颜色(红或黑).关于二叉搜索树的内容,可参见本系列之前一篇博客: &算法导论&学习笔记(3)--二叉搜索树
红黑树的每个结点都有如下五个属性:color.key.left.right.pa ...
#include &stdlib.h& #include &stdio.h& typedef int EleT typedef enum Color //颜色属性:红.黑 { RED = 0, BLACK = 1 } C typedef struct Nod ...
红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其 他路径长出俩倍,因而是接近平衡的. 红黑树,能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn). 一 ...
这是c++实现的红黑树,主要思路跟前一篇c语言的一样,主要是设计方式的不同,通过这两篇博客也能比较一下面向过程和面向对象之间的区别与联系. 本例单独5个函数: Node.h #ifndef NODE_H_ #define NODE_H_ typedef int EleT //定义红黑树结点颜 ...
1.stl中的set底层用的什么数据结构? 2.红黑树的数据结构怎么定义的? 3.红黑树有哪些性质? 4.红黑树的各种操作的时间复杂度是多少? 5.红黑树相比于BST和AVL树有什么优点? 6.红黑树相对于哈希表,在选择使用的时候有什么依据? 7.如何扩展红黑树来获得比某个结点小的元素有多少个? 8 ...
我们先来说输出: 输出重要部分是: - 那么问题来了... 12.234567大家伙估计都明白是数据,那么5.2f是什么意思呢? .2f是截取后两位,截取3位就是.3f,以此类推 12.234567: 小数点的位数为 ...
MyEclipse中创建新的Maven项目(webapp目录结构)过程如下: 1. New ...
1.类目 类目就是为已存在的类添加新的方法.但是不能添加实例变量.比如系统的类,我们看不到他的.m文件,所以没有办法用直接添加方法的方式去实现. @interface NSMutableArray (Sort) // ...
C# 如果要实现自定义属性必须要需要实现接口ICustomTypeDescriptor
今天,哦是昨天了,一天心有点不静,工作状态不佳,今天一定要调整好! 昨天看到一篇日志,讲到开发日志的,这几天正好也在想这个问题,最近开发中,遇到了很多问题,也做了不少以前没做过的功能模块,回想下确实又有些模糊了,加上 ...
友情链接：
管理员邮箱：info@