红黑树的插入与删除 详细整理资料.docx
《红黑树的插入与删除 详细整理资料.docx》由会员分享，可在线阅读，更多相关《红黑树的插入与删除 详细整理资料.docx（27页珍藏版）》请在冰点文库上搜索。
红黑树的插入与删除详细整理资料
红黑树的插入、删除及旋转原则
Category:
Uncategorized—wuxicn@12:
29AM
红黑树（Red-BlackTree）的插入和删除操作很繁琐，一不小心就容易弄错，不能靠强制记忆。
因此，今天总结一下红黑树插入和删除操作的推导原则，包括旋转的推导原则。
本文所有内容来自三个网页
1.
2.http:
//icoder.me/2009/08/25/insert-delete-in-red-black-tree/
3.
如果大家能打开上面的链接，就不用再看了，我整理得不好。
。
先是比较简单的插入操作的推导原则：
1.红黑树的插入和普通搜索二叉树（BinarySearchTree）的插入一样，只是在插入完以后，将新插入的节点标记为红色，然后从该节点开始，向上进行调整颜色。
2.向上调整颜色进行旋转时，旋转的原则是尽量用1次或者最多2次旋转完成，并且旋转操作不能影响该层以下层次的节点，只能影响其父节点，然后将其父节点（或者叔节点、兄弟节点）作为新的要调整颜色节点，继续向上递推调整。
3.调整完后注意检查根的颜色是否还是黑色。
删除操作的推导原则：
（比较麻烦！
）
1.删除节点z时，先找到z的中根后继节点y，然后将y的数据复制给z（不包括颜色），然后将y删除。
这样，删除y的时候，y最多只有一个孩子节点x，将x取代y即可，然后如果y的颜色是黑色，才需要调整颜色。
若要调整颜色，从x处开始向上递推的调整颜色。
2.从x处开始向上调整颜色时也应注意不要影响该层次以下的节点，只能影响x同层或者更高层的节点。
调整完后x的父节点（或者叔节点、兄弟节点）作为新的待调节点（新的x），如果newx颜色为红色时，则不用调了，直接结束。
3.调整是应注意通过标记各层高度（黑高度）来进行推导。
4.结束后看x是否是红色，如果是，改成黑色。
Remarks:
1.里面提到的高度是指黑节点个数。
2.层次也是关于黑节点来说的。
红黑树原理详解上：
前言：
之所以要写这篇文章，第一个目的是为了各位朋友在查看我写的源代码之前有一个可以理解理论的文章因为红黑树还是有点难的，
如果不想搞懂理论，而直接看代码，那绝对是云里雾里，不知所云。
第二个目的是我觉得网上虽然后不少我文章也在讲，但是我就是理解
不上有点困难，在我参考了很多文章之后，认真阅读才慢慢摸透了其中的原理，所以我想用自己的方式来表达，希望有助于各位的朋友理解。
你可以在这里获得配套源代码
红黑树由来：
他是在1972年由RudolfBayer发明的，他称之为“对称二叉B树”，它现代的名字是LeoJ.Guibas和RobertSedgewick于1978
年写的一篇论文中获得的。
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的:
它可以在O（logn）时间内做查找，
插入和删除，这里的n是树中元素的数目。
红黑树性质：
1.每个结点或红或黑。
2.根结点为黑色。
3.每个叶结点（实际上就是NULL指针）都是黑色的。
4.如果一个结点是红色的,那么它的周边3个节点都是黑色的。
5.对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。
讨论的前提：
1，我们只讨论往树的左边和从树的左边删除的情况，与之对称的情况一样。
2，假设我们要删除一个元素的方法都是采取删除后继节点，而非前驱节点。
3，NL或全黑表示黑空节点，也可以不用画出。
4，“=>”这个符号我们用来表示“变成”的意思。
一．插入
当红黑树中没有节点的时候，新节点直接涂黑就可以了。
当树中已有节点，我们就将新节点涂红，并且底下挂两个黑空节点。
1.1新节点的父亲为黑色
这种情况最简单，只接插入将新节点可以了，不会出现红色警戒。
1.2新节点的父亲为红色
这种情况出现红色警戒，并且通过红色的父亲，我们可以推出一定有一个黑色的父，并且父亲不可能为树根（树根必须为黑）。
这种情况需要修复。
1.2.1新节点的叔叔是红色。
（红叔）
图1.2.1-1
图1.2.1-2
注解：
在这种情况下，我们可以通过这样的方式来修复红黑树的性质。
因为遇到红色警戒所以我们首先可以想到的就是将父亲变成黑色，但这样祖父的左子树的黑高就增加了，为了达到祖父的平衡，我们红叔变成黑色，这样祖父就平衡了。
但是整个祖父这颗树的高度增高了，所以再此将祖父的颜色变成红色来保持祖父这颗树的高度不变。
因为祖父变成了红色，因此往上遍历。
方法：
父=>黑；叔=>黑；祖=>红；往上遍历；
1.2.2新节点的叔叔是黑色（黑叔）
图1.2.2-1
图1.2.2-2
注解：
首先可以说明的是，这种情况下我们都可以通过改变颜色和旋转的方式到达平衡，并且不再出现红色警戒，因为无需往上遍历。
图1.2.2-1：
首先我们将红父变成黑色，祖父变成红色，然后对祖父进行右旋转。
这样我们可以看到，整颗树的黑高不变，并且这颗树的左右子树也达到平衡。
新的树根为黑色。
因此无需往上遍历。
方法：
图1.2.2-1 父=>黑；祖=>红；祖父右旋转；
图1.2.2-2 新=>黑；祖=>红；父左旋转；祖右旋转；
插入我们就算做完了，与之对称的右边插入的情况完全一样，请自己下来分析；
一．删除
删除是比较经典但也是最困难的一件事了，所以我们必须一步一步地理解。
为了中途思想不混乱，请始终记住一点，下面我们删除的节点都已经表示的是实际要删除的后继节点了。
因此可以得出一下结论。
首先，可以肯定的是我们要删除的节点要么是红色，要么是黑色。
其次，既然我们要删除的结点是后继节点，那么要删除的节点的左子树一定为空。
所以当删除的节点为黑色时只剩下两种情况。
最后，如果删除的节点为红色，那么它必为叶子节点。
（自己好好想象为什么）。
请在看下面的内容前先牢记上面的结论，这样更加方便让你理解下面的知识。
a：
当删除的节点为黑色时
删黑a 删黑b
b：
当删除的节点为红色时
上面的几附图都是很简单的。
因为你可以将空节点
去掉不看。
所就形成了要删除的节点要么有一个右孩子，要么为叶子节点。
下面我们就开始真正的删除操作了。
2.1删除红色节点
注解：
这种情况是最简单的，因为根据上面的结论我们可以推出子节点 一定为空，也就是说删除的红色节点为叶子节点。
只需将这个旧节点的右孩子付给父亲的左孩子就可以了，高度不变。
方法：
略
2.2删除黑色节点
遇到黑色节点情况就将变得复杂起来，因此我们一定要慢慢来，仔细分析。
2.2.1当删除的节点有一个红色子孩子
注解：
这种情况其实就是上面我们分析的三种情况之一，如图"删黑b"。
这种情况是非常简单的，只需将旧节点的右孩子取代旧节点，并将子孩子的颜色变为黑色，树平衡；
方法：
子取代旧；子=>黑；
2.2.2当删除的节点无左右孩子
这种情况其实就是上面我们分析的三种情况之一，如图"删黑a"。
我们推出子节点
一定为空，请务必记住这点，不然在后面你将很容易被混淆，父亲的颜色我们标记为绿色，是表示，父亲的颜色可为红或黑。
黄色的子节点
其实就是一个黑空节点，这样方便后面分析。
a：
红兄
注解：
当我们删除的节点拥有一个红色的兄弟时，这种情况还相对比较简单，因为兄弟为黑色，我们可以推出父亲一定为黑色。
因为父节点的左树高度减一，所以我们可以通过左旋转父节点，来将节点1旋转到左边来恢复左边的高度。
然后将父变成红，兄变成黑。
这样整颗树的高度不变，父节点也平衡记住子节点
为空所以可以删除看，这样便于理解。
其实我们也可以推出1，2为空，但这里没有必要。
方法：
父=>红；兄=>黑；左旋转父节点；
b：
黑兄
遇到黑兄就又麻烦了，我们又必须引入要删除的节点的侄子了。
所以我们这里再次细分为b1:
黑兄双黑侄b2:
黑兄左黑侄右红侄b3:
黑兄右黑侄左红侄。
可能你会问b4呢，双红侄的情况呢？
其实双红侄的情况同属于b2,b3的情况，所以可以默认用b2,b3其中一种情况来处理就可以了。
现在我们开始了
b1黑兄双黑侄
注解：
我们首先可以肯定的是父节点的左子树高度减一了，所以我们必须想方设法来弥补这个缺陷。
如果我们把父节点的右子树高度也减一（兄变成红色）那么父节点这颗树就可以保持平衡了，但整颗树的高度减一，所以我们可以判断，如果父亲是红色，那么我们可以通过把父亲变成黑色来弥补这一缺陷。
但如果父亲是黑色呢，既然遇到到黑色了我们就只好往上遍历了。
方法：
兄=>红；子=黑； 红父=>黑;
往上遍历（黑父）;
补充：
其实子节点就是空节点，没有必要变。
就算遍历上去，父节点也为黑
b2黑兄左黑侄右红侄
注解：
绿色表示，颜色不影响修复的方式。
依然我们可以肯定父节点的左子树高度减一，所以我们可以通过将父节点旋转下来并且变为黑色来弥补，但由于兄弟被旋转上去了，又导致右子树高度减一，但我们这有一个红侄，所以可以通过红侄变成黑色来弥补。
父亲所在位置的颜色不变；（
子为空）
方法：
兄=>父色；父=>黑；侄=>黑；（子=>黑）；左旋转父节点；
b3黑兄左红侄右黑侄
注解：
绿色表示，颜色不影响修复的方式。
依然我们可以肯定父节点的左子树高度减一,同样我们通过父节点左旋转到左子树来弥补这一缺陷。
但如果直接旋转的话，我们可以推出左右子树将不平衡（黑父），或者两个红色节点相遇（红父）；这样将会更加的复杂，甚至不可行。
因此，我们考虑首先将兄弟所在子树右旋转，然后再左旋转父子树。
这样我们就可以得到旋转后的树。
然后通过修改颜色来使其达到平衡，且高度不变。
方法：
侄=>父色；父=>黑;右旋转兄；左旋转父；
总结：
如果我们通过上面的情况画出所有的分支图，我们可以得出如下结论
插入操作：
解决的是红-红问题
删除操作：
解决的是黑-黑问题
即你可以从分支图中看出，需要往上遍历的情况为红红（插入）；或者为黑黑黑（删除）的情况，，如果你认真分析并总结所有的情况后，并坚持下来，红黑树也就没有想象中的那么恐怖了，并且很美妙；
∙版权声明：
转载时请以超链接形式标明文章原始出处和作者信息及本声明
红黑树删除节点函数Rb_tree_rebalance_for_erase详析（注，以下内容我也没找到相关的图片，大家只有自己理解了，抱歉）
在编程时，会碰上多少让你发疯想死的代码？
这样的程序代码的存在妈的简直对人的信心就是种极度挑战，而且搞懂这些代码，不会让你有任何成就感，而只会更加恨能写得出这些代码的二逼。
仅仅一段代码一个函数，搞了几天才完全搞通，别说成就感了，净剩下拿刀捅人的冲动了。
在读SGI/STL版本的STL实作的源代码时，遇上了一个罕见复杂抽象的内部全局函数_Rb_tree_rebalance_for_erase，这个函数是我所见过的为数不多的可以用“恐怖”去形容的，其恐怖到什么程度：
在侯捷的《STL源代码剖析》一书中，对于红黑树的操作这节内容中，他只讲到插入节点的操作，居然对删除节点的操作只字不提，不知道是不是故意的。
究其原因，不知道是不是跟这个诡异复杂的函数有些联系。
这个函数是在红黑树删除节点之前做的准备工作，当然，删除过程中的绝大部分任务就是由这个函数完成的。
从这个函数中出来之后，树还是平衡的，而实际要删除的节点已经和红黑树分离开来了，基本上剩下的只要在内存管理器中消除节点就够了。
这万恶的函数如下：
inline_Rb_tree_node_base*
_Rb_tree_rebalance_for_erase（_Rb_tree_node_base*__z,
_Rb_tree_node_base*&__root,
_Rb_tree_node_base*&__leftmost,
_Rb_tree_node_base*&__rightmost）
看该函数的原型，该函数的目的是将z节点从整个红黑树中去除（并非从内存管理器中最终删除，最终从内存管理配置器中删除该节点的任务不是由此函数完成的）并使剩下的树继续组成一个平衡的红黑树；函数最终返回指向被去除节点的迭代器。
但是这函数有个大前提：
函数执行前的红黑树也必须是平衡的，抛开这个前提，别的无从谈起。
该函数完成了两个主要工作：
1． 将z节点从整个树中去除并将其位置保存；
2． 调整剩余红黑树节点使其重新达到平衡。
我们一步一步来看。
1. 将z节点从整个树中去除
第一步，我们不考虑红黑树平衡性，仅是单纯从树中去除z节点。
这需要在函数中定义一个局部迭代器y并最终将z保存到y中，函数最后只需返回y即可。
删除二叉搜索树中任意节点的原则其实基本相同，就是在整个儿二叉树中寻找到与欲删除节点键值最相近的节点（也即某叶节点），用该节点去替换掉欲删节点即可，如下图1所示：
图1
图1中，z（d）为删除节点，我们根据二叉搜索树的建立原则对其全部结点顺序进行排序，则必定可以找到如下图2所示的顺序队列：
图2
这里的n或q节点有可能为空，这并不影响问题的处理方法。
在全树中，我们可以用m或p去填充z（d）所占的位置，将m的左子树n接到原先m的位置上，然后将d从树中去掉；或者我们用p去填充z（d）所占据的位置，将p的右子树q接到原先p的位置上，然后将d从树中去掉。
这两种方法是等效的，在本函数大多数情况下中所采取的是后一种方法，也即用p去填充z（d）的方法，所以我们只讨论这种方法。
只有在一种情况下我们不得不进行前一种方法，那就是在d不存在右孩子的情况下，我们只能用前面的m填充z（d）的位置来进行处理（这种情况我们到后面再讨论）。
在进行上述操作之后整个树变成下图3所示的情况：
图3
这时整颗二叉搜索树的特性也没有破坏，并仍然保持顺序队列，如图4：
图4
我们来看具体这部分的代码片段：
_Rb_tree_node_base*__y=__z; //局部变量定义指针/迭代器y指向待删除节点z
_Rb_tree_node_base*__x=0;
_Rb_tree_node_base*__x_parent=0;
首先，我们来确定y在整颗红黑树中的位置，排除两个特殊情况，即y位于最左节点和y位于最右节点处（即y节点分别为树中键值最小和键值最大节点两种情况），这两种情况下，我们可以对y直接进行去除，不需要进行查询替换手续，但是，这两种情况下依然要对x进行定位，以便在后面调整红黑树平衡时使用。
始终保持一个原则：
x永远指向替换的节点的子节点。
if（__y->_M_left==0） //__zhasatmostonenon-nullchild.y==z.
__x=__y->_M_right; //__xmightbenull.
else
if（__y->_M_right==0） //__zhasexactlyonenon-nullchild.y==z.
__x=__y->_M_left; //__xisnotnull.注意这就是我们前面所说的y（或z）不存在右孩子的情况，这种情况下x不同的取了y左孩子的值。
else{ //__zhastwonon-nullchildren. Set__yto
__y=__y->_M_right; // __z'ssuccessor. __xmightbenull.
while（__y->_M_left!
=0）
__y=__y->_M_left;
__x=__y->_M_right;
}
在上一个else条件中，即是最普通的情况，这种情况下y有两个子节点，处于顺序队列中间，这种情况下我们需要向z的右子树里去寻找键值最接近z的节点（即前面讨论的p节点），并将y指向p，这里程序使用一个while循环进行查找，先令y指向z的右子树的跟，然后一路向左行进，直到找到最左的叶节点，此时就是p所在：
__y=__y->_M_right; // __z'ssuccessor. __xmightbenull.
while（__y->_M_left!
=0）
__y=__y->_M_left;
找到p之后y指向p，紧跟着就是将x指向p的右子树（因为到底了，y已经没有左子树了）。
这时x有可能为空。
下面开始填充z节点的过程，STL注释解释的比较到位，他说“在z的位置对y进行重新连接”，想想的确如此，在物理位置上没有改变，只是将y与z及其相邻的若干节点进行重新连接而已。
这里分两种情况来考虑，一种是一般情况，另一种就是上面提到的，z是红黑树里最右边的节点（键值最大），此种情况下可能需要改变head节点指向的leftmost以及rightmost指针的指向（还记得函数原型中最后两个参数是干什么用的么？
就在这里使用）。
我们首先看到第一种一般情况，就是z不是树里最右边的节点。
if（__y!
=__z）{ //relinkyinplaceofz. yisz'ssuccessor
此种情况下，开始改变y与z原先的连接，使y代替原先z的位置：
__z->_M_left->_M_parent=__y; //首先改变与z相连的左孩子，节点其父节点指针的链接，使其指向y，
__y->_M_left=__z->_M_left;//同样将y自身的左孩子与z的左孩子相连
if（__y!
=__z->_M_right）{//y不是z的右孩子
__x_parent=__y->_M_parent;//此时引入__x_parent来，__x_parent的意义就是在调整y结束之后始终指在x的父节点位置。
if（__x）__x->_M_parent=__y->_M_parent;//如果x不为空，x中的父节点指针始终等于__x_parent
__y->_M_parent->_M_left=__x; //__ymustbeachildof_M_left，指针x指向的节点在调整结束后取代y之前的位置，始终是__x_parent的左孩子，见图5：
图5
现在调整y的右孩子指针，使其指向z的右孩子：
__y->_M_right=__z->_M_right;
__z->_M_right->_M_parent=__y;//调整z右孩子的父亲指针使其指向y，至此y的重新连接完毕。
}
else//如果y是z的右孩子，属于稍微特殊的一种情况，
__x_parent=__y; //这种情况下y自身就是x的父亲即__x_parent
这里还有种特殊情况，即欲删除的z本身就是整个红黑树的根结点，如下：
if（__root==__z）
__root=__y;//这种情况下，直接令根结点等于y本身即可
elseif（__z->_M_parent->_M_left==__z）//如果z本身是左孩子，则
__z->_M_parent->_M_left=__y;//令z的父亲的左孩子指针指向y
else
__z->_M_parent->_M_right=__y;//令z的父亲的右孩子指针指向y到，这里已经离开y是否z的右孩子这个判断条件了：
__y->_M_parent=__z->_M_parent;//修改y所指向的父亲指针，时期重新指向z指向的父亲
__STD:
:
swap（__y->_M_color,__z->_M_color）;//对换y和z各自指向的节点本身的颜色值，以备下面红黑树平衡时使用，注意这里对换之后，并没有破坏原先树的颜色规则，也即：
这行保证了删除之前z是什么颜色的节点，删除之后在树中相同位置的仍然是这种颜色。
注意，在经过上述行为之后，原先树中z指向的节点是否发生了改变了吗我们可以自己查看，除了颜色值之外，z指向节点的内容并没有发生改变也就是说，只是y所指向的那个节点和z指向节点的相邻周围节点发生了改变，z指向的节点得到了充分的保护。
__y=__z;//__ynowpointstonodetobeactuallydeleted
}
y重新指向了z指向的节点，这一步是为了下面红黑树平衡调整时使用的，而且也正是最终函数返回的实际上被删除的指针！
要使用到的关键的一个值就是y指向的节点的颜色值这时，因为上面的对换语句，y指向的节点的颜色值，其实就是之前未变化之前的节点的颜色值，请注意这里，这里很重要，马上就要用到这个颜色值以图来解释就是下图6所示：
图6（注：
我们其实只是为比较p和d的颜色值的对换情况而特别举此图中的例子，这种情况我们到后面还要说到。
）
我们再来看第二种情况，就是z是红黑树最右边的节点（即y==z）：
else{ //__y==__z
__x_parent
升级会员 