《数据结构与算法分析》详细对⽐⾃顶向下与⾃底向上红⿊树
——C实现⾃顶向下插⼊与删除
前⾔：
这本书学到了最后⼀章终于出现了红⿊树，它不愧为最难的⼏个数据结构之⼀，从看书到实现整个红⿊树⼀共⽤时2天，第⼀天看书加上实现⾃顶向下的插⼊算法⼤概⽤了6个⼩时。
July 的博客⾥，还有各个知名博主博客⾥的红⿊树基本是使⽤⾃底向上的⽅式来实现删除的，《数据结构与算法分析》这本书上建议使⽤⾃顶向下删除，但是对于如何删除，说的特别含糊，基本上不可以参考，于是在⽹络上寻是否有详细的讲解，最终，到⼀篇英⽂⽂献，⽐较详细的介绍了如何实现《数据结构与算法分析》12.2节中的⾃顶向下删除的⽅法。
此⽂中讲述了各个情况如何旋转红⿊树，但是并没有⼀个流程图，也没有将清楚如何删除，不过⾃⼰花了⼤约10个⼩时，把整个思路理清楚了，然后完成了⾃顶向下删除的流程图与伪代码，最终实现了⾃顶向下的删除过程。
我的github：
我实现的代码全部贴在我的github中，欢迎⼤家去参观。
介绍：
红⿊树：
⼀、简介：
红⿊树（Red Black Tree）是⼀种⾃平衡⼆叉查树，是在计算机科学中⽤到的⼀种数据结构，典型的⽤途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡⼆叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J.Guibas 和Robert Sedgewick 修改为如今的“红⿊树”。
红⿊树和AVL树类似，都是在进⾏插⼊和删除操作时通过特定操作保持⼆叉查树的平衡，从⽽获得较⾼的查性能。
它虽然是复杂的，但它的最坏情况运⾏时间也是⾮常良好的，并且在实践中是⾼效的：它可以在O(log n)时间内做查，插⼊和删除，这⾥的n 是树中元素的数⽬。
⼆、红⿊树的性质：
性质1. 节点是红⾊或⿊⾊。
性质2. 根节点是⿊⾊。
性质3 每个叶节点（NIL节点，空节点）是⿊⾊的。
性质4 每个红⾊节点的两个⼦节点都是⿊⾊。(从每个叶⼦到根的所有路径上不能有两个连续的红⾊节点)
性质5. 从任⼀节点到其每个叶⼦的所有路径都包含相同数⽬的⿊⾊节点。
如上是⼀颗红⿊树，在实现红⿊树时，我们有⼀个⼩技巧，能够巧妙的简化⾃顶向下的插⼊与删除操作。
三、平衡树旋转：
平衡树的旋转分成单旋转和双旋转，单旋转分成左旋转和右旋转。
双旋转是由两个单旋转构成的。
旋转的详细内容不是这⾥要叙述的，如果需要更加详细的介绍可以参考其他博客。
红⿊树的旋转同样是使⽤以上两种旋转来达到其性质要求，主要是保证性质4和5在插⼊和删除节点时能继续成⽴。
四、实现⼩技巧：
在实现红⿊树时，我们建⽴⼀个NullNode来代表NULL，如果⼀个节点的孩⼦指向了NullNode，那么就代表没有孩⼦。NullNode的颜⾊设置为⿊⾊，在判断孩⼦节点颜⾊的时候，省去了对NULL的特殊处理。NULL的元素值设置为Infinity。
除了NullNode之外，根节点T不是真正的根节点，T中元素设置为NegInfinity，它真正的根在它的右⼦树上，即T->right才是真正的根，T->left指向NullNode。这样做的好处最开始我⼀点都不明⽩，直到实现⾃顶向下的删除时，才发现这样设计的妙处。
红⿊树的操作：
基础操作
⼀、打印：
打印红⿊树就需要从真正的根节点开始了，需要⼀个驱动程序来驱动真正的打印过程：
inline void PrintTree(RedBlackTree T)
{DoPrint(T->right, 0);}
/*打印红⿊树*/
void DoPrint(RedBlackTree T, int depth)
{
if(T != NullNode)
{
DoPrint(T->left, depth +1);
for(int i =0; i<depth; i++)
printf("    ");
printf("%d,%s\n", T->Elememt, T->color == Red? "Red":"Black");
DoPrint(T->right, depth+1);
}
}
在这⾥是打印到终端⾥，打印出红⾊和⿊⾊，紧跟着权值。下图是⼀张例⼦图，插⼊的点与《数据结构与算法分析》给出的相同，图的上⽅代表左孩⼦，下⽅代表右孩⼦。
⼆、搜索节点：
搜索节点过程中，如果遇到了要的节点，就返回该节点，如果没有到，就返回最后停留的节点，⽽不返回NullNode，这样做的好处是在删除节点时，⽅便到⼦树的最⼩或者最⼤节点。
RedBlackTree find(ElementType item, RedBlackTree T)
{
RedBlackTree Parent;
while(T != NullNode && T->Elememt != item)
{
Parent = T;
if(item <T->Elememt)
T =T->left;
else
T =T->right;
}
if(T == NullNode)
return Parent;
else
return T;二叉树的基本性质
}
插⼊节点：
插⼊节点是第⼀个⿇烦的地⽅，在这⾥只有把插⼊的节点设置为红⾊，才不会影响到树的性质5，但是如果插⼊节点的⽗亲节点是红⾊，那么就⿇烦了，成以下⼏个⽅式讨论：
情况1：插⼊的是根结点。
原树是空树，此情况只会违反性质2。
对策：直接把此结点涂为⿊⾊。
情况2：插⼊的结点的⽗结点是⿊⾊。
此不会违反性质2和性质4，红⿊树没有被破坏。
对策：什么也不做。
⿇烦的情况：
以下两种情况只考虑插⼊的⽗亲节点P是祖⽗节点G的左⼦树，另⼀种镜像的情况可同理推出。
这⾥设N为插⼊的节点，即考虑的当前节点，P为N的⽗亲节点，U为N的兄弟节点，即此时P的右⼦树。G为P的⽗亲节点，也就是N的祖⽗。
情况3：N为红，P为红，U为⿊，P为G的左孩⼦，N为P的左孩⼦
操作：如图P、G变⾊，P、G变换即G右旋（镜像情况左旋），结束。
解析：要知道经过P、G变换（旋转），变换后P的位置就是最初G的位置，所以红P变为⿊，⽽⿊G变为红都是为了不违反性质5，⽽维持到达叶节点所包含的⿊节点的数⽬不变！
情况4：N为红，P为红，U为⿊，P为G的左孩⼦，N为P的右孩⼦（镜像：P为G的右孩⼦，N为P的左孩⼦；反正两⽅向相反）。
操作：需要进⾏两次变换（旋转），图中只显⽰了⼀次变换-----⾸先P、N变换，颜⾊不变；然后就变成了情形3的情况，按照情况3操作，即结束。
解析：由于P、N都为红，经变换，不违反性质5；然后就变成3的情形，此时G与G现在的左孩⼦变⾊，并变换，结束。
最⿇烦的情况：
以上两种⿇烦的情况只需要完成变换就可以了，这个第五种情况需要递归的进⾏，这也是⾃底向上插⼊时，向上⾛的⽬的。
情况5：N为红，P为红，（祖节点⼀定存在，且为⿊，下边同理）U也为红，这⾥不论P是G的左孩⼦，还是右孩⼦；不论N是P的左孩⼦，还是右孩⼦。
操作：如图把P、U改为⿊⾊，G改为红⾊，未结束。然后将N指向G，P指向G的⽗亲节点，U指向N的兄弟，G也顺势向上移动，然后重新开始执⾏插⼊算法。
解析：N、P都为红，违反性质4；若把P改为⿊，符合性质4，显然左边少了⼀个⿊节点，违反性质5；所以我们把G，U都改为相反⾊，这样⼀来通过G的路径的⿊节点数⽬没变，即符合4、5。此时G变红了，若G的⽗节点⼜是红的就有违反了4。所以如果需要把G当做插⼊节点，重新判断符合以上5种情况的哪⼀种，然后再处理。
所以经过上边操作后未结束，把G看做⼀个插⼊的红节点继续向上检索----属于哪种情况，按那种情况操作~遇上情况2就结束，或者达到根结点（此时根结点为红⾊，根据红⿊树性质，改成⿊⾊，完成插⼊）。
⾃底向上插⼊的缺点：
以上5种情况就概括了所有的插⼊时遇到的情况。需要⾃底向上处理的情况也就是情况5了。要实现情况5，那么就需要在红⿊树结构体⾥加上⽗亲指针，或者使⽤栈的⽅式来解决递归向上。我参看july的博客，发现基本上都是增加⼀个⽗亲节点来解决这个问题。
1. 这样就就使得结构体变⼤了，这样的情况在⾃底向上实现AVL树时也出现了（我先⾃底向上实现了AVL树，觉得太繁琐，⼜⾃顶向下实现了⼀遍）。
2. 加上⽗亲节点之后，编程变得⾮常的⿇烦，特别是旋转操作时，需要⾮常⼩⼼。（在编写⾃底向上的AVL树时就吃过亏）
⾃顶向下插⼊的改进：
使⽤⾃顶向下，改进的就是第5种情况，没有了第5种情况，3和4旋转之后，新的⽗亲节点都是⿊⾊，不会遇上违反性质4的情况，即旋转之后红⿊树就完成了插⼊。
1. ⽆需添加⽗亲指针
2. 编码简单
⾃顶向下的实现⽅法：
现在既然已经知道，要避免递归往上判断，就需要避免情况5出现，要避免情况5出现，就只需要⼀个办法：
让兄弟节点U永远是⿊⾊。
插⼊步骤：
步骤1：. 从根节点往下，记录⽗亲节点P，祖⽗节点GP，祖祖⽗节点GGP，当前节点X。
步骤2.：如果X有两个红⾊的孩⼦，那么就使两个孩⼦变成⿊⾊，X变成红⾊。这个过程可能使得X与P都是红⾊。如果不满⾜这个条件，就跳到步骤4。
步骤3.：如果出现了X与P都是红⾊，那么此时X的兄弟节点U必定是⿊⾊，因为从上往下的过程，我们已经确定了U肯定是⿊⾊的。那么这就回到了上⾯所描述的插⼊中的情况3/4。直接使⽤单旋转或者双旋转就可以解决。解决之后，让X指向旋转之后的根节点，此时X为⿊⾊，两个孩⼦为红⾊，原本的X是指向这两个红⾊孩⼦中的其中⼀个的，我们在这⾥回退，⽬的是让GP,GGP随着X的下降，回到正常的值（此时不判定两个孩⼦是否都为红⾊，刚刚做的事情就是让两个孩⼦变成红⾊，根节点变成⿊⾊，）。
步骤4： 完成过程2(3)之后，继续往下前进，重复过程2,4，直到到达key的节点，或者达到NULL，此时X为NULL。
步骤5：如果到达了key，那么key已经存在，不能再插⼊，直接返回即可。如果到达NULL，那么X指向插⼊新的节点，并且设X为红⾊，并且判断此时的P是否是红⾊，如果是红⾊，那么兄弟U必然是⿊⾊，那么再进⾏⼀次步骤3，就完成了插⼊。
实现过程中需要保存GGP节点的原因是，G也会参与到旋转中，那么旋转之后，GGP需要指向新的旋转之后的根。
⾃顶向下插⼊编码：
循环往下前进，由于T中不是真正的根，且T中保存最⼩的值，所以X可以⾃动指向根，并使得P指向合适的值。在这⾥，GGP, GP, P, X, BRO都是全局变量，所以我感觉红⿊树更合适使⽤C++的类来实现，这样可以把这些元素保存为类的成员，避免了多线程处理的不安全问题。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。