红黑树 订阅
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 [1]  红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 [2]  红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 [2]  它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。 [2] 展开全文
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 [1]  红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 [2]  红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 [2]  它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。 [2]
信息
外文名
RED-BLACK-TREE
发明人
鲁道夫·贝尔
发明时间
1972年
别    名
对称二叉B树
用    途
实现关联数组 [1]
中文名
红黑树
性    质
平衡二叉查找树 [3]
学    科
计算机
红黑树简介
红黑树是一种特定类型的二叉树,它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树,则它的任一子树必为红黑树. [4]  红黑树是一种平衡二叉查找树的变体,它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉树(AVL),但 对之进行平衡的代价较低, 其平均统计性能要强于 AVL 。 [2]  由于每一颗红黑树都是一颗二叉排序树,因此,在对红黑树进行查找时,可以采用运用于普通二叉排序树上的查找算法,在查找过程中不需要颜色信息。 [5] 
收起全文
精华内容
参与话题
问答
  • 教你初步了解红黑树

    万次阅读 多人点赞 2010-12-29 18:36:00
    教你透彻了解红黑树 作者:July、saturnman 2010年12月29日本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。推荐阅读:Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, ...

                     教你初步了解黑树


     

    作者:July、saturnman   2010年12月29日

    本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。

    推荐阅读

    1. Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008,直接下载:http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
    2. 本文的github优化版:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

     

    一、红黑树的介绍

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

     

    红黑树,作为一棵二叉查找树,满足二叉查找树的一般性质。下面,来了解下 二叉查找树的一般性质。

    二叉查找树

    二叉查找树,也称有序二叉树(ordered binary tree),或已排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

    • 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    • 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    • 任意节点的左、右子树也分别为二叉查找树。
    • 没有键值相等的节点(no duplicate nodes)。

    因为一棵由n个结点随机构造的二叉查找树的高度为lgn,所以顺理成章,二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后,则这些操作最坏情况运行时间为O(n)。

    红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

    但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢?这就引出了红黑树的5个性质:

    1. 每个结点要么是红的要么是黑的。  
    2. 根结点是黑的。  
    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。  
    4. 如果一个结点是红的,那么它的两个儿子都是黑的。  
    5.  对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 

    正是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

    :上述第3、5点性质中所说的NULL结点,包括wikipedia.算法导论上所认为的叶子结点即为树尾端的NIL指针,或者说NULL结点。然百度百科以及网上一些其它博文直接说的叶结点,则易引起误会,因,此叶结点非子结点

    如下图所示,即是一颗红黑树(下图引自wikipedia:http://t.cn/hgvH1l):


    此图忽略了叶子和根部的父结点。同时,上文中我们所说的 "叶结点" 或"NULL结点",如上图所示,它不包含数据而只充当树在此结束的指示,这些节点在绘图中经常被省略,望看到此文后的读者朋友注意。 


    二、树的旋转知识

        当在对红黑树进行插入和删除等操作时,对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质,可以通过对结点进行重新着色,以及对树进行相关的旋转操作,即通过修改树中某些结点的颜色及指针结构,来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的

        树的旋转分为左旋和右旋,下面借助图来介绍一下左旋和右旋这两种操作。

    1.左旋

    如上图所示当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行,它使Y成为该子树新根,而Y的左孩子b则成为pivot的右孩子。

    LeftRoate(T, x)
    y ← x.right				       //定义y:y是x的右孩子
    x.right ← y.left	            //y的左孩子成为x的右孩子
    if y.left ≠ T.nil
        y.left.p ← x	
    y.p ← x.p				       //x的父结点成为y的父结点
    if x.p = T.nil
    	then T.root ← y
    else if x = x.p.left
    	then x.p.left ← y
    else x.p.right ← y 
    y.left ← x                       //x作为y的左孩子
    x.p ← y

    2.右旋

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

     

    树在经过左旋右旋之后,树的搜索性质保持不变树的红黑性质则被破坏了所以,红黑树插入和删除数据后,需要利用旋转颜色重涂来重新恢复树的红黑性质

        至于有些书如《STL源码剖析》有对双旋的描述,其实双旋只是单旋的两次应用,并无新的内容,因此这里就不再介绍了,而且左右旋也是相互对称的,只要理解其中一种旋转就可以了。

     

    三、红黑树的插入

    要真正理解红黑树的插入,还得先理解二叉查找树的插入。磨刀不误砍柴工,咱们再来了解下二叉查找树的插入红黑树的插入

    如果要在二叉查找树中插入一个结点,首先要查找到结点插入的位置,然后进行插入假设插入的结点为z的话,插入的伪代码如下:

    TREE-INSERT(T, z)
    y ← NIL
    x ← T.root
    while x ≠ NIL
    	do y ←  x
    	if z.key < x.key
    		then x ← x.left
    	else x ← x.right
    z.p ← y
    if y == NIL
    	then T.root ← z       
    else if z.key < y.key
    	then y.left ← z
    else y.right ← z

    红黑树的插入和插入修复

    现在我们了解了二叉查找树的插入,接下来,咱们便来具体了解红黑树的插入操作。红黑树的插入相当于在二叉查找树插入的基础上,为了重新恢复平衡,继续做了插入修复操作。

    假设插入的结点为z,红黑树的插入伪代码具体如下所示:

    RB-INSERT(T, z)
    y ← nil
    x ← T.root
    while x ≠ T.nil
    	do y ← x
    	if z.key < x.key
    		then x ← x.left
    	else x ← x.right
    z.p ← y
    if y == nil[T]
    	then T.root ← z
    else if z.key < y.key
    	then y.left ← z
    else y.right ← z
    z.left ← T.nil
    z.right ← T.nil
    z.color ← RED
    RB-INSERT-FIXUP(T, z)

    把上面这段红黑树的插入代码,跟之前看到的二叉查找树的插入代码比较一下可以看出,RB-INSERT(T, z)前面的第1~13行代码基本上就是二叉查找树的插入代码,然后第14~16行代码把z的左孩子和右孩子都赋为叶结点nil,再把z结点着为红色,最后为保证红黑性质在插入操作后依然保持,调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色,并旋转。

    换言之,如果插入的是根结点,由于原树是空树,此情况只会违反性质2因此直接把此结点涂为黑色;如果插入的结点的父结点是黑色,由于此不会违反性质2和性质4,红黑树没有被破坏,所以此时什么也不做。

    但当遇到下述3种情况时又该如何调整呢?

    • ● 插入修复情况1:如果当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色

      ● 插入修复情况2:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

      ● 插入修复情况3:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左子

    答案就是根据红黑树插入代码RB-INSERT(T, z)最后一行调用的RB-INSERT-FIXUP(Tz)函数所示的步骤进行操作,具体如下所示:

    RB-INSERT-FIXUP(T, z)
    while z.p.color == RED
    	do if z.p == z.p.p.left
    		then y ← z.p.p.right
    		if y.color == RED
    			then z.p.color ← BLACK               ▹ Case 1
    			y.color ← BLACK                    ▹ Case 1
    			z.p.p.color ← RED                    ▹ Case 1
    			z ← z.p.p                            ▹ Case 1
    		else if z == z.p.right
    			then z ← z.p                          ▹ Case 2
    			LEFT-ROTATE(T, z)                   ▹ Case 2
    		z.p.color ← BLACK                        ▹ Case 3
    		z.p.p.color ← RED                         ▹ Case 3
    		RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3
    	else (same as then clause with "right" and "left" exchanged)
    T.root.color ← BLACK

    下面,咱们来分别处理上述3种插入修复情况

    • 插入修复情况1:当前结点的父结点是红色,祖父结点的另一个子结点(叔叔结点)是红色。

    如下代码所示:

    while z.p.color == RED
    	do if z.p == z.p.p.left
    		then y ← z.p.p.right
    		if y.color == RED

    此时父结点的父结点一定存在,否则插入前就已不是红黑树。与此同时,又分为父结点是祖父结点的左孩子还是右孩子,根据对称性,我们只要解开一个方向就可以了。这里只考虑父结点为祖父左孩子的情况,如下图所示(勘误:图中15节点应改为13,特此说明,下同):

    对此,我们的解决策略是:将当前节点的父节点和叔叔节点涂黑,祖父结点涂红,把当前结点指向祖父节点,从新的当前节点重新开始算法。即如下代码所示:

    			then z.p.color ← BLACK               ▹ Case 1
    			y.color ← BLACK                    ▹ Case 1
    			z.p.p.color ← RED                    ▹ Case 1
    			z ← z.p.p                            ▹ Case 1  

    所以,变化后如下图所示

    于是,插入修复情况1转换成了插入修复情况2

    • 插入修复情况2:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

    此时,解决对策是:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。即如下代码所示:

    		else if z == z.p.right
    			then z ← z.p                          ▹ Case 2
    			LEFT-ROTATE(T, z)                   ▹ Case 2
    所以红黑树由之前的:

     

    变化成:

     

    从而插入修复情况2转换成了插入修复情况3

    • 插入修复情况3:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左孩子

    解决对策是:父节点变为黑色,祖父节点变为红色,在祖父节点为支点右旋,操作代码为:

    		z.p.color ← BLACK                        ▹ Case 3
    		z.p.p.color ← RED                         ▹ Case 3
    		RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3

    最后,把根结点涂为黑色,整棵红黑树便重新恢复了平衡。所以红黑树由之前的:

    变化成:


    回顾:经过上面情况3、情况4、情况5等3种插入修复情况的操作示意图,读者自会发现,后面的情况4、情况5都是针对情况3插入节点4以后,进行的一系列插入修复情况操作,不过,指向当前节点N指针一直在变化。所以,你可以想当然的认为:整个下来,情况3、4、5就是一个完整的插入修复情况的操作流程


    四、红黑树的删除

    接下来,咱们最后来了解,红黑树的删除操作。

    "我们删除的节点的方法与常规二叉搜索树中删除节点的方法是一样的,如果被删除的节点不是有双非空子女,则直接删除这个节点,用它的唯一子节点顶替它的位置,如果它的子节点分是空节点,那就用空节点顶替它的位置,如果它的双子全为非空,我们就把它的直接后继节点内容复制到它的位置,之后以同样的方式删除它的后继节点,它的后继节点不可能是双子非空,因此此传递过程最多只进行一次。”

    二叉查找树的删除

    继续讲解之前,补充说明下二叉树结点删除的几种情况,待删除的节点按照儿子的个数可以分为三种:

    1. 没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。
    2. 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。
    3. 有两个儿子。这是最麻烦的情况,因为你删除节点之后,还要保证满足搜索二叉树的结构。其实也比较容易,我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置,就可以保证结构的不变。当然,你要记得调整子树,毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素,其实选择右儿子的最小元素也一样,没有任何差别,只是人们习惯从左向右。这里咱们也选择左儿子的最大元素,将它放到待删结点的位置。左儿子的最大元素其实很好找,只要顺着左儿子不断的去搜索右子树就可以了,直到找到一个没有右子树的结点。那就是最大的了。

    二叉查找树的删除代码如下所示:

    TREE-DELETE(T, z)
     1  if left[z] = NIL or right[z] = NIL
     2      then y ← z
     3      else y ← TREE-SUCCESSOR(z)
     4  if left[y] ≠ NIL
     5      then x ← left[y]
     6      else x ← right[y]
     7  if x ≠ NIL
     8      then p[x] ← p[y]
     9  if p[y] = NIL
    10      then root[T] ← x
    11      else if y = left[p[y]]
    12              then left[p[y]] ← x
    13              else right[p[y]] ← x
    14  if y ≠ z
    15      then key[z] ← key[y]
    16           copy y's satellite data into z
    17  return y

    红黑树的删除和删除修复

    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 ≠ 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  

    “在删除节点后,原红黑树的性质可能被改变,如果删除的是红色节点,那么原红黑树的性质依旧保持,此时不用做修正操作,如果删除的节点是黑色节点,原红黑树的性质可能会被改变,我们要对其做修正操作。那么哪些树的性质会发生变化呢,如果删除节点不是树唯一节点,那么删除节点的那一个支的到各叶节点的黑色节点数会发生变化,此时性质5被破坏。如果被删节点的唯一非空子节点是红色,而被删节点的父节点也是红色,那么性质4被破坏。如果被删节点是根节点,而它的唯一非空子节点是红色,则删除后新根节点将变成红色,违背性质2。”

    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就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。"--saturnman。

    如果是以下情况,恢复比较简单:

    • a)当前节点是红+黑色
      解法,直接把当前节点染成黑色,结束此时红黑树性质全部恢复。
    • b)当前节点是黑+黑且是根节点, 解法:什么都不做,结束。

    但如果是以下情况呢?:

    • 删除修复情况1:当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)
    • 删除修复情况2:当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色
    • 删除修复情况3:当前节点颜色是黑+黑,兄弟节点是黑色,兄弟的左子是红色,右子是黑色
    • 删除修复情况4:当前节点颜色是黑-黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意

    此时,我们需要调用RB-DELETE-FIXUP(T, x),来恢复与保持红黑性质的工作。

    下面,咱们便来分别处理这4种删除修复情况。

    删除修复情况1:当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。

    解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况(注:变化前,原本就未违反性质5,只是为了把问题转化为兄弟节点为黑色的情况)。 即如下代码操作:

    //调用RB-DELETE-FIXUP(T, x) 的1-8行代码
     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

    变化前:

     

    变化后: 

     

    删除修复情况2:当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。

    解法:把当前节点和兄弟节点中抽取一重黑色追加到父节点上,把父节点当成新的当前节点,重新进入算法。(此变换后性质5不变),即调用RB-INSERT-FIXUP(T, z) 的第9-10行代码操作,如下:

    //调用RB-DELETE-FIXUP(T, x) 的9-11行代码
    9                if color[left[w]] = BLACK and color[right[w]] = BLACK
    10                   then color[w] ← RED                          ▹  Case 2
    11                        x p[x]                                  ▹  Case 2

    变化前

     

    变化后

     

    删除修复情况3:当前节点颜色是黑+黑,兄弟节点是黑色,兄弟的左子是红色,右子是黑色。

    解法:把兄弟结点染红,兄弟左子节点染黑,之后再在兄弟节点为支点解右旋,之后重新进入算法。此是把当前的情况转化为情况4,而性质5得以保持,即调用RB-INSERT-FIXUP(T, z) 的第12-16行代码,如下所示:

    //调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
    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

    变化前:

     

    变化后:

    删除修复情况4:当前节点颜色是黑-黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意。

    解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确,即调用RB-INSERT-FIXUP(T, z)的第17-21行代码,如下所示:

    //调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
    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

    变化前:

     

    变化后:

    最后值得一提的是上述删除修复的情况1~4都只是树的局部,并非树的整体全部,且删除修复情况3、4在经过上面的调整后,调整还没结束(还得继续调整直至重新恢复平衡,只是图并没有画出来)。
    后面会继续修改完善下本文,感谢关注,thanks。

    July、二零一四年九月十五日修订。

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

    之前在学校寝室画红黑树画了好几个钟头,贴俩张图:

      红黑树插入修复的3种情况:

     

      红黑树删除修复的4种情况:


    updated

    继续请看本文的github优化版本:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md,或看看这个PPT:http://vdisk.weibo.com/s/zrFL6OXJNfNVU。另,对应新书《编程之法:面试和算法心得》3.1节。July、二零一四年五月三日。

    展开全文
  • 最容易懂得红黑树

    万次阅读 多人点赞 2017-03-23 17:00:58
    介绍红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍微放松逛一下限制,希望找到一个能在...

    介绍

    红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍微放松逛一下限制,希望找到一个能在对数时间内完成查找的数据结构。这个时候,红黑树站了出来。
    阅读以下需要了解普通二叉树的插入以及删除操作。
    红黑树是在普通二叉树上,对没个节点添加一个颜色属性形成的,同时整个红黑二叉树需要同时满足一下五条性质
    红黑树需要满足的五条性质:
    性质一:节点是红色或者是黑色;
    在树里面的节点不是红色的就是黑色的,没有其他颜色,要不怎么叫红黑树呢,是吧。
    性质二:根节点是黑色;
    根节点总是黑色的。它不能为红。
    性质三:每个叶节点(NIL或空节点)是黑色;
    这个可能有点理解困难,可以看图:
    这里写图片描述
    这个图片就是一个红黑树,NIL节点是个空节点,并且是黑色的。
    性质四:每个红色节点的两个子节点都是黑色的(也就是说不存在两个连续的红色节点);
    就是连续的两个节点不能是连续的红色,连续的两个节点的意思就是父节点与子节点不能是连续的红色。

    **性质五:从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点;**
    还是看图:
    

    这里写图片描述
    从根节点到每一个NIL节点的路径中,都包含了相同数量的黑色节点。
    这五条性质约束了红黑树,可以通过数学证明来证明,满足这五条性质的二叉树可以将查找删除维持在对数时间内。
    当我们进行插入或者删除操作时所作的一切操作都是为了调整树使之符合这五条性质。
    下面我们先介绍两个基本操作,旋转。
    旋转的目的是将节点多的一支出让节点给另一个节点少的一支,旋转操作在插入和删除操作中经常会用到,所以要熟记。

    下面是左旋和右旋:
    左旋:
    

    这里写图片描述
    右旋:
    这里写图片描述

    下面讲讲插入

    我们先明确一下各节点的叫法
    这里写图片描述

    因为要满足红黑树的这五条性质,如果我们插入的是黑色节点,那就违反了性质五,需要进行大规模调整,如果我们插入的是红色节点,那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时,违反性质二,所以,我们把要插入的节点的颜色变成红色。

    下面是可能遇到的插入的几种状况:
    1、当插入的节点是根节点时,直接涂黑即可;
    2、当要插入的节点的父节点是黑色的时候。
    这里写图片描述
    这个时候插入一个红色的节点并没有对这五个性质产生破坏。所以直接插入不用在进行调整操作。

    3、如果要插入的节点的父节点是红色且父节点是祖父节点的左支的时候。
    这个要分两种情况,一种是叔叔节点为黑的情况,一种是叔叔节点为红的情况。
    当叔叔为黑时,也分为两种情况,一种是要插入的节点是父节点的左支,另一种是要插入的节点是父亲的右支。
    我们先看一下当要插入的节点是父节点的左支的情况:

    这里写图片描述
    这个时候违反了性质四,我们就需要进行调整操作,使之符合性质四,我们可以通过对祖父节点进行右旋同时将祖父节点和父节点的颜色进行互换,这样就变成了:
    这里写图片描述
    经过这样的调整可以符合性质四并且不对其他性质产生破坏。
    当插入的节点是父节点的右支的时候:
    这里写图片描述
    当要插入的节点是父节点的右支的时候,我们可以先对父节点进行左旋,变成如下:
    这里写图片描述
    如果我们把原先的父节点看做是新的要插入的节点,把原先要插入的节点看做是新的父节点,那就变成了当要插入的节点在父节点的左支的情况,对,是的,就是按照当要插入的节点在父节点的左支的情况进行旋转,旋转完之后变成如下:
    这里写图片描述
    4、如果要插入的节点的父节点是红色且父节点是祖父节点的右支的时候;
    这个时候的情况跟情况3所表述的情况是一个镜像,将情况3的左和右互换一下就可以了。
    5、如果要插入的节点的父节点是红色并且叔叔节点也为红色,如下:
    这里写图片描述
    这个时候,只需将父亲节点和叔叔节点涂黑,将祖父节点涂红。

    以上就是插入的全部过程。
    下面我们再讲讲删除的操作:

    首先你要了解普通二叉树的删除操作:
    1.如果删除的是叶节点,可以直接删除;
    2.如果被删除的元素有一个子节点,可以将子节点直接移到被删除元素的位置;
    3.如果有两个子节点,这时候就可以把被删除元素的右支的最小节点(被删除元素右支的最左边的节点)和被删除元素互换,我们把被删除元素右支的最左边的节点称之为后继节点(后继元素),然后在根据情况1或者情况2进行操作。如图:
    这里写图片描述
    将被删除元素与其右支的最小元素互换,变成如下图所示:

    这里写图片描述
    然后再将被删除元素删除:

    这里写图片描述

    我们下面所称的被删除元素,皆是指已经互换之后的被删除元素
    加入颜色之后,被删除元素和后继元素互换只是值得互换,并不互换颜色,这个要注意。

    下面开始讲一下红黑树删除的规则:
    1.当被删除元素为红时,对五条性质没有什么影响,直接删除。
    2.当被删除元素为黑且为根节点时,直接删除。
    3.当被删除元素为黑,且有一个右子节点为红时,将右子节点涂黑放到被删除元素的位置,如图:

    这里写图片描述
    变成
    这里写图片描述

    4.当被删除元素为黑,且兄弟节点为黑,兄弟节点两个孩子也为黑,父节点为红,此时,交换兄弟节点与父节点的颜色;NIL元素是指每个叶节点都有两个空的,颜色为黑的NIL元素,需要他的时候就可以把它看成两个黑元素,不需要的时候可以忽视他。
    如图:

    这里写图片描述
    变成:
    这里写图片描述
    5.当被删除元素为黑、并且为父节点的左支,且兄弟颜色为黑,兄弟的右支为红色,这个时候需要交换兄弟与父亲的颜色,并把父亲涂黑、兄弟的右支涂黑,并以父节点为中心左转。如图:
    由:

    这里写图片描述
    变成:

    这里写图片描述
    6.当被删除元素为黑、并且为父节点的左支,且兄弟颜色为黑,兄弟的左支为红色,这个时候需要先把兄弟与兄弟的左子节点颜色互换,进行右转,然后就变成了规则5一样了,在按照规则5进行旋转。如图:

    这里写图片描述
    先兄弟与兄弟的左子节点颜色互换,进行右转,变成:

    这里写图片描述
    然后在按照规则5进行旋转,变成:
    这里写图片描述
    7.当被删除元素为黑且为父元素的右支时,跟情况5.情况6 互为镜像。
    8.被删除元素为黑且兄弟节点为黑,兄弟节点的孩子为黑,父亲为黑,这个时候需要将兄弟节点变为红,再把父亲看做那个被删除的元素(只是看做,实际上不删除),看看父亲符和哪一条删除规则,进行处理变化如图:
    由:
    这里写图片描述
    变成:
    这里写图片描述
    8.当被删除的元素为黑,且为父元素的左支,兄弟节点为红色的时候,需要交换兄弟节点与父亲结点的颜色,以父亲结点进行左旋,就变成了情况4,在按照情况四进行操作即可,变化如下:
    由:

    这里写图片描述
    交换兄弟节点与父亲结点的颜色,以父亲结点进行左旋 变成:
    这里写图片描述
    在按照情况四进行操作,变成:
    这里写图片描述

    好了,删除的步骤也讲完,没有讲到的一点就是,在添加删除的时候,时刻要记得更改根元素的颜色为黑。
    这里并没有语言实现,只是讲了一下红黑树的插入删除步骤,你可以根据步骤自己把红黑树实现。

    点击这里,照着规则一步一步的构建一个红黑树吧。

    最后:
    1.红黑树的实现其实是一个2、3、4树,只是将双节点或者三节点用红色进行了标示,如果你将红色节点放到和它父元素相同的高度,并把它和父元素看做是一个元素,你就会发现,变成了一个高度为lgN的二叉树,这个2.3.4树对红黑树很有启发意义。
    2.上面的步骤其实可以不用死记硬背,是可以推导出来的,因为我们是把一个平衡但通过插入或者删除破坏了平衡的红黑树再次平衡,同过旋转让位,改变红黑颜色,使之符合那五条基本性质。比如遇到删除操作情况四的时候,我们可以把那个删除元素去除,发现左边比右边少一个黑元素,这个时候,怎么办,我们发现兄弟节点的子元素有一个红元素,操作这个不会影响那五条性质,所以我们通过变换颜色,旋转,即可让左右两边的的黑色数目一样。
    3.旋转操作的目的是出让一个元素到另外的地方并且符合二叉树左小右大的性质,交换颜色的目的是为了保持红黑树的那五条性质。
    4.要时刻记得 ,一切的操作都是为了保持那五条性质。

    最后的最后,其实还有一种更为简单的红黑二叉树,这个简单的红黑二叉树实际上是一个2.3树,他只允许左节点为红节点,但是性能上肯定是不如这个红黑树。这个简单的红黑二叉树在《算法》第四版有介绍,掌握完之后再看这个简单的红黑二叉树,就会觉着简单 easy。
    最后的最后的最后,一定要尝试着自己推导一下插入删除规则啊,不然经常忘,是睡一觉起来再看就有点懵逼的那种忘。

    展开全文
  • 红黑树,超强动静图详解,简单易懂

    千次阅读 多人点赞 2019-07-24 09:29:19
    红黑树,超强动静图详解,简单易懂

    写在前面

    红黑树,对很多童鞋来说,是既熟悉又陌生。学校中学过,只了解大概;工作中不怎么使用,但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。没错,本文内容就是要解决这个问题,用简单的语言,搭配静图和动图(利用大脑图形记忆方式),让你对红黑树有更深入的了解和更清晰的记忆,希望小伙伴们再次遇到红黑树的问题不至于头大,建议读该文章姿势: 打开两个页面,一个页面看图片和内容,一个页面看公式,像玩魔方一样,多玩几次就明白了

    通过工具 (公众号回复「工具」—>那些可以提高效率的工具—>红黑树) 动态感受红黑树的转换过程

    俺家司令买完东西后,我俩经常会发生这样的一段对话:

    司令:你猜我买的这个多少钱?
    我: 1000
    司令: 高了
    我: 500
    司令: 低了:
    我: 750
    … 直到最后猜中

    这样说大家应该已经猜到了是「二分查找法」,通过这个例子我想要引出的是 ,来看图片


    程序中的树其实是我们日常看到的树的倒影,或者发挥一下想象,倒影也可以是树根

    二叉查找树

    二叉查找树,Binary Search Tree 「BST」,要想了解二叉查找树,我们首先看下二叉查找树有哪些特性呢?

    1. 某节点的左子树节点值仅包含小于该节点值
    2. 某节点的右子树节点值仅包含大于该节点值
    3. 左右子树每个也必须是二叉查找树
      看个图就轻松理解上面三句话的意思了:

    上图,结合二叉查找树的三条约束来看,非常好,没有什么问题。再来看一个图,依旧符合上面三条约束,感觉有问题吗?

    1. 这是一个走路一米六,一米八的树
    2. 这是一个畸形的树,大风一挂很可能被折断的树
      从程序的角度来说这个树不够平衡,查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长

    理科生在高中学习生物时学过一个关键字「去除顶端优势」,通过去除植物顶端优势,侧芽会迅速生长,慢慢变得强壮和平衡, 红黑树其实就是去除二叉查找树顶端优势的解决方案,从而达到树的平衡

    红黑树

    红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST),树上的每个节点都遵循下面的规则:

    1. 每个节点都有红色或黑色
    2. 树的根始终是黑色的 (黑土地孕育黑树根,?)
    3. 没有两个相邻的红色节点(红色节点不能有红色父节点或红色子节点,并没有说不能出现连续的黑色节点
    4. 从节点(包括根)到其任何后代NULL节点(叶子结点下方挂的两个空节点,并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

    瞬间懵逼?了解一下印象就行,开始玩魔方都是要照着魔方公式一点点玩的,多玩几次就熟悉了。红黑树也一样,红黑树有两大操作:

    1. recolor (重新标记黑色或红色)
    2. rotation (旋转,这是树达到平衡的关键)
      我们会先尝试 recolor,如果 recolor 不能达到红黑树的 4 点要求,然后我们尝试 rotation,其实红黑树的关键玩法就是弄清楚 recolor 和 rotation 的规则,接下来看看详细的算法公式吧 千万别着急记忆公式,有图示会逐步说明,就像魔方一样,多玩几次就懂了:
      假设我们插入的新节点为 X
      1. 将新插入的节点标记为红色
      1. 如果 X 是根结点(root),则标记为黑色
      1. 如果 X 的 parent 不是黑色,同时 X 也不是 root:
      • 3.1 如果 X 的 uncle (叔叔) 是红色
        • 3.1.1 将 parent 和 uncle 标记为黑色
        • 3.1.2 将 grand parent (祖父) 标记为红色
        • 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同,然后重复步骤 2、3

    话不多说,看下图

    跟着上面的公式走:

    1. 将新插入的 X 节点标记为红色
    2. 发现 X 的 parent § 同样为红色,这违反了红黑树的第三条规则「不能有两个连续相邻的红色节点」
    3. 发现 X 的 uncle (U) 同样为红色
    4. 将 P 和 U 标记为黑色
    5. 将 X 和 X 的 grand parent (G) 标记为相同的颜色,即红色,继续重复公式 2、3
    6. 发现 G 是根结点,标记为黑色
    7. 结束

    刚刚说了 X 的 uncle 是红色的情况,接下来要说是黑色的情况

      1. 如果 X 的 parent 不是黑色,同时 X 也不是 root:
      • 3.2 如果 X 的 uncle (叔叔) 是黑色,我们要分四种情况处理
        • 3.2.1 左左 (P 是 G 的左孩子,并且 X 是 P 的左孩子)
        • 3.2.2 左右 (P 是 G 的左孩子,并且 X 是 P 的右孩子)
        • 3.2.3 右右 (和 3.2.1 镜像过来,恰好相反)
        • 3.2.4 右左 (和 3.2.2 镜像过来,恰好相反)
          当出现 uncle 是黑色的时候我们第一步要考虑的是 旋转 ,这里先请小伙伴不要关注红黑树的第 4 条规则,主要是为了演示如何旋转的,来一点点看,不要看图就慌,有解释的?:

    左左情况

    这种情况很简单,想象这是一根绳子,手提起 P 节点,然后变色即可

    左右

    左旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的左孩子,然后再应用 左左情况

    右右

    与左左情况一样,想象成一根绳子

    右左

    右旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的右孩子,然后再应用 右右情况

    你说的动图在哪里,你个大骗子,别着急,现在就为小伙伴们奉上动图演示,来说明公式的使用:

    案例一

    插入 10,20,30,15 到一个空树中

    1. 向空树中第一次插入数字 10,肯定是 root 节点

    2. root 节点标记成黑色

    3. 向树中插入新节点 20,标记为红色

    4. 20 > 10,并发现 10 没有叶子节点,将新节点 20 作为 10 的右孩子

    5. 向树中插入新节点 30,标记为红色

    6. 30 > 10,查找 10 的右子树,找到 20

    7. 30 > 20,继续查找 20 的右子树,发现 20 没有叶子节点,将值插在此处

    8. 30 和 20 节点都为红色,30 为右孩子,20 也为右孩子,触发了 右右情况

    9. 通过一次旋转,提起 20 节点

    10. 20 节点是根结点,标记为黑色

    11. 向树中插入新节点 15,标记为红色

    12. 通过比对大小和判断是否有叶子节点,最终插值为 10 节点的右孩子

    13. 15 和 10 节点都为红色,15 的 uncle 节点 30 也为红色

    14. 按照公式,将 15 的 parent 10 和 uncle 30 更改为黑色

    15. 让 15 节点 grand parent 20 的颜色与 15 节点的颜色一样,变为红色

    16. 20 为根结点,将其改为黑色

    继续插入其他节点只不过反复应用上面的公式,上面应用到的红黑树工具,可以暂停动画效果,一帧一帧的看红黑树的转换过程,这样通过练习,查看公式,观察变化三管齐下,红黑树的入门理解应该完全不再是问题了

    灵魂追问

    1. jdk 1.8 HashMap 中有使用到红黑树,你知道触发条件是什么吗?有读过源码是如何 put 和 remove 的吗?
    2. 这里讲的是红黑树的 insert,delete 又是什么规则呢?
    3. 哪些场景可以应用红黑树?
    4. 你了解各种树的时间复杂度吗?
    5. 留个小作业,应用工具将 [10 70 32 34 13 56 32 56 21 3 62 4 ] 逐个插入到树中,理解红黑树 recolor 和 rotation 的转换规则

    提高效率工具

    [center]


    推荐阅读

    只会用 git pull ?有时候你可以尝试更优雅的处理方式
    双亲委派模型:大厂高频面试题,轻松搞定
    面试还不知道BeanFactory和ApplicationContext的区别?
    如何设计好的RESTful API
    程序猿为什么要看源码?


    欢迎持续关注公众号:「日拱一兵」

    • 前沿 Java 技术干货分享
    • 高效工具汇总
    • 面试问题分析与解答
    • 技术资料领取

    后续文章会为你讲解各种时间空间复杂度,以及多线程,ElasticSearch 等问题

    以读侦探小说思维轻松趣味学习 Java 技术栈相关知识,本着将复杂问题简单化,抽象问题具体化和图形化原则逐步分解技术问题,技术持续更新,请持续关注…

    [外链图片转存失败(img-aQIhfytJ-1563931818687)(http://rgyb.sunluomeng.top/公众账号文章/感想与总结/_image/2019-06-18/a (1)].png)

    展开全文
  • ———————————— 二叉查找(BST)具备什么特性呢? ...1.左子树上所有结点的值均...下图中这棵,就是一颗典型的二叉查找: 1.查看根节点9: 2.由于10 &gt; 9,因此查看右孩子13: ...

    ————————————

    二叉查找树(BST)具备什么特性呢?

    1.左子树上所有结点的值均小于或等于它的根结点的值。

    2.右子树上所有结点的值均大于或等于它的根结点的值。

    3.左、右子树也分别为二叉排序树。

    下图中这棵树,就是一颗典型的二叉查找树:

    1.查看根节点9:

    2.由于10 > 9,因此查看右孩子13:

    3.由于10 < 13,因此查看左孩子11:

    4.由于10 < 11,因此查看左孩子10,发现10正是要查找的节点:

    假设初始的二叉查找树只有三个节点,根节点值为9,左孩子值为8,右孩子值为12:

    接下来我们依次插入如下五个节点:7,6,5,4,3。依照二叉查找树的特性,结果会变成什么样呢?

    1.节点是红色或黑色。

    2.根节点是黑色。

    3.每个叶子节点都是黑色的空节点(NIL节点)。

    4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

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

    下图中这棵树,就是一颗典型的红黑树:

    什么情况下会破坏红黑树的规则,什么情况下不会破坏规则呢?我们举两个简单的栗子:

    1.向原红黑树插入值为14的新节点:

    2.向原红黑树插入值为21的新节点:

    由于父节点22是红色节点,因此这种情况打破了红黑树的规则4(每个红色节点的两个子节点都是黑色),必须进行调整,使之重新符合红黑树的规则。

    变色:

    为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色。

    下图所表示的是红黑树的一部分,需要注意节点25并非根节点。因为节点21和节点22连续出现了红色,不符合规则4,所以把节点22从红色变成黑色:

    但这样并不算完,因为凭空多出的黑色节点打破了规则5,所以发生连锁反应,需要继续把节点25从黑色变成红色:

    此时仍然没有结束,因为节点25和节点27又形成了两个连续的红色节点,需要继续把节点27从红色变成黑色:

    左旋转:

    逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子。说起来很怪异,大家看下图:

    图中,身为右孩子的Y取代了X的位置,而X变成了自己的左孩子。此为左旋转。

    右旋转:

    顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子。大家看下图:

    图中,身为左孩子的Y取代了X的位置,而X变成了自己的右孩子。此为右旋转。

    我们以刚才插入节点21的情况为例:

    首先,我们需要做的是变色,把节点25及其下方的节点变色:

    此时节点17和节点25是连续的两个红色节点,那么把节点17变成黑色节点?恐怕不合适。这样一来不但打破了规则4,而且根据规则2(根节点是黑色),也不可能把节点13变成红色节点。

    变色已无法解决问题,我们把节点13看做X,把节点17看做Y,像刚才的示意图那样进行左旋转:

    由于根节点必须是黑色节点,所以需要变色,变色结果如下:

    这样就结束了吗?并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4,其他路径的黑色节点个数是3,不符合规则5。

    这时候我们需要把节点13看做X,节点8看做Y,像刚才的示意图那样进行右旋转:

    最后根据规则来进行变色:

    如此一来,我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂,经历了如下步骤:

    变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色

    几点说明:

    1. 关于红黑树自平衡的调整,插入和删除节点的时候都涉及到很多种Case,由于篇幅原因无法展开来一一列举,有兴趣的朋友可以参考维基百科,里面讲的非常清晰。

    2.漫画中红黑树调整过程的示例是一种比较复杂的情形,没太看明白的小伙伴也不必钻牛角尖,关键要懂得红黑树自平衡调整的主体思想。

    展开全文
  • 红黑树真的没你想的那么难

    万次阅读 2018-07-06 23:42:18
    TreeMap是红黑树的java实现,红黑树能保证增、删、查等基本操作的时间复杂度为O(lgN)。 首先我们来看一张TreeMap的继承体系图: 还是比较直观的,这里来简单说一下继承体系中不常见的接口NavigableMap和...
  • 红黑树 B树 B+树

    2020-03-10 00:53:14
    红黑树 假设1-100个数字 让你猜 根据提示告诉你打了还是小了 想到的算法肯定是二分查找 如果转成数据结构 有哪些? 二叉树 二分查找树 由一组数{0.3.4.5.6.8} 时间复杂度就是树的深度 logn 这个树经过增删操作可能...
  • 红黑树

    2020-11-15 19:58:09
    1. 二叉搜索 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。 若它的柚子不为空,则右子上所有节点的值均大于它的根节点的值。 它的左、右子也分别为二叉排序。 1.1 二叉搜索-...
  • Table of Contents 1.定义 2.性质 3.基本操作 4.功能 4.1查找 4.2 插入 4.3 删除 5.红黑树的部分实现 6.应用--map/multimap ...如上图整理所示 红黑树是一种平衡的二叉树,引入它为了解决的...
  • 浅析红黑树(RBTree)原理及实现

    万次阅读 多人点赞 2018-07-10 12:13:05
    我们在上一篇博客认识到了平衡二叉树(AVLTree),了解到AVL的性质,其实平衡二叉树最大的作用就是查找,AVL的查找、插入和删除在平均和最坏情况下都是O(logn)。AVL的效率就是高在这个地方。如果在AVL中插入或...
  • 面试常问:什么是红黑树

    万次阅读 多人点赞 2018-10-22 19:26:04
    什么是红黑树?   ———————————— 二叉查找树(BST)具备什么特性呢? 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的...
  • 红黑树详解

    千次阅读 2019-02-26 09:50:05
    title: 红黑树原理 红黑树提纲 2-3树介绍 红黑树 该博客都是读者具备二分树基础知识前提下写的(不清楚的不要看下面的内容了,看了也不会明白多少的…) 下面都统一用RBTree表示红黑树。 RBTree很多人都觉得难,...
  • 红黑树理解 - 数据结构

    千次阅读 2015-05-07 18:31:21
    红黑树  红黑树是很多平衡树的一种,保证最坏情况下基本动态几何操作时间复杂度为O(log(n))   1、红黑树性质 (1) 每个节点是红色的,或者是黑色的 (2) 根节点是黑色的 (3) 每个叶节点(nil)是黑色的 (4) 如果一...
  • 红黑树的认识总结

    万次阅读 2020-05-12 17:06:50
    备注:后续逐步增加
  • 红黑树原理详解

    万次阅读 多人点赞 2019-01-08 19:12:00
       二叉查找由于在频繁的动态更新过程中,可能会出现的高度远大于 log2n的情况,所以就会导致各个操作效率下降,最坏的情况下就会退化为链表,变为O(n).很明显,想要解决这个问题,有效的一种办法就是使得...
  • 快速理解红黑树原理

    千次阅读 2018-01-31 11:43:40
    红黑树 红黑树 其实就是一个二叉树。 常用的二叉树类型 简单说二叉树概念: 二叉树 又称度为至多二的树。 平衡二叉树 平衡二叉树又称 AVL 树 特点:一个根节点的左右个子树的高度差不超过1 平衡二叉树 ...
  • 红黑树原理解析以及Java实现

    万次阅读 多人点赞 2017-01-10 15:17:52
    2、红黑树的左旋转、右旋转、重新着色的原理与Java实现; 3、红黑树的增加结点、删除结点过程解析;1.红黑树的基本概念与数据结构表示首先红黑树来个定义: 红黑树定义:红黑树又称红-黑二叉树,它首先是一颗...
  • 浅析红黑树原理以及实现 我们在上一篇博客认识到了平衡二叉树(AVLTree),了解到平衡二叉树的性质,其实平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均 和最坏情况下都是O(logn)。AVL树的效率...
  • 红黑树(RBTree)是一种相比平衡二叉树(AVL)平衡要求较低的的一种二叉搜索树,所谓平衡要求较低的意思是相比AVL树的每个节点的左右子树的高度差不能超过2,红黑树使用红黑两种颜色来标记二叉搜索树中的节点,并对这种...
  • 福利:机械工业出版社华章公司联合当当网特意为【过往记忆大数据】用户申请了一批可与满减叠加使用的“满200减30”的图书优惠码,优惠码使用后相当于:400减230!!!优...
  • 红黑树原理详解(转)

    千次阅读 2012-08-01 21:57:50
     之所以要写这篇文章,第一个目的是为了各位朋友在查看我写的源代码之前有一个可以理解理论的文章因为红黑树还是有点难的, 如果不想搞懂理论,而直接看代码,那绝对是云里雾里,不知所云。第二个目的是我觉得网上...

空空如也

1 2 3 4 5 ... 20
收藏数 101,280
精华内容 40,512
关键字:

红黑树