6
5
2014
4

红黑树

参考

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可以删除了

 

Category: 算法、数据结构 | Tags: | Read Count: 1779
Avatar_small
Digital Ali 说:
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

Avatar_small
Axis Bank NEFT Form 说:
2022年11月02日 22:11

Axis bank Ranks among the top three largest banks in India, offering financial and banking services. The bank has over the years, open new branches, and introduced new services to loyal customers. It has open new platforms for bank transfers such as internet banking services . Axis Bank NEFT Form Axis bank uses RTGS and NEFT services to transfer funds from one bank to the other. It's a convenient and secure way for customers to transfer and bank their money.

Avatar_small
tneb online payment 说:
2022年12月16日 22:01

The Tamil Nadu Electricity Board (TNEB) was established on July 1, 1957, as a highly integrated utility responsible for generating electricity, transmission, and distribution under Section 54 of the Electricity (Supply) Act of 1948 relating to Tamil Nadu. tneb online payment State Citizens can register to pay their electricity bills and check the status of their connection along with the paid bill by registering at TANGEDCO / TNEBNET portal. This guide will explain the registration process along with Login and Status check online in a simple manner.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com