《数据结构》 (java版) 课件 7-3红黑树

红黑树（red－blacktree）的定义红黑树是一棵平衡二叉搜索树，它的深度略高于AVL树，但可以采用自顶向下(或自底向上)的实现方法，代码相对简单，效率高。内部结点外部结点(虚拟结点)655070806062510红黑树（red－blacktree）的定义为了保证树的平衡，红黑树使用了以下的规则：RB1:根结点和外部结点是黑颜色；RB2:从根结点到任一外部结点的路径上，不能有两个连续的红色结点；RB3:从根结点到任一外部结点的路径上，黑色结点个数相同；红黑树（red－blacktree）的性质定理1:从根结点到外部结点的最短路径Q和最长路径P存在以下关系：length(P)≦2length(Q)证明：由规则2得知，Q全部由黑色结点组成，设有m个黑色结点（不包括外部结点），则length(Q)=m。由规则3得知，P中黑色结点数也为m。由条件2得知，红色结点只能出现在2个黑色结点之间，因此，红色结点数为m。因此，length(P)=2m。红黑树（red－blacktree）的性质令h表示树的深度，r表示从根结点到外部结点路径中黑色结点的个数，n表示树中结点个数（不包括外部结点）由完全二叉树的性质，n≥2r-1式2根据定理1,h≦2r式1由式2整理得r≤log2(n+1)式3式1和式3得h≦2log2(n+1)，所以红黑树的常用操作的时间复杂度为O(logn)

AVL树的深度近似为1.44log2(n+2)红黑树（red－blacktree）的性质红黑树可以像AVL树那样采用自底向上的方法实现：首先采用普通的二叉搜索树的put、remove操作，然后再进行平衡。在平衡过程中，有可能对从插入结点(删除结点)到根结点路径上的所有结点都要平衡，而且，调整的方向是从插入结点到根结点，即从下往上逐一平衡。红黑树的优势是采用自顶向下的方法实现：例如put操作首先要从根结点往下找到插入位置，在找插入位置的过程中就根据情况进行平衡，当找到插入位置时，只插入新结点即可，而不需要再平衡。自底向上－put1、基本上同二叉搜索树的put，新插入的结点x一定是叶子结点。3、如果结点x的父结点的颜色是黑色，则完成。否则，违反规则BR2，造成出现2个连续的红色结点，需要做调整。2、红黑树的规则3要求新插入的结点x必须是红色（除非插入前是空树）红色的表示1棵根结点为红色的红黑树。黑色的表示1棵根结点为黑色的红黑树。?代表1棵根结点颜色可红可黑的红黑树下图中用u表示需要调整的结点，pu表示它的父结点。因为pu是红色的，并且红黑树的根结点是黑色的，所以，u的祖父结点gu一定存在。根据u、pu、gu的左右关系，有4种形态，再结合guR的颜色，有8种情况需要讨论。upuguuLuRpuRguR?upuguuLuRpuLguR?upuguuLuRpuLguL?upuguuLuRpuRguL?自底向上－putupuguuLuRpuRguRupuguuLuRpuRguR分析：1、任何从根到以uL、uR、puR、guR为根的子树中的外部结点的路径中黑色结点的数目在变换前后没有发生变化。2、以gu为根的子树内没有两个相邻的红色结点。3、但是，如果gu的父结点是红色的，则需要继续调整。如果gu的父结点是黑色，则结束。如果gu是根结点，则将gu的颜色改为黑色（所有路径的黑色结点数增加1个），结束。改变pu,gu，和guR根结点的颜色自底向上－put：LLr注：1、红色结点变为黑色，会造成经过该结点的从根到外部结点的路径黑色的结点比不经过该结点的路径多了1个黑色结点，违背BR3。2、黑色结点变为红色，可能会造成两个连续相邻的红色结点，违背BR2。upuguuLuRpuLguRupuguuLuRpuLguR分析同前，有可能需要继续调整gu。自底向上－put：LRrupuguuLuRpuLguLupuguuLuRpuLguLupuguuLuRpuRguLupuguuLuRpuRguL自底向上－put：RRr、RLr当结点u的叔父结点为红色时，无论是LLr、LRr、RRr或RLr，都是改变3个结点的颜色：pu，gu和guL/R的颜色：红变黑，黑变红。然后，如果需要，继续调整gu，直到gu为根结点或gu不是根结点但是黑色。注：只要改变3个结点的颜色，然后继续调整。自底向上－put：XYr小结upuguuLuRpuRguRupuguuLuRpuRguR旋转，改变pu,gu的颜色upuguuLuRpuLguLupuguuLuRpuLguL旋转，改变pu,gu的颜色自底向上－put：LLb、RRb注：不需要再调整。旋转upuguuLuRpuLguRupuguuLuRpuLguR旋转，成LLbupuguuLuRpuLguR改变u,gu的颜色注：如果在第1次旋转后，交换pu和u的名字，则第2次旋转和改变颜色的规则完全同LLb，即1次旋转可以将LRb变换为LLb。自底向上－put：LRb旋转旋转，成RRbupuguuLuRpuRguL改变u,gu的颜色upuguuLuRpuRguLupuguuLuRpuRguL自底向上－put：RLb1、RLb和LRb经过1次旋转后，变换为RRb和LLb（同时将u更名为pu）。2、RRb和LLb经过1次旋转，然后改变pu和gu的颜色，最终pu为黑色，gu为红色。3、经过旋转后，调整就结束，不会继续向上调整。自底向上－put：XYb小结put－实例50908010初始时插入70，因为70的父结点是黑色，不需要调整5090801070初始时插入60，父结点是红色，需要调整。因为是XYr型，改变3个结点的颜色。5090801070509080107060501060907080自底向上－put：实例插入65，父结点是红色，叔父是外部结点，为黑色。进行2次旋转，改变pu和gu的颜色。5010609070806550106090658070注：如果编程时将所有虚拟的外部结点用一个实际存在的结点实现，就不用区分叔父结点是空指针还是一般结点。自底向上－put：实例插入62，父结点是红色，叔父是红色。改变3个结点的颜色。但65的父结点是红色，需要继续调整结点65。50106090658070625010908062706065自底向上－put：实例65的叔父结点是10，为黑色。需要进行2次旋转，并改变2个结点的颜色。5010908062706065旋转5010908062706065自底向上－put：实例旋转，变颜色5010908062706065651090806270605065的叔父结点是10，为黑色。需要进行2次旋转，并改变2个结点的颜色。自底向上－put：实例由二叉搜索树知，被删除的结点是叶子结点或者只有1个孩子结点。(如果有2个孩子结点，则已经变换为只有1个孩子结点）对红黑树1、如果被删除的结点是红色的，则直接删除，不会破坏任何规则。2、如果被删除的结点是黑色的，并且孩子结点是红色的，则删除这个结点，并且把孩子结点的颜色改为黑色，不会破坏任何规则。3、如果被删除的结点是黑色，并且孩子结点也是黑色，则删除这个结点，会造成从根结点到外部结点经过这个被删除结点的路径上少了1个黑色结点，破坏了BR3，需要进行调整。但是，如果被删除的结点是根结点，则启用新的根，不用做调整。自底向上－remove在下面使用y代表以被删除结点的孩子结点为根的子树，有时也代表这棵子树的根结点（如果被删除结点是叶子结点，则该子树为空），根据前面的假设y一定是黑色。y一定有父结点py（因为需要调整，所以被删除的结点不是根结点），而且y子树中少了1个黑色结点，所以，它一定有1个兄弟结点v，而且这个兄弟结点不是外部结点（否则，从根到兄弟结点的路径上就少1个黑色结点，违反BR3。）根据兄弟结点和兄弟结点的孩子结点的颜色以及兄弟结点的位置，可以分别处理：自底向上－remove自底向上－remove：Rb0(i)Rb0:y是右孩子，其兄弟结点v是黑色，并且v的两个孩子都是黑色结点(0个红色孩子），py是黑色。分析：1、因为v的父、孩子结点都是黑色，所以不会造成出现2个连续的红色结点。2、但从根结点到vL和vR中的外部结点的路径上就少了1个黑色结点。3、因为删除的是黑色结点，所以，从根结点到y中的外部结点的路径上少了1个黑色结点。4、综合2和3，从根结点到以py为根的子树中的外部结点的路径上少了1个黑色结点，因此，把py当成y，继续调整。5、vL、vR和y的相对位置没有变化，保证中序遍历得到的结点序列仍然是有序的。vpyvLvRyvpyvLvRy改颜色vpyvLvRy改颜色分析：1、从根结点到vL和vR中外部结点的路径上的黑色结点数目在改颜色前后没有变化。2、从根结点到y中的外部结点的路径上的黑色结点数目在改颜色后多了1个，补偿了因为删除少的1个黑色结点。3、以py为根结点的子树在的根结点由红变为黑，不会造成出现连续的2个红色结点，也没有增加从根结点到其它外部结点路径上黑色结点的数目。（因为那些路径本来就不经过py）。4、不需要进一步调整，调整结束5、同前面的分析。py的颜色为红，其它同Rb0(i)vpyvLvRy自底向上－remove：Rb0(ii)v的左孩子是红色,其它同前。vpyvLvRyvpyvLvRy分析：验证没有造成2个红色结点相邻、从根结点到vL、vR和y中外部结点路径上的黑色结点没有变化、3棵子树的相对位置没有变化。调整结束。py的颜色任意，在转换前后不变化自底向上－remove：Rb1(i)旋转，如果py是黑色，则将vL根结点改成黑色，否则，vL的颜色不变。即vL与py同颜色。v的右孩子是红色，其它同前。因为w是红色，所以它的左右孩子必需都为黑色。旋转vpyvLvRywwLwRvpyvLywwLwRvpyvLywwLwR旋转w继承py的颜色，py改为黑色分析：同前。调整结束。自底向上－remove：Rb1(ii)v的左右孩子都红色，其它同前。按Rb1(ii)处理。vpyvLvRy自底向上－remove：Rb2y是py的右孩子，v是红色，vR没有红色的孩子(两个孩子是黑色)。vpyvLvRyvpyvLvRy旋转改变v和vR的颜色分析：v的双亲和两个孩子一定都是黑色结点；因为y少了1个黑色结点，v是红色，所以vL和vR不会是空树1、因为假设子树vR根结点的两个孩子结点都是黑色的，所以，将vR根结点改成红色，不会造成2个红色结点相邻。2、根到vL和vR中外部结点路径上的黑色结点数在调整前后没有变化。3、根到子树y的外部结点路径上多了1个黑色结点，补偿了因删除少了1个黑色结点。4、3棵子树vL、vR和y的相对位置在调整前后没有变化。自底向上－remove：Rr0vR的右孩子w(w肯定不是外部结点)的左孩子是红色。旋转vpyvLvRywwLwRvpyvLywwLwRvpyvLywwLwR旋转wL改成黑色自底向上－remove：Rr1(i)旋转旋转vpyvLywwLxRxxL2、vR的右孩子的右孩子x是红色，x的两个孩子肯定是黑色。vpyvLywwLxRxxLvpyvLywwLxRxxLvpyvLywwLxRxxL旋转将x的颜色改成黑色vR自底向上－remove：Rr1(ii)vR的右孩子w的左右孩子都是红色。按Rr1(ii)处理。vpyvLvRywwLwR自底向上－remove：Rr2如果y的兄弟结点是红色，则要看靠近y的侄孙结点的颜色进行1-3次旋转并改颜色。自底向上－remove：RrX小结1、y在左边，兄弟结点v是黑色，其两个孩子都是黑色。处理方法同Rb0(i)，都是将v改成红色，继续调整pyvpyvLvRyvpyvLvRy继续调整py自底向上－remove：Lb0(i)改颜色vpyvLvRy1、Lb0(ii):同Rb0(ii)。vpyvLvRy分析：根到y中外部结点的路径上多了1个黑色结点，补偿了因为删除少的那个黑色结点。根到vL和vR中外部结点路径上说的黑色结点数目没有变化。自底向上－remove：Lb0(ii)2、Lb1(i):类同Rb1(i)，但旋转方向不一样，红色孩子的位置相反。旋转，如果py是黑色，则将vR根结点改成黑色，否则，vR的颜色不变。即vR与py同颜色。py的颜色任意，在转换前后不变化vpyvLvRyvpyvLvRy自底向上－remove：Lb1(i)2、Lb1(ii)。类同Rb1(ii)，但是旋转方向相反，最终w,py的颜色一致。旋转旋转w继承py的颜色，py改为黑色调整结束。vpywLvRywRwvLvpywLvRywRwvpywLvRywRw自底向上－remove：Lb1(ii)2、Lb2，按Lb1(ii)处理。vpyvLvRy自底向上－remove：Lb21、如果2个侄子都为黑，改颜色。否则2、看侄子结点的颜色，远离y的侄子结点为红1次旋转加改颜色，靠近y的侄子结点为红，2次旋转加改颜色。3、目的是让y多1个黑色结点，其它子树的黑色结点数不变。。自底向上－remove：LbX小结y是py的左孩子，v是红色，vL的两个孩子是黑色。vpyvLvRy旋转改变v和vL的颜色vpyvLvRy自底向上－remove：Lr0vL的左孩子w的右孩子是红色。旋转vpyvLvRywwLwR旋转vpyvRywwLwRvpyvRywwLwRwR改成黑色自底向上－remove：Lr1(i)旋转旋转vpyvRywwRxRxxLvL的左孩子w的左孩子x是红色。旋转将x的颜色改成黑色vpyvRywwRxRxxLvpyvRywwRxRxxLvpyvRywwRxRxxL自底向上－remove：Lr1(ii)vL的左孩子w的左右孩子都是红色。按Lr1(ii)处理。vpyvLvRywwLwR自底向上－remove：Lr2共有：1(删红色)+1(删黑色+孩子红色)+1(删根结点)+删黑色+孩子结点黑色：9*2=21种情况自底向上－remove小结6510908062706050初始删除90，Rb0(ii)，改变70和80的颜色65108062706050y65107062806050自底向上－remove：实例删除8065107062806050改变70的颜色651062605070自底向上－remove：实例删除70Rr1(ii),旋转3次，改变62的颜色6510626050706510626050y6510605062自底向上－remove：实例vpyvLvRy因为v是红色，所以它的父结点、左右孩子都是黑色，并且，因为删除了1个黑色结点，所以v的左右孩子都不是外部结点。旋转后，没有破坏任何规则，并且y的兄弟结点是黑色的，可以按照前面的分析处理。v黑色，py红色vpyvRyvL旋转当v是红色时，除了按照前面的分析处理外，还可以将它变换为v是黑色结点的情形进行处理。自底向上－remove：变换vpyvLvRy因为v是红色，所以它的父结点、左右孩子都是黑色，并且，因为删除了1个黑色结点，所以v的左右孩子都不是外部结点。旋转后，没有破坏任何规则，并且y的兄弟结点是黑色的，可以按照前面的分析处理。v黑色，py红色vpyvRyvL旋转自底向上－remove：变换自顶向下－put从前面(自底向上的put)的分析可以发现：1、如果新插入结点（红色）的父结点是黑色，则直接插入即可。2、如果新插入结点（红色）的父结点是红色，但叔父结点是黑色，则通过旋转就可以完成调整，不需要继续向上进行调整。基本思路：保证任何结点的两个孩子结点不会都是红色：在从根到插入位置的查找过程中，如果某个结点x是黑色，并且两个孩子都是红色，则按照下面的更改父子结点的颜色：xx这样可以保证，如果插入结点的父结点是红色，则其叔父结点一定是黑色。自顶向下－putxx分析：1、改变颜色前后，从根结点到以x为根的子树的外部结点路径上黑色结点的数量没有改变，所以，不会违反规则BR3。2、如果x的父结点是红色，则改变颜色后，会造成两个红色结点相邻，但x的叔父结点一定是黑色，可以用旋转进行调整，避免违反BR2，不会继续向上波及。3、有可能将根结点改成红色，最后要改成黑色。自顶向下－put：实例301065580508560157020904055初始插入45，搜索路径为30->70->60->50->40。在结点50，需要改变父子结点的颜色，如下：301065580558560157020905040自顶向下－put：实例改变50的颜色后，出现了50-60两个连续红色结点，但50的叔父结点85是黑色的，旋转301065580558560157020905040301065580558570156020905040自顶向下－put：实例301065580558570156020905040插入45，其父结点是黑色，结束。30106558055857015602090504045自顶向下－remove从前面的分析可以发现：1、如果被删除的结点是红色，则直接删除即可。2、如果被删除的结点是黑色，但其孩子结点是红色，则改变孩子结点的颜色即可。3、如果被删除的结点是黑色，其孩子结点也是黑色。如果父结点是红色，则可以一次调整解决问题。基本思路：在从根到删除结点的查找过程中，如果某个结点x是黑色，则尽可能将它改成红色，删除时是1的情形。如果不能调整成黑色，则延迟处理，保证是情形3。自顶向下－remove首先：引进1个“头结点”，让它的颜色是红色，并作为根结点的父结点：然后，从根结点开始，在向下的查找过程中，遇到黑色的结点，就改变颜色为红色。将要更改颜色的结点命名为当前结点，用x表示。根结点头结点x的父结点p一定是红色，根据RB2，兄弟结点s一定是黑色。pxs对x和s孩子结点的颜色组合进行分析、处理：自顶向下－remove：LBr0x是父结点的左孩子(L)，x两个孩子结点都是黑色(B)，s有0个红色的孩子结点(r0)。改变x、p和s的颜色pxssLsRxLxRpxssLsRxLxR自顶向下－remove：LBr1(i)x是父结点的左孩子，x的两个孩子结点都是黑色，s右孩子是红色。改变x、p、s和sR的颜色pxssLsRxLxRpxssLsRxLxR旋转自顶向下－remove：LBr1(ii)x是父结点的左孩子，x的两个孩子结点都是黑色，s左孩子是红色。改变x、p的颜色旋转pxssLsRxLxRnnLnRpxssRxLxRnnLnRxpssRxLxRnnLnR旋转自顶向下－remove：LBr2x是父结点的左孩子，x的两个孩子结点都是黑色，s两个孩子都是红色。pxssLsRxLxR参照LBr1(i)处理。自顶向下－remove：RBr0x是父结点的右孩子，x和s的两个孩子结点都是黑色。改变x、p和s的颜色psxxLxRsLsRpsxxLxRsLsR自顶向下－remove：RBr1(i)x是父结点的右孩子，x的两个孩子结点都是黑色，s左孩子是红色。改变x、p、s和sL的颜色psxxLxRsLsRpxssLsRxLxR旋转自顶向下－remove：RBr1(ii)x是父结点的右孩子，x的两个孩子结点都是黑色，s右孩子是红色。改变x、p的颜色旋转pxssLsRxLxRnnLnR旋转pxssLxLxRnnLnRpxssLxLxRnnLnR自顶向下－remove：RBr2x是父结点的右孩子，x的两个孩子结点都是黑色，s两个孩子都是红色。参照RBr1(i)处理。psxxLxRsLsR自顶向下－remove：LBr?和RBr?调整前，父结点p是红色，当前结点x是黑色。调整后，p是黑色，x是红色。自顶向下－remove：XR型x是父结点的左或右孩子，x至少有1个红色的孩子，如下图：pxsxLxR此时x的父结点是红色，暂缓处理，继续向下查找。pxsxLxRpxsxLxRpxsxLxRpxsxLxRpxsxLxR自顶向下－remove：XR型下一个当前结点或者是xL的根结点或者是xR的根结点，如果这个结点是红色，不需要调整，继续向下。如果是黑色，一种情况如下图，即xR是当前结点。以x为根的子树经旋转和改颜色后完成了一次变换，调整后，当前结点仍然是黑色，但父结点是红色。旋转xLLxLRpxsxLxRxxRxLxLLxLR自顶向下－remove：XR型另一种情况如下图，即向xR是当前结点。以x为根的子树经旋转和改颜色后完成了一次变换，调整后，当前结点仍然是黑色，但父结点是红色。旋转xR