参考
http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#.E6.8F.92.E5.85.A5
1.有二叉平衡树,why红黑树。
二叉平衡树的缺点,在删除时,需要调整整棵树,费时间。红黑树只需要调整局部
2.红黑树性质:
1).所有节点非红即黑
2).根是黑的
3).所有叶子是黑的。(叶子指不存数据的NULL结点)
4).红结点的儿子一定是黑的
5).从任意结点出发,到其所有叶子节点的路径上黑色节点数相同。(同一结点到不同叶子结点路径上)
3.红黑树的插入
新插入的结点默认为红色,这样可以保证性质5),若性质4)收到威胁,再采取措施
先分析:我们可以得到
性质1)3)可以始终保持,
性质4)在增加红色结点、重绘黑色结点为红色、做旋转时受到威胁
性质5)在增加黑色结点、重绘红色结点为黑色、做旋转时受到威胁
在如下描述中,新插入的标记为N,N的父亲标记为P,N的祖父标记为G,N的叔父标记为U.先分析插入的情况
(3.1)N为根节点。直接重绘为黑色
(3.2)P为黑色。直接插入
一下情况P为红色,由1)得知,N一定有叔父结点。ps 不存数据的NULL叶子节点也可以使叔父结点。
(3.3)P和U都是红色,N为P的左儿子或右儿子。则把PU重绘黑,G重绘红。在把G当做N进行从(3.1)开始的各种情况的检查。
(3.4)P红色,而U为黑色(包括U为存数据的黑色以及叶子节点的黑色),N是P的右儿子,P是G的左儿子。则进行左旋,接着按(3.5)做处理
(3.5)P红色,而U为黑色(包括U为存数据的黑色以及叶子节点的黑色),N是P的左儿子,P是G的左儿子。对G进行右旋
插入实际上是原地算法,上述都采用了尾部递归。
4.红黑树的删除
首先把删除两个具有两个儿子节点(非叶子儿子)的问题转化为删除另一个只有一个儿子节点的问题(非叶子儿子)。先找到左子树中最大元素或者右子树中最小元素来顶替节点,即把找到的结点先转移到要删除的结点中,接着再删除我们从中复制出的那个结点。
若选择复制左子树的最大节点,复制出的那个结点有下图三种情况(最大节点,故要删除的结点没有右儿子)。
(1)红色结点,左右儿子为不存数据的NULL。则直接删除,结束。不破坏性质
(2)黑色结点,左右儿子为不存数据的NULL。这个情况删除略微麻烦,见下面详细讨论
(3)黑色结点,左儿子为红色,右儿子为NULL。这种情况,删掉黑色后,原本指向黑色结点的指针指向黑色结点的左儿子,并把左儿子重绘为黑色,结束。
其他情况若有左儿子,则不满足性质(4),即红色结点左儿子为红色。或者性质(5),黑色结点左儿子为黑色。
下面都来讨论删除该复制出的那个结点,要删除的结点是N。删除上面第(2)中情况
(4.1)N是新根,直接删除
(4.2)S红色(推出P为黑)。则在P上左旋转,然后对调N的P和G的颜色。此时N的新S为黑,P为红,以左边框内作为单位,转到(4.4)(4.5)(4.6)来处理
(4.3)N的P、S以及S的SL、SR都是黑色。把S重绘为红色。则该小单元在删除N后黑色个数相同,则把框内看成整体,从(4.1)开始调整。即从(4.1)开始,在P上做重新平衡处理
(4.4)N的P为红色,S以及SL、SR都是黑色。则把P和S的颜色交换,就完成了
(4.5)S黑色,SL红色,SR黑色。将S做右旋,再交换SL和S的颜色,再由(4.6)处理
(4.6)S黑色,SR红色。在P点做左旋;交换P,S的颜色;把SR重绘为黑色。这样通过N的路径上多了一个黑色,N可以删除了
2021年9月06日 15:37
When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. 123movies