精华内容
下载资源
问答
  • 红黑树

    万次阅读 2011-02-11 21:56:00
    介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树...自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。不过

     

    介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和Robert Sedgewick改成一个比较摩登的名字:红黑树。

    红黑树和之前所讲的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。不过在我了解了红黑树的实现原理后,并不相信这是真的,关于这一点我们会在后面进行讨论。

    红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时,已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

    首先来一个Silverlight做的红黑树的动画,它有助于帮你理解什么是红黑树。这里需要注意,必须安装Silverlight 2.0 RTW 才能正常运行游戏,下载地址:

    http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0

     

    使用注意事项:

    l         结点只接收整数,如果在添加和删除操作中输入非法字串,则会随机添加或删除一个0~99之间的整数。

    l         可以不在编辑框中输入数字,直接单击添加和删除按钮进行添加和删除操作。

    l         可以拖动拖动条控制动画速度。

    红黑树的平衡

    红黑树首先是一棵二叉查找树,它每个结点都被标上了颜色(红色或黑色),红黑树满足以下5个性质:

    1、 每个结点的颜色只能是红色或黑色。

    2、 根结点是黑色的。

    3、 每个叶子结点都带有两个空的黑色结点(被称为黑哨兵),如果一个结点n的只有一个左孩子,那么n的右孩子是一个黑哨兵;如果结点n只有一个右孩子,那么n的左孩子是一个黑哨兵。

    4、 如果一个结点是红的,则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

    5、 对于每个结点来说,从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

    红黑树的这5个性质中,第3点是比较难理解的,但它却非常有必要。我们看图1中的左边这张图,如果不使用黑哨兵,它完全满足红黑树性质,结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后(如图1右图中的小黑圆点),叶结点的个数变为8个黑哨兵,根结点50到这8个叶结点路径上的黑高度就不一样了,所以它并不是一棵红黑树。

     

     

    要看真正的红黑树请在以上动画中添加几个结点,看看是否满足以上性质。

    红黑树的旋转操作

    红黑树的旋转操作和AVL树一样,分为LL、RR、LR、RL四种旋转类型,差别在于旋转完成后改变的是结点的颜色,而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画:

    http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

    红黑树上结点的插入

    在讨论红黑树的插入操作之前必须要明白,任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解,因为插入黑点会增加某条路径上黑结点的数目,从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时(如图2所示),将会违返红黑树性质:一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

     

     

     

    为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点;使用“父”字表示新插入点的父结点;使用“叔”字表示“父”结点的兄弟结点;使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况:

    1黑父

    如图3所示,如果新点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见,从而使红黑树需要旋转的几率相对AVL树来说会少一些。

     

     

     

    2.红父

    如果新点的父结点为红色,这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示,由于父结点为红色,此时可以判定,祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作,而每次进行不平衡判断的起始点(我们可将其视为新点)都不一样。所以我们在此使用一个蓝色箭头指向这个起始点,并称之为判定点。

     

     

     

    2.1 红叔

    当叔父结点为红色时,如图4所示,无需进行旋转操作,只要将父和叔结点变为黑色,将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色,从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。

     

     

    需要注意,无论“父”在“叔”的左边还是右边,无论“新”是“父”的左孩子还是右孩子,它们的操作都完全一样。

     

    2.2 黑叔

    当叔父结点为黑色时,需要进行旋转,以下图示了所有的旋转可能

    情形1:

     

     

    情形2:

     

    情形3:

     

     

    情形4:

     

     

    可以观察到,当旋转完成后,新的旋转根全部为黑色,此时不需要再向上回溯进行平衡操作,插入操作完成。需要注意,上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

    其实红黑树的插入操作不是很难,甚至比AVL树的插入操作还更简单些。但删除操作就远远比AVL树复杂得多,下面就介绍红黑树的删除操作。

    红黑树上结点的删除

    红黑树本身是一棵二叉查找树,它的删除和二叉查找树的删除类似。首先要找到真正的删除点,当被删除结点n存在左右孩子时,真正的删除点应该是n的中序遍在前驱,关于这一点请复习二叉查找树的删除。如图9所示,当删除结点20时,实际被删除的结点应该为18,结点20的数据变为18。

     

     

     

    所以可以推断出,在进行删除操作时,真正的删除点必定是只有一个孩子或没有孩子的结点。而根据红黑树的性质可以得出以下两个结论:

    1、 删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点

    2、 如果真正的删除点是一个红色结点,那么它必定是一个叶子结点

    理解这两点非常重要,如图10所示,除了情况(a)外,其他任一种况结点N都无法满足红黑树性质。

     

     

     

    在以下讨论中,我们使用蓝色箭头表示真正的删除点,它也是旋转操作过程中的第一个判定点;真正的删除点使用“旧”标注,旧点所在位置将被它的的孩子结点所取代(最多只有一个孩子),我们使用“新”表示旧点的孩子结点。删除操作可分为以下几种情形:

    1、旧点为红色结点

    若旧点为红色结点,则它必定是叶子结点,直接删除即可。如图11所示

     

     

     

    2、一红一黑

    当旧点为黑色结点,新点为红色结点时,将新点取代旧点位置后,将新点染成黑色即可(如图12所示)。这里需要注意:旧点为红色,新点为黑色的情况不可能存在。

     

     

     

    3、双黑

    当旧点和新点都为黑色时(新点为空结点时,亦属于这种情况),情况比较复杂,需要根据旧点兄弟结点的颜色来决定进行什么样的操作。我们使用“兄”来表示旧点的兄弟结点。这里可分为红兄和黑兄两种情况:

    3.1 红兄

    由于兄弟结点为红色,所以父结点必定为黑色,而旧点被删除后,新点取代了它的位置。下图演示了两种可能的情况:

     

     

     

    红兄的情况需要进行RR或LL型旋转,然后将父结点染成红色,兄结点染成黑色。然后重新以新点为判定点进行平衡操作。我们可以观察到,旋转操作完成后,判定点没有向上回溯,而是降低了一层,此时变成了黑兄的情况。

    3.2 黑兄

    黑兄的情况最为复杂,需要根据黑兄孩子结点(这里用“侄”表示)和父亲结点的颜色来决定做什么样的操作。

    3.2.1 黑兄二黑侄红父

    如图14所示,这种情况比较简单,只需将父结点变为黑色,兄结点变为黑色,新结点变为黑色即可,删除操作到此结束。

     

     

     

    3.2.2 黑兄二黑侄黑父

    如图15所示,此时将父结点染成新结点的颜色,新结点染成黑色,兄结点染成红色即可。当新结点为红色时,父结点被染成红色,此时需要以父结点为判定点继续向上进行平衡操作。

     

     

     

    3.2.3 黑兄红侄

    黑兄红侄有以下四种情形,下面分别进行图示:

    情形1:

     

     

    情形2:

     

    情形3:

     

    情形4:

     

     

     

    由以上图例所示,看完以上四张图的兄弟有可能会有一个疑问,如果情形1和情形2中的两个侄子结点都为红色时,是该进行LL旋转还是进行LR旋转呢?答案是进行LL旋转。情形3和情形4则是优先进行RR旋转的判定。

     

     

     

     

     

     

     

     

        教你透彻了解红黑树

     

    作者 July、saturnman   2010年12月29日

    本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。
    本人声明:个人原创,转载请注明出处。

    推荐阅读:Left-Leaning Red-Black TreesDagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.

    ------------------------------
    红黑树系列,四篇文章于今日已经完成。[二零一一年一月九日]

    教你透彻了解红黑树:
    http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
    红黑树算法的层层剖析与逐步实现  [此文被推荐]
    http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
    教你彻底实现红黑树:红黑树的c源码实现与剖析
    http://blog.csdn.net/v_JULY_v/archive/2011/01/03/6114226.aspx
    一步一图一代码,一定要让你真正彻底明白红黑树 [最后更新]
    http://blog.csdn.net/v_JULY_v/archive/2011/01/09/6124989.aspx

    ------------------------------

     

    一、红黑树的介绍

    先来看下算法导论对R-B Tree的介绍:
    红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。
    通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其
    他路径长出俩倍,因而是接近平衡的。

     

    前面说了,红黑树,是一种二叉查找树,既然是二叉查找树,那么它必满足二叉查找树的一般性质。
    下面,在具体介绍红黑树之前,咱们先来了解下 二叉查找树的一般性质:
    1.在一棵二叉查找树上,执行查找、插入、删除等操作,的时间复杂度为O(lgn)。
        因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,一般操作的执行时间为O(lgn)。
        //至于n个结点的二叉树高度为lgn的证明,可参考算法导论 第12章 二叉查找树 第12.4节。
    2.但若是一棵具有n个结点的线性链,则此些操作最坏情况运行时间为O(n)。

     

    红黑树,能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)。

    ok,我们知道,红黑树上每个结点内含五个域,color,key,left,right。如果相应的指针域没有,则设为NIL。

    一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

     

    下图所示,即是一颗红黑树:

    此图忽略了叶子和根部的父结点。

     

    二、树的旋转知识

    当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。

    为了保持红黑树的性质,我们可以通过对树进行旋转,即修改树种某些结点的颜色及指针结构,以达到对红黑树进行

    插入、删除结点等操作时,红黑树依然能保持它特有的性质(如上文所述的,五点性质)。

     

    树的旋转,分为左旋和右旋,以下借助图来做形象的解释和介绍:

    1.左旋

    如上图所示:

    当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为树内任意右孩子而不是NIL[T]的结点。

    左旋以pivot到y之间的链为“支轴”进行,它使y成为该孩子树新的根,而y的左孩子b则成为pivot的右孩子。

    来看算法导论对此操作的算法实现(以x代替上述的pivot):

     LEFT-ROTATE(Tx)
    1  y  right[x Set y.
    2  right[x left[y]       Turn y's left subtree into x's right subtree.

    3  p[left[y]]  x
    4  p[y p[x]              Link x's parent to y.
    5  if p[x] = nil[T]
    6     then root[T y
    7     else if x = left[p[x]]
    8             then left[p[x]]  y
    9             else right[p[x]]  y
    10  left[y x              Put x on y's left.
    11  p[x y

     

    2.右旋

    右旋与左旋差不多,再此不做详细介绍。

     

    对于树的旋转,能保持不变的只有原树的搜索性质,而原树的红黑性质则不能保持,

    在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。

     

    至于有些书如 STL源码剖析有对双旋的描述,其实双旋只是单旋的两次应用,并无新的内容,

    因此这里就不再介绍了,而且左右旋也是相互对称的,只要理解其中一种旋转就可以了。

     

    三、红黑树插入、删除操作的具体实现

       三、I、ok,接下来,咱们来具体了解红黑树的插入操作。
    向一棵含有n个结点的红黑树插入一个新结点的操作可以在O(lgn)时间内完成。

    算法导论:
    RB-INSERT(T, z)
     1  y ← nil[T]
     2  x ← root[T]
     3  while x ≠ nil[T]
     4      do y ← x
     5         if key[z] < key[x]
     6            then x ← left[x]
     7            else x ← right[x]
     8  p[z] ← y
     9  if y = nil[T]
    10     then root[T] ← z
    11     else if key[z] < key[y]
    12             then left[y] ← z
    13             else right[y] ← z
    14  left[z] ← nil[T]
    15  right[z] ← nil[T]
    16  color[z] ← RED
    17  RB-INSERT-FIXUP(T, z)

    咱们来具体分析下,此段代码:
    RB-INSERT(T, z),将z插入红黑树T 之内。

    为保证红黑性质在插入操作后依然保持,上述代码调用了一个辅助程序RB-INSERT-FIXUP
    来对结点进行重新着色,并旋转。

    14  left[z] ← nil[T]
    15  right[z] ← nil[T]  //保持正确的树结构
    第16行,将z着为红色,由于将z着为红色可能会违背某一条红黑树的性质,
    所以,在第17行,调用RB-INSERT-FIXUP(T,z)来保持红黑树的性质。

    RB-INSERT-FIXUP(T, z),如下所示:
     1 while color[p[z]] = RED
     2     do if p[z] = left[p[p[z]]]
     3           then y ← right[p[p[z]]]
     4                if color[y] = RED
     5                   then color[p[z]] ← BLACK                    ▹ Case 1
     6                        color[y] ← BLACK                       ▹ Case 1
     7                        color[p[p[z]]] ← RED                   ▹ Case 1
     8                        z ← p[p[z]]                            ▹ Case 1
     9                   else if z = right[p[z]]
    10                           then z ← p[z]                       ▹ Case 2
    11                                LEFT-ROTATE(T, z)              ▹ Case 2
    12                           color[p[z]] ← BLACK                 ▹ Case 3
    13                           color[p[p[z]]] ← RED                ▹ Case 3
    14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3
    15           else (same as then clause
                             with "right" and "left" exchanged)
    16 color[root[T]] ← BLACK

     
    ok,参考一网友的言论,用自己的语言,再来具体解剖下上述俩段代码。
    为了保证阐述清晰,我再写下红黑树的5个性质:

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

     

    在对红黑树进行插入操作时,我们一般总是插入红色的结点,因为这样可以在插入过程中尽量避免对树的调整。
    那么,我们插入一个结点后,可能会使原树的哪些性质改变列?
    由于,我们是按照二叉树的方式进行插入,因此元素的搜索性质不会改变。

    如果插入的结点是根结点,性质2会被破坏,如果插入结点的父结点是红色,则会破坏性质4。
    因此,总而言之,插入一个红色结点只会破坏性质2或性质4。
    我们的回复策略很简单,
    其一、把出现违背红黑树性质的结点向上移,如果能移到根结点,那么很容易就能通过直接修改根结点来恢复红黑树的性质。直接通过修改根结点来恢复红黑树应满足的性质。
    其二、穷举所有的可能性,之后把能归于同一类方法处理的归为同一类,不能直接处理的化归到下面的几种情况,

     //注:以下情况3、4、5与上述算法导论上的代码RB-INSERT-FIXUP(T, z),相对应:

     

    情况1:插入的是根结点。
    原树是空树,此情况只会违反性质2。
      对策:直接把此结点涂为黑色。
    情况2:插入的结点的父结点是黑色。
    此不会违反性质2和性质4,红黑树没有被破坏。
      对策:什么也不做。
    情况3:当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色。
    此时父结点的父结点一定存在,否则插入前就已不是红黑树。
    与此同时,又分为父结点是祖父结点的左子还是右子,对于对称性,我们只要解开一个方向就可以了。

    在此,我们只考虑父结点为祖父左子的情况。
    同时,还可以分为当前结点是其父结点的左子还是右子,但是处理方式是一样的。我们将此归为同一类。
      对策:将当前节点的父节点和叔叔节点涂黑,祖父结点涂红,把当前结点指向祖父节点,从新的当前节点重新开始算法。

    针对情况3,变化前(图片来源:saturnman)[插入4节点]:

    变化后:

    情况4:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

    对策:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。

    如下图所示,变化前[插入7节点]:

     

    变化后:

     

     

    情况5:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左子

    解法:父节点变为黑色,祖父节点变为红色,在祖父节点为支点右旋

    如下图所示[插入2节点]

    变化后:

     

     

    ==================

       三、II、ok,接下来,咱们最后来了解,红黑树的删除操作:

    算法导论一书,给的算法实现: 

    RB-DELETE(T, z)   单纯删除结点的总操作
     1 if left[z] = nil[T] or right[z] = nil[T]
     2    then y ← z
     3    else y ← TREE-SUCCESSOR(z)
     4 if left[y] ≠ nil[T]
     5    then x ← left[y]
     6    else x ← right[y]
     7 p[x] ← p[y]
     8 if p[y] = nil[T]
     9    then root[T] ← x
    10    else if y = left[p[y]]
    11            then left[p[y]] ← x
    12            else right[p[y]] ← x
    13 if y 3≠ z
    14    then key[z] ← key[y]
    15         copy y's satellite data into z
    16 if color[y] = BLACK
    17    then RB-DELETE-FIXUP(T, x)
    18 return y

     

    RB-DELETE-FIXUP(T, x)   恢复与保持红黑性质的工作
     1 while x ≠ root[T] and color[x] = BLACK
     2     do if x = left[p[x]]
     3           then w ← right[p[x]]
     4                if color[w] = RED
     5                   then color[w] ← BLACK                        ▹  Case 1
     6                        color[p[x]] ← RED                       ▹  Case 1
     7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
     8                        w ← right[p[x]]                         ▹  Case 1
     9                if color[left[w]] = BLACK and color[right[w]] = BLACK
    10                   then color[w] ← RED                          ▹  Case 2
    11                        x p[x]                                  ▹  Case 2
    12                   else if color[right[w]] = BLACK
    13                           then color[left[w]] ← BLACK          ▹  Case 3
    14                                color[w] ← RED                  ▹  Case 3
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3
    16                                w ← right[p[x]]                 ▹  Case 3
    17                         color[w] ← color[p[x]]                 ▹  Case 4
    18                         color[p[x]] ← BLACK                    ▹  Case 4
    19                         color[right[w]] ← BLACK                ▹  Case 4
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
    21                         x ← root[T]                            ▹  Case 4
    22        else (same as then clause with "right" and "left" exchanged)
    23 color[x] ← BLACK

     

    为了保证以下的介绍与阐述清晰,我第三次重写下红黑树的5个性质

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

    (相信,重述了3次,你应该有深刻记忆了。:D)

     

     saturnman:
    红黑树删除的几种情况:

    -------------------------------------------------
    博主提醒:
    以下所有的操作,是针对红黑树已经删除结点之后,
    为了恢复和保持红黑树原有的5点性质,所做的恢复工作。

    前面,我已经说了,因为插入、或删除结点后,
    可能会违背、或破坏红黑树的原有的性质,
    所以为了使插入、或删除结点后的树依然维持为一棵新的红黑树,
    那就要做俩方面的工作:
    1、部分结点颜色,重新着色
    2、调整部分指针的指向,即左旋、右旋。

    而下面所有的文字,则是针对红黑树删除结点后,所做的修复红黑树性质的工作。

     二零一一年一月七日更新。
    ------------------------------------------------------------

    (注:以下的情况3、4、5、6,与上述算法导论之代码RB-DELETE-FIXUP(T, x) 恢复与保持
    中case1,case2,case3,case4相对应。)
    情况1:当前节点是红色
        解法,直接把当前节点染成黑色,结束。
        此时红黑树性质全部恢复。
    情况2:当前节点是黑色且是根节点
        解法:什么都不做,结束

    情况3:当前节点是黑色,且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
        解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。
        然后,针对父节点做一次左旋。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况。

                         3.变化前:

     

                         3.变化后: 

     

    情况4:当前节点是黑色,且兄弟是黑色,且兄弟节点的两个子节点全为黑色。
          解法:把当前节点和兄弟节点中抽取一重黑色追加到父节点上,把父节点当成新的当前节点,重新进入算法。(此变换后性质5不变)

                            4.变化前

     

                            4.变化后

     

    情况5:当前节点颜色是黑色,兄弟节点是黑色,兄弟的左子是红色,右子是黑色。
        解法:把兄弟结点染红,兄弟左子节点染黑,之后再在兄弟节点为支点解右旋,
    之后重新进入算法。此是把当前的情况转化为情况6,而性质5得以保持。

                  5.变化前:

     

                      5.变化后:

     

    情况6:当前节点颜色是黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意。

        解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,

    之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确。

                        6.变化前:

                  6.变化后:

     

    限于篇幅,不再过多赘述。更多,可参考算法导论或下文我写的第二篇文章。

    完。

    July、二零一零年十二月二十九日初稿。三十日凌晨修订。行文3个小时以上。

    ----------------

     

    今下午画红黑树画了好几个钟头,贴俩张图:

      红黑树插入的3种情况:

     

      红黑树删除的4种情况:

     

    ok,只贴俩张,更多,参考我写的关于红黑树的第二篇文章:

    红黑树算法的层层剖析与逐步实现[推荐]
    http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx

    这篇文章针对算法实现源码分十层,层层、逐层剖析,相信,更清晰易懂。

    //尤其文末针对红黑树的删除情况,层次清晰。

     

                 July、二零一零年十二月三十一日、最后更新。

     

    展开全文
  • 红黑树和AVL树的效率对比

    千次阅读 2016-09-05 20:08:47
    为什么选择红黑树作为底层实现 红黑树是一种类平衡树, 但它不是高度的平衡树, 但平衡的效果已经很好了.... 当你对搜索的效率要求较高,并且数据经常改动的情景,你可以用红黑树, 也就是 map.至于, 为什么不用 AVL

    为什么选择红黑树作为底层实现
    红黑树是一种类平衡树, 但它不是高度的平衡树, 但平衡的效果已经很好了. 补充说明另一种 AVL 树, 我之前的博文: 《编程珠玑,字字珠玑》读书笔记完结篇——AVL树

    用过 STL map 么, 你用过 linux 么(这个说大了), 他们都有红黑树的应用. 当你对搜索的效率要求较高,并且数据经常改动的情景,你可以用红黑树, 也就是 map.

    至于, 为什么不用 AVL 树作为底层实现, 那是因为 AVL 树是高度平衡的树, 而每一次对树的修改, 都要 rebalance, 这里的开销会比红黑树大. 红黑树插入只要两次旋转, 删除至多三次旋转. 但不可否认的是, AVL 树搜索的效率是非常稳定的. 选取红黑树, 我认为是一种折中的方案.

    黑体字是不正确的,对AVL插一个node或者删一个node,显然不需要每次都做rotation来维持balance。且AVL插入最多也只需要2次旋转。

    下面是我的回答:

    1. 如果插入一个node引起了树的不平衡,AVL和RB-Tree都是最多只需要2次旋转操作,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的量级O(logN),而RB-Tree最多只需3次旋转,只需要O(1)的复杂度。

    2. 其次,AVL的结构相较RB-Tree来说更为平衡,在插入和删除node更容易引起Tree的unbalance,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,RB-Tree在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。

    3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,RB-tree的统计性能是高于AVL的。

    最坏情况下,AVL树有最多O(logN)次旋转,而红黑树最多三次。当然,这是个结论,谁能给出一个证明啊。。

    展开全文
  • 红黑树属于平衡二叉树。它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。 红黑树(red-black tree)是一棵满足下述性质的二叉查找...

    红黑树属于平衡二叉树。它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。

    红黑树(red-black tree) 是一棵满足下述性质的二叉查找树

    1. 每一个结点要么是红色,要么是黑色。

    2. 根结点是黑色的。

    3. 所有叶子结点都是黑色的(实际上都是Null指针,下图用NIL表示)。叶子结点不包含任何关键字信息,所有查询关键字都在非终结点上。

    4. 每个红色结点的两个子节点必须是黑色的。换句话说:从每个叶子到根的所有路径上不能有两个连续的红色结点

    5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

    红黑树相关定理

    1. 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

          根据上面的性质5我们知道上图的红黑树每条路径上都是3个黑结点。因此最短路径长度为2(没有红结点的路径)。再根据性质4(两个红结点不能相连)和性质1,2(叶子和根必须是黑结点)。那么我们可以得出:一条具有3个黑结点的路径上最多只能有2个红结点(红黑间隔存在)。也就是说黑深度为2(根结点也是黑色)的红黑树最长路径为4,最短路径为2。从这一点我们可以看出红黑树是 大致平衡的。 (当然比平衡二叉树要差一些,AVL的平衡因子最多为1)

    2. 红黑树的树高(h)不大于两倍的红黑树的黑深度(bd),即h<=2bd

          根据定理1,我们不难说明这一点。bd是红黑树的最短路径长度。而可能的最长路径长度(树高的最大值)就是红黑相间的路径,等于2bd。因此h<=2bd。

    3. 一棵拥有n个内部结点(不包括叶子结点)的红黑树的树高h<=2log(n+1)

          下面我们首先证明一颗有n个内部结点的红黑树满足n>=2^bd-1。这可以用数学归纳法证明,施归纳于树高h。当h=0时,这相当于是一个叶结点,黑高度bd为0,而内部结点数量n为0,此时0>=2^0-1成立。假设树高h<=t时,n>=2^bd-1成立,我们记一颗树高 为t+1的红黑树的根结点的左子树的内部结点数量为nl,右子树的内部结点数量为nr,记这两颗子树的黑高度为bd'(注意这两颗子树的黑高度必然一 样),显然这两颗子树的树高<=t,于是有nl>=2^bd'-1以及nr>=2^bd'-1,将这两个不等式相加有nl+nr>=2^(bd'+1)-2,将该不等式左右加1,得到n>=2^(bd'+1)-1,很显然bd'+1>=bd,于是前面的不等式可以 变为n>=2^bd-1,这样就证明了一颗有n个内部结点的红黑树满足n>=2^bd-1。

            在根据定理2,h<=2bd。即n>=2^(h/2)-1,那么h<=2log(n+1)

            从这里我们能够看出,红黑树的查找长度最多不超过2log(n+1),因此其查找时间复杂度也是O(log N)级别的。

    红黑树的操作

    因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。然而,在红黑树上进行插入操作和删除操作会导致不 再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。 虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次 。

    红黑树的优势

    红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

    而且实际应用中,很多语言都实现了红黑树的数据结构。比如 TreeMap, TreeSet(Java )、 STL(C++)等。

    展开全文
  • 为什么红黑树效率比较高

    千次阅读 2017-08-20 21:57:53
    红黑树属于平衡二叉树。它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。 红黑树(red-black tree) 是一棵满足下述性质的二叉...

    红黑树属于平衡二叉树。它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。

    红黑树(red-black tree) 是一棵满足下述性质的二叉查找树:

    1. 每一个结点要么是红色,要么是黑色。

    2. 根结点是黑色的。

    3. 所有叶子结点都是黑色的(实际上都是Null指针,下图用NIL表示)。叶子结点不包含任何关键字信息,所有查询关键字都在非终结点上。

    4. 每个红色结点的两个子节点必须是黑色的。换句话说:从每个叶子到根的所有路径上不能有两个连续的红色结点

    5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

     

    红黑树相关定理

    1. 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

          根据上面的性质5我们知道上图的红黑树每条路径上都是3个黑结点。因此最短路径长度为2(没有红结点的路径)。再根据性质4(两个红结点不能相连)和性质1,2(叶子和根必须是黑结点)。那么我们可以得出:一条具有3个黑结点的路径上最多只能有2个红结点(红黑间隔存在)。也就是说黑深度为2(根结点也是黑色)的红黑树最长路径为4,最短路径为2。从这一点我们可以看出红黑树是 大致平衡的。 (当然比平衡二叉树要差一些,AVL的平衡因子最多为1)

     

    2. 红黑树的树高(h)不大于两倍的红黑树的黑深度(bd),即h<=2bd

          根据定理1,我们不难说明这一点。bd是红黑树的最短路径长度。而可能的最长路径长度(树高的最大值)就是红黑相间的路径,等于2bd。因此h<=2bd。

     

    3. 一棵拥有n个内部结点(不包括叶子结点)的红黑树的树高h<=2log(n+1)

          下面我们首先证明一颗有n个内部结点的红黑树满足n>=2^bd-1。这可以用数学归纳法证明,施归纳于树高h。当h=0时,这相当于是一个叶结点,黑高度bd为0,而内部结点数量n为0,此时0>=2^0-1成立。假设树高h<=t时,n>=2^bd-1成立,我们记一颗树高 为t+1的红黑树的根结点的左子树的内部结点数量为nl,右子树的内部结点数量为nr,记这两颗子树的黑高度为bd'(注意这两颗子树的黑高度必然一 样),显然这两颗子树的树高<=t,于是有nl>=2^bd'-1以及nr>=2^bd'-1,将这两个不等式相加有nl+nr>=2^(bd'+1)-2,将该不等式左右加1,得到n>=2^(bd'+1)-1,很显然bd'+1>=bd,于是前面的不等式可以 变为n>=2^bd-1,这样就证明了一颗有n个内部结点的红黑树满足n>=2^bd-1。

            在根据定理2,h<=2bd。即n>=2^(h/2)-1,那么h<=2log(n+1)

            从这里我们能够看出,红黑树的查找长度最多不超过2log(n+1),因此其查找时间复杂度也是O(log N)级别的。



    红黑树的操作

     

    因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。然而,在红黑树上进行插入操作和删除操作会导致不 再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。 虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次 。

     

    红黑树的优势

     

    红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

    而且实际应用中,很多语言都实现了红黑树的数据结构。比如 TreeMap, TreeSet(Java )、 STL(C++)等。

    展开全文
  • 以数组为基本形态,数组中的元素先以链表形式储存,当链表的长度超过8时(包含数组上的那个链表头)就会将链表转换为红黑树,以加快修改和查询效率。当然除HashMap还有很多地方都会用到红黑树,理解红黑树的原理还是...
  • 红黑树与AVL树的区别

    千次阅读 2019-03-09 11:25:04
    红黑树效率更高,因为AVL为了保证其完全平衡,插入和删除的时候在最坏的情况下要旋转logN次,而红黑树插入和删除的旋转次数要比AVL少。 AVL树[1],它或者是一颗空二叉树,或者是具有下列性质的二叉树: (1) 其根的...
  • 查找、插入、删除操作的最坏时间复杂度 二叉查找树 平衡二叉树 红黑树 查找 O(n) O(logn) Olog(n) 插入 ...平衡二叉树和红黑树是带有平衡条件的二叉查找树,故它们的效率...
  • 红黑树系列之一:红黑树的概述

    千次阅读 2014-09-24 21:48:40
    一、红黑树的定义
  • 红黑树详解

    2017-05-09 14:07:37
    红黑树  一.红黑树定义 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于...
  • 今天我们要说的红黑树就是就是一棵非严格均衡的二叉树,均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质,插入、搜索、删除的效率都比较高。红黑树也是实现 TreeMap 存储结构的基石。 文章相关视频...
  • 红黑树原理

    千次阅读 多人点赞 2014-04-10 10:16:28
    不过自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。这一点在我们了解了红黑树的实现原理后,就会有更加深切的体会。  红黑树和AVL树的区别在于它使用颜色来标识结点的...
  • 为什么直接采用红黑树 因为红黑树需要进行左旋,右旋操作, 而单链表不需要, 主要考察链表和红黑树对比: 1)如果元素小于8个,查询成本高,新增成本低 2)如果元素大于8个,查询成本低,新增成本高 HashMap在jdk...
  • 我们知道epoll的底层使用了红黑树来管理文件描述符,为什么会选择红黑树这种结构呢? 以下是个人理解: epoll和poll的一个很大的区别在于,poll每次调用时都会存在一个将pollfd结构体数组中的每个结构体元素从用户...
  • 红黑树简介

    2016-05-11 19:35:18
    自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。不过在我了解了红黑树的实现原理后,并不相信这是真的,关于这一点我们会在后面进行讨论。 红黑树和AVL树的区别在于它使用...
  • 原文链接 查找、插入、删除操作的最坏时间复杂度 ...平衡二叉树和红黑树是带有平衡条件的二叉查找树,故它们的效率也较高。 平衡二叉树的插入/删除操作带来的旋转操作可能会达到logn次,而红黑树的插入/.
  • 终于搞懂红黑树!--红黑树的原理及操作

    千次阅读 多人点赞 2019-07-30 15:17:04
    红黑树( Red black tree)是种自平衡二叉查找树,在计算机科学中用到的一种数据结构。 它是在1972年由 Rudolf Bayer发明的当时被称为平衡二叉B树( symmetric binary B-trees)。后来,在1978年被 Leo. guibas和 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 63,206
精华内容 25,282
关键字:

红黑树效率