精华内容
下载资源
问答
  • 红黑树的时间复杂度分析

    万次阅读 2020-04-23 11:26:29
    一、红黑树的基本属性。 红黑树的每个结点,要么是黑色,要么是红色,不可能是黄色或其它颜色。 根结点(root)一定是黑色,简称为黑头。 所有红色结点不可以直接相邻。 也即是,如果一个结点为红色,那么,它的爸爸...

    一、红黑树的基本属性。

    1. 红黑树的每个结点,要么是黑色,要么是红色
    2. 根结点(root)一定是黑色
    3. 所有红色结点不可以直接相连。 也即是,如果一个结点为红色,那么,它的爸爸或儿子,一定就是黑色,不可是红色。符合,绿帽定律。
    4. 所有空结点,都是黑色。所谓的空结点,就是当红黑树的某一个叶子结点下,没有其它结点,那么这个结点,就是空结点,用NILNULL 表示。
    5. 从任意结点出发,到其某个子结点的空结点,所经过的黑结点数量,总是相同的。(维基上的原文:Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.)

    二、基础概念。

    1、空结点,即值为NILNULL的结点,
    2、亲子结点,跟某一根结点,直接相连接的两个结点,称作亲子结点。
    3、h(x),即树的高度
    4、bh(x) , 全称是Black Height(x) ,是指结点x所在的位置的黑树的高度。听起来,有点抽象,让我们来看一张图片。以结点10为例, x = 10时, BH(x) = BH(10) = 2。这个2是怎么来的呢?从结点10开始数起(不包含起始结点),到空结点为止。5是黑色结点,NIL也是黑色结点。所以,BH(10) = 2。同理,我们再举一个例子,结点9,当 x = 9时,BH(x) = BH(9) = 1(不包含起始结点),NIL是黑色结点,所以,BH(9) = 1。现在,你应该清楚的了解了什么是BH(即黑树的高度)。

    在这里插入图片描述

    三、通过归纳法论证红黑树的时间复杂度为Olog(n)。

    通过对红黑树的大量研究,人们发现这么一个规律,以结点x为根结点的子树,至少包含,2bh(x)-1个内结点。这个规律是通过,大量的研究,总结出来的。但规律,毕竟只是规律,必须通过证明,才能确定是正确的。Loosely Speaking,我们把这种归纳出来的,需要被证明的规律,称为引理。把经过证明的引理,称为定理。接下来,让我们来证明这个引理。在证明的过程,我们依据由简入繁的思路,步步为营。

    引理:结点x的子树至少包含2bh(x)-1个内结点。

    证明过程:

    1. 首先,我们来证明一种比较简单的情况,即h(x) = 0 。当结点x包含的子结点为0时,这个结点一定是空结点NIL。而且,空结点的黑树高度,也必然为0(结点本身不计数),即当h(x) =0时,bh(x) = 0也必然成立。因为上述的描述是必然正确的(不信者,可自代实数以验之),所以,如果引理是正确的,引理一定会满足以上的条件,让我们将这种情况,代入到引理中:

      当h(x) = bh(x) = 0 时,2bh(x) - 1 = 2h(x) - 1 = 20 - 1 = 1 - 1 = 0。综上所述,当h(x) = bh(x) = 0 时,引理是正确的。

    2. 接下来,我们证明h(x) > 0的情况。当h(x) > 0时,意味着结点x一定是个叶子结点,每一个叶子结点,都拥有左右两棵子树(或空结点)。 那么,结点x的左右子树两边的黑高,要么是bh(x),要么是bh(x)-1。这取决于,结点x的亲子结点的颜色。如果亲子结点是红色,就是bh(x)-1。如果是黑色,即是bh(x)。因为如果是亲子结点是红色的,不计入黑高。根据归纳法,每一个子树至少包含(2bh(x)-1 - 1) 个结点。所以,结点x至少包含,左树结点 + 右树结点 + x结点本身,个结点

      综上所述,我们可以得到如下公式:(2bh(x)-1 - 1) + (2bh(x)-1 - 1) + 1 = 2bh(x) - 1。其中,第一个括号代表左子树,第二个代表右子树,最后的+1代表结点x本身。

    3. 根据1和2的论证,我们可以知道,某个结点x,至少会包含 2bh(x) -1 个结点。我们设总结点数为N,则 N ≥ 2bh(x)-1。 接下来就是变形的过程:

      已知,N ≥ 2bh(x)-1
      所以, N + 1 ≥ 2bh(x)
      所以,log2(N +1) ≥ bh(x)

    4. 根据红黑树的第三个属性,红色结点不可以直接相邻。所以,从某一个根结点到其任意一个空结点NIL的任意路径上(这句话的意思是指h(x),即树的高度),黑色结点的数量(这句指的是bh(x)),至少包含一半及以上。即,bh(x) ≥ h(x)/2。 让我们把这句,代入论述3里面的公式,可得:

      log2(N +1) ≥ bh(x) ≥ h(x)/2,
      两边同时,乘以2,得 2log2(N+1) ≥ h(x)。
      所以,h(x) ≤ 2log2(N+1)。
      因为,当N+1趋于无限大时,2log2(N+1)与lg(N),只相差一个常数。
      所以,h(x) ≤ 2log2(N+1),等价于h(x) ≤ lg(N),也等价于log(N)。
      也即是,Olog(N)或Olog(n)。

    【看不懂为什么,log2(N)==lg(N)==log(N)的,可以查看,博文最底部的注1】

    四、总结。

    学习红黑树的复杂度,需要了解算法、红黑树、对数函数、指数函数和数学归纳法的一些基本概念。其中任何知识点的不熟悉,都会对整个论证过程,造成障碍。最后,感谢各位的阅读,要是还有什么疑问,可以留言提出。


    【注1】:

    这里为什么要,强调或是O(lgn)呢?因为在算法领域,当log的底数固定,且n趋于无限大时,两者的结果都是一个常数,只是两者存在一个倍数差而已。所以,在研究算法时,这底数是可以忽略掉。打比方说:O(n+100000),我们会简单的看成O(n),一样的道理。这表达的是一种极限思维。不理解这点的,可以再私聊我详聊,这里不再赘述。


    【参考资料】

    1、维基百科-红黑树。
    2、Red-Black Trees。

    展开全文
  • 排序二叉树是一种特殊结构的二叉树,可以非常方便地对中所有节点进行排序和检索。 排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树: ? 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值...

     

    1 排序二叉树

    排序二叉树是一种特殊结构的二叉树,可以非常方便地对树中所有节点进行排序检索。 排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树: ? 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; ? 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值; ? 它的左、右子树也分别为排序二叉树。 下图显示了一棵排序二叉树:

     

    对排序二叉树,若按中序遍历就可以得到由小到大的有序序列。中序遍历得: {2,3,4,8,9,9,10,13,15,18} 排序二叉树虽然可以快速检索,但在最坏的情况下:如果插入的节点集本身就是有序的,要么是由小到大排列,要么是由大到小排列,那么最后得到的排序二叉树将变成链表:所有节点只有左节点(如果插入节点集本身是大到小排列);或所有节点只有右节点(如果插入节点集本身是小到大排列)。在这种情况下,排序二叉树就变成了普通链表,其检索效率就会很差

    2 红黑树

    《算法导论》关于红黑树的定义:

    正如在CLRS中定义的那样(CLRS指的是就是算法导论这本书《Introduction to Algorithms》,CLRS是该书作者Cormen, Leiserson, Rivest and Stein的首字母缩写),一棵红黑树是指一棵满足下述性质的二叉搜索树(BST, binary search tree):

    1. 每个结点或者为黑色或者为红色。

    2. 根结点为黑色。

    3. 每个叶结点(实际上就是NULL指针)都是黑色的。

    4. 如果一个结点是红色的,那么它的两个子节点都是黑色的(也就是说,不能有两个相邻的红色结点)。

    5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。

    数据项只能存储在内部结点中(internal node)。我们所指的"叶结点"在其父结点中可能仅仅用一个NULL指针表示,但是将它也看作一个实际的结点有助于描述红黑树的插入与删除算法,叶结点一律为黑色。 定义详解: 根据性质 5:红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点,因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度(black-height)”。 性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3 的红黑树:从根节点到叶节点的最短路径长度是 2,该路径上全是黑色节点(黑节点 – 黑节点 – 黑节点)。最长路径也只可能为 4,在每个黑色节点之间插入一个红色节点(黑节点 – 红节点 – 黑节点 – 红节点 – 黑节点),性质 4 保证绝不可能插入更多的红色节点。由此可见,红黑树中最长路径就是一条红黑交替的路径。 根据定义我们做如下练习: -不符合定义的一颗非红黑树: 红黑树的这5个性质中,第3点是比较难理解的,但它却非常有必要。我们看图1中的左边这张图,如果不使用黑哨兵,它完全满足红黑树性质,结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后(如图1右图中的小黑圆点),叶结点的个数变为8个黑哨兵,根结点50到这8个叶结点路径上的黑高度就不一样了,所以它并不是一棵红黑树。 -两颗正确的红黑树:  定理

    一棵拥有n个内部结点的红黑树的树高h<=2log(n+1)

    由此我们可以得出结论:对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 * (N-1)。 提示:排序二叉树的深度直接影响了检索的性能,正如前面指出,当插入节点本身就是由小到大排列时,排序二叉树将变成一个链表,这种排序二叉树的检索性能最低:N 个节点的二叉树深度就是 N-1。 红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的情况。 由于红黑树只是一个特殊的排序二叉树,因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同,只是红黑树保持了大致平衡,因此检索性能比排序二叉树要好很多。 但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征,因此插入操作和删除操作都需要进行一定的维护,以保证插入节点、删除节点后的树依然是红黑树。

    3 红黑树和AVL树的比较

    1.  红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。
     
    红黑树能够以 O(log n) 的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构,能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。 红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高
     
    当然,红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,做一个哈希表,性能可能会更好一些。
     
    红黑树是一个更高效的检索二叉树,因此常常用来实现关联数组。典型地,JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。
     
    IBM DevelopWorks 上一篇文章讲解非常好,供参考。
     
    TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员,其中 TreeMap 是 Map 接口的常用实现类,而 TreeSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同,但 TreeSet 底层是通过 TreeMap 来实现的,因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。
     
    对于 TreeMap 而言,由于它底层采用一棵“红黑树”来保存集合中的 Entry,这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低:当 TreeMap 添加元素时,需要通过循环找到新增 Entry 的插入位置,因此比较耗性能;当从 TreeMap 中取出元素时,需要通过循环才能找到合适的 Entry,也比较耗性能。
     
    但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于:TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态,TreeSet 中所有元素总是根据指定排序规则保持有序状态。
     
    AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
    引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.
     
    AVL树的定义:
    一棵AVL树满足以下的条件:
    1>它的左子树和右子树都是AVL树
    2>左子树和右子树的高度差不能超过1
    性质:
    1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)
    2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
    3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).
    为了保证平衡,AVL树中的每个结点都有一个平衡因子(balance factor,以下用BF表示),它表示这个结点的左、右子树的高度差,也就是左子树的高度减去右子树的高度的结果值。AVL树上所有结点的BF值只能是-1、0、1。反之,只要二叉树上一个结点的BF的绝对值大于1,则该二叉树就不是平衡二叉树。下图演示了平衡二叉树和非平衡二叉树。
     
    从1这点来看红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。 此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高.
     
     
     

    转载于:https://www.cnblogs.com/aspirant/p/7190554.html

    展开全文
  • 红黑树插入删除

    2019-04-09 10:43:31
    1、红黑树介绍 (1)二叉查找树 二叉查找树,也称有序二叉树(orderedbinarytree),或已排序二叉树(sortedbinarytree),是指一棵空树或者具有下列性质的二叉树: 若任意节点的左子树不空,则左子树上所有结点...

    本文转载于:https://blog.csdn.net/v_JULY_v/article/details/6105630

    1、红黑树介绍

    (1)二叉查找树

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

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

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

    (2)红黑树

        红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢?这就引出了红黑树的5个性质:

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

        正是红黑树的这5条性质,对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。如下图为一颗红黑树:

                           

    2、红黑树的插入

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

    (1)如果插入的是根结点,由于原树是空树,此情况只会违反性质2,因此直接把此结点涂为黑色;

    (2)如果插入的结点的父结点是黑色,由于此不会违反性质2和性质4,红黑树没有被破坏,所以此时什么也不做;

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

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

        

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

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

        此时,解决对策是:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。

        

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

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

        解决对策是:父节点变为黑色,祖父节点变为红色,在祖父节点为支点右旋,最后,把根结点涂为黑色,整棵红黑树便重新恢复了平衡。

                                      

                             

    3、红黑树的删除

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

        我们从被删节点后来顶替它的那个节点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的节点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父节点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。

    (1)当前节点是红+黑色,解法:直接把当前节点染成黑色,结束,此时红黑树性质全部恢复;

    (2)当前节点是黑+黑且是根节点, 解法:什么都不做,结束;

    (3)删除修复情况1:当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑):
        解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况(注:变化前,原本就未违反性质5,只是为了把问题转化为兄弟节点为黑色的情况)。

       

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

       

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

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

    (6)删除修复情况4:当前节点颜色是黑-黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意:
    解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确:

      

    参考:https://blog.csdn.net/v_JULY_v/article/details/6105630

    展开全文
  • 红黑树插入删除原理

    千次阅读 2014-10-04 11:00:01
    红黑树本质是一颗二叉查找树,增加了着色以及相关的性质,使得红黑树的查找,插入删除的时间复杂度最坏为O(log n)。 一、红黑树相对二叉查找树来说,有以下五个性质。 a.红黑树的节点不是红色就是黑色 b.红黑树...

    红黑树本质是一颗二叉查找树,增加了着色以及相关的性质,使得红黑树的查找,插入,删除的时间复杂度最坏为O(log n)。

     

    一、红黑树相对二叉查找树来说,有以下五个性质。

    a.红黑树的节点不是红色就是黑色

    b.红黑树中根节点必是黑色。

    c.红黑树上的节点时红色,它的两个子节点必须是黑色

    d.树中任意一个节点到叶子结点的路径上的黑色节点数目相同

    f.每个叶子节点都是黑色

     

    二、理解左旋与右旋

       当对红黑树进行删除或者是插入工作时,为了保证树的平衡与性质,必须要对红黑树进行调整,调整时可能需要进行旋转操作。通过对节点的着色以及树的旋转操作,来对红黑树进行插入或者是删除节点等操作。当父节点颜色为红色,需要通过旋转或者是颜色改变来维护红黑树的性质。

    1.左旋,以下是左旋转的C++源码(来源于STL源码剖析)


    inline void _rb_tree_rotate_left(_rb_tree_node_base*x,_rb_tree_node_base*&root)

    {    

    x为旋转点

        _rb_tree_node_base*y=x->right;//令y为旋转点的右节点

        x->right=y->left;

        if(y->left!=0)

        {

           y->left->parent=x;//设定父节点

        }

        //令y完全顶替x的地位

        y->parent=x->parent;

        if(x==root)    //如果x为根节点

            root=y;

        else if(x==x->parent->left)//如果x为其父节点的左节点

            x->parent->left=y;

        else                               //如果x为父节点的右节点

            x->parent->left=y;

            y->left=x;

            x->parent=y;

    }

    2.右旋,以下是右旋转的C++源码(来源于STL源码剖析)


    inline void _rb_tree_rotate_left(_rb_tree_node_base*x,_rb_tree_node_base*&root)

    {

        x为旋转点

        _rb_tree_node_base*y=x->left;//令y为旋转点的右节点

        x->left=y->right;

        if(y->right!=0)

        {

           y->right->parent=x;//设定父节点

        }

        //令y完全顶替x的地位

        y->parent=x->parent;

        if(x==root)    //如果x为根节点

            root=y;

        else if(x==x->parent->lright)//如果x为其父节点的左节点

            x->parent->right=y;

        else                               //如果x为父节点的右节点

            x->parent->left=y;

            y->right=x;

            x->parent=y;

    }

    如果用到双旋转,只是左旋和右旋转的结合应用,这里不一一细描述。树在经过左旋右旋之后,树的搜索性质保持不变,但树的红黑性质则被破坏了,所以,红黑树插入和删除数据后,需要利用旋转与颜色重涂来重新恢复树的红黑性质。

     

    三、红黑树的插入节点

    通过红黑树的性质的分析,插入节点会产生四种不同的典型情况,分析以下图RB-Tree分别插入3,8,35,75根据二叉查找树的规则,我们分别得到以下图的插入位置,我们发现它们都破坏了红黑树的规则,我们必须调整树形,也就是旋转树形以及改变节点颜色。(以下灰色为红色,深色为黑色)。


    以上1.2.3.4为四种不符合红黑树的四种情况,破外了红黑树的性质,我们必须通过旋转树或者是调整节点颜色。为了方便定义,让我们首先为了这些特殊节点定义一些代名,以下讨论将沿用这些代名。假设新节点为X,其父节点为P,祖父节点为G,伯父节点(父亲之兄弟节点)为S,曾祖父节点为GG,现在根据二叉查找树的规则,新节点必然是叶节点。根据红黑树规则4,X必为红色。若P为红色(这就违反了规则3,必须调整树形)则G为黑色(原为RB-tree,必须遵循规则3)。于是,根据X的插入位置以及外围的节点(S和GG)的颜色,有四种以下典型情况。

    1.S为黑且X为外侧插入。对此情况,我们队P,G做了一次但旋转,并更改P,G颜色,即可重新满足红黑树的规则3。见下图


    注意,此时可能产生不平衡状态(高度相差为1以上)。例如图中A和B为null,D或者E不为NULL。这倒是没关系,因为RB-Tree的平衡性本来就比AVL-tree弱。然而RB-tree通常能够导致良好的平衡状态。是的,经验告诉我们,RB-tree的搜索平均效率和AVL-tree几乎相等。

    2.S为黑且X为内侧插入。对此情况,我们必须先对P,X做一次单旋转并更改G,X颜色,再将结果对G做一次单旋转,即可在此满足红黑树规则3.


    3.S为红色X为外侧插入。对此情况。我们先对P和G做一次单旋转,并改变X的颜色。此时如果GG为黑,一切搞定,但如果GG为红色,则问题如4状况。


    4.S为红色X为外侧插入,对此情况,先对P和G做一次单旋转,并改变X的颜色。此时如果GG亦为红色,还要持续往上做,直到不再有父子连续并为红色的情况。

     

    四、红黑树的删除

    红黑树是一种特殊的二叉查找树,其删除结点首先要按二叉查找树删除结点的算法进行

    (一).普通二叉查找树删除一个结点:

    (1)待删除结点没有子结点,即它是一个叶子结点,此时直接删除

    (2)待删除结点只有一个子结点,则可以直接删除;如果待删除结点是根结点,则它的子结点变为根结点;如果待删除结点不是根结点,则用它的子结点替代它的位置。

    (3)待删除结点有两个子结点,首先找出该结点的后继结点(即右子树中数值最小的那个结点),然后将两个结点进行值交换(即:只交换两个结点的数值,不改变结点的颜色)并将待删除结点删除,由于后继结点不可能有左子结点,对调后的待删除结点也不会有左子结点,因此要把它删除的操作会落入情况(1)或情况(2)中。

    (二)红黑树的删除结点算法

    1.待删除结点有两个外部结点,操作如下:

    (1)直接把该结点调整为叶结点

    (2)若该结点是红色,则可直接删除,不影响红黑树的性质,算法结束  

    (3)若该结点是黑色,则删除后红黑树不平衡。此时要进行“双黑”操作         

     记该结点为V,则删除了V后,从根结点到V的所有子孙叶结点的路径将会比树中其他的从根结点到叶结点的路径拥有更少的黑色结点,破坏了红黑树性质4。此时,用“双黑”结点来表示从根结点到这个“双黑”结点的所有子孙叶结点的路径上都缺少一个黑色结点。  
    双黑含义:该结点需要代表两个黑色结点,才能维持树的平衡


    2.待删除结点有一个外部结点

    操作为:该节点是黑色,其非空子节点为红色 ;则将其子节点提升到该结点位置,颜色变黑

    3.“双黑”结点的处理

    分三种情况:

    (1)双黑色结点的兄弟结点是黑色,且子结点有红色结点

    (2)双黑结点的兄弟结点是黑色,且有两个黑色结点

    (3)双黑结点的兄弟结点是红色结点

    (1)双黑结点的兄弟结点是黑色,且子结点有红色结点

    A种情况:双黑结点远侄子结点(双黑结点若为左孩子,则双黑结点的兄弟结点的右孩子为远侄子结点;同理,处理双黑结点为右孩子)为红色,如图2

    处理方法:把兄弟结点染为双黑结点的父亲结点的颜色,把兄弟结点的右孩子染为黑色,再把父结点染为黑色;然后针对父结点进行一次左旋转,如图3 。


    B种情况:双黑结点近侄子结点(双黑结点若为左孩子,则双黑结点的兄弟结点的左孩子为近侄子结点;同理,处理双黑结点为右孩子)为红,如图4

    处理方法:针对双黑结点的兄弟做一次右旋转,结果使双黑结点的近侄子成为双黑结点新的兄弟;将新兄弟结点着为双黑结点的父结点的颜色,父结点着为黑色,再针对父做一次左旋转,如图5


    (2)双黑结点的兄弟结点是黑色,且有两个黑色结点,如图6

    处理方法:把双黑结点的兄弟结点着为红色,双黑结点的父结点着为黑色;若父结点原来为红色,则算法结束;若父结点原来黑色,则将父结点作为双黑结点,继续调整,如图7


    (3)双黑结点的兄弟结点是红色结点,如图8

    处理方法:单旋转为情况1或情况2,并改变双黑结点的兄弟结点的颜色及父结点的颜色(如图9)


    文章参考了侯捷的《STL源码剖析》以及参考了 http://gengning938.blog.163.com/blog/static/1282253812011420103852696/

    展开全文
  • 红黑树的查找时间复杂度O(logn)

    千次阅读 2020-09-25 14:07:58
    红黑树查找时间复杂度 如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n),近似于折半查找。如果二叉排序树完全不平衡,则其深度可达到n,查找效率为O(n),退化为顺序查找。一般...
  • 红黑树插入删除

    千次阅读 2016-05-26 15:09:52
    红黑树和AVL树类似,都是在进行插入删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。红黑树可以在O(log n)时间内完成查找,插入删除操作。 二叉搜索树可以看 二叉搜索树 AVL树可以看 ...
  • 不论是数组、链表还是二叉树、二叉排序树(搜索树)、红黑树,我们要找到其中特定的一个元素,方法只有一个那就是挨个比较直到找到为止,这就造成了查找的时间复杂度总是与N有关系。 数组 链表 二叉树 ...
  • 红黑树的引入是对AVL树的一种性能上的提升,使删除操作的时间复杂度也可在常数时间内完成。 外部节点 与B树一样,在末端节点处增加外部节点。可以说,红黑树在一定意义上是满二叉树。 规则: (1) 树根结点必须是...
  • 红黑树的时间复杂度为: O(lgn)下面通过“数学归纳法”对红黑树的时间复杂度进行证明。 定理:一棵含有n个节点的红黑树的高度至多为2log(n+1). 证明: "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题...
  • 【算法导论】红黑树详解之一(插入)

    万次阅读 多人点赞 2015-01-14 11:11:47
    红黑树是建立在二叉查找树的基础之上的,关于二叉查找树可以参看【算法导论】二叉搜索树的插入删除和【算法导论】二叉树的前中后序非递归遍历实现。对于高度为h的二叉查找树而言,它的SEARCH、INSERT、DELETE、...
  • 一、红黑树(Red Black Tree)删除操作 B树中,最后真正被删除的元素都在叶子节点中 1、删除 – RED节点 直接删除,不用作任何调整 2、删除 – BLACK节点 有 3 种情况 ①、拥有 2 个RED 子节点的BLACK 节点 ✓ 不...
  • 红黑树插入删除详解

    万次阅读 多人点赞 2018-07-11 15:54:05
    红黑树插入删除操作的介绍转载自:红黑树 练习题转载自:红黑树练习 R-B Tree简介  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,...
  • 红黑树插入删除、查找算法学习

    千次阅读 2015-11-11 19:53:19
    红黑树(red-black tree)是许多“平衡”搜索树中的一种,可以保证在最坏情况下基本动态集合操作的时间复杂度为O(lgn),文章讲述红黑树的性质,结构描述,插入删除算法分析,最后完成一个C语言测试程序。
  • java面试 –红黑树 红黑树性质 红黑树是一种自平衡二叉树,在平衡二叉树的基础上每个节点又增加了一个颜色的属性,节点的颜色只能是红色或黑色。具有以下性质: (1)节点要么是红色,要么是黑色, (2)根节点...
  • 3.红黑树 4.二叉查找树 5.替罪羊树 1. AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入删除在平均和最坏情况下都是O(log ...
  • 1.红黑树简介 2.红黑树的性质 3.红黑树操作 3.1 旋转操作 3.2 插入 3.2.1 情况一 3.2.2 情况二 3.2.3 情况三 3.2.4 情况四 3.2.5 情况五 3.2.6 插入总结 3.3 删除 3.3.1 情况一 3.3.2 情况二 3.3.2 ...
  • 红黑树算法探索笔记

    2018-05-04 13:24:38
    本次代码的实现请点击:红黑树实现代码 – gist红黑树基础知识定义红黑树是带有 color 属性的二叉搜索树,color 的值为红色或黑色,因此叫做红黑树。对红黑树的每个结点的结构体定义如下:struct RBNode { int ...
  • 看了很多材料,关于红黑树删除,大概所有的总结都大同小异,今天先聊聊对红黑树删除的情况分析: 红黑树删除操作 1:节点命名约定 D表示要被删除的节点。即:取 Delete 的首字母; P 表示父节点。即:取 ...
  • 红黑树

    2019-05-01 22:07:23
    红黑树 https://zhuanlan.zhihu.com/p/24367771 https://www.cnblogs.com/skywang12345/p/3245399.html(这里面有错误,但有一些内容可以参考) 红黑树的特性: (1)每个节点或者是黑色,或者是红色。 (2)根节点是...
  • AVL的查找、删除插入,并写了测试程序测试程序的正确性
  • 红黑树插入删除操作

    千次阅读 2016-09-26 15:42:51
     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。 红黑树的特性: (1)每个节点或者是黑色,或者是红色...
  • 时间复杂度:O(log(n))红黑树有如下4个性质: 1).没个结点不是红色就是黑色; 2).根结点是黑色的; 3).每个红色结点的父亲是黑色的; 4).根结点到达每个叶子结点的路径中黑色结点的个数是一样的;那么,为什么...
  • 红黑树 插入算法(一)

    千次阅读 2020-03-31 00:54:16
    红黑树在数据结构里面,是一种能自动平衡的树,它的查询速度很快,因为能够用到二分法,二分法的查询复杂度只有O(log2(N)),几万条的数据也就只需查十几次,不过要维持那么高的查询速度也是有代价,它的添加和删除节点都...
  • 这些规则使红黑树保证了一种平衡,插入删除、查找的最坏时间复杂度都为 O(logn)。它的统计性能要好于平衡二叉树(AVL树),这也正解释了红黑树为什么使用这么广的原因。 红黑树的5个特性: 每个结点要么是红色,...
  • 本文的思维导图解决了红黑树全部插入删除问题,包含详细操作原理,各种情况的对比和原因 思维导图源文件已经发布在我的资源当中,有需要的可以去 我的主页 了解更多计算机学科的精品思维导图整理 本文可以转载,但...
  • 红黑树 查找 O(h) O(lgn) 查最大/小元素 O(h) O(lgn) 前驱/后继 O(h) O(lgn) 插入 O(h) O(lgn) 删除 O(h)
  • 哈希表: 哈希表存储的是键值对,其查找的时间哈希复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的,因此...红黑树和B+树都是二叉树,插入都是O(lgn)没错 ...
  • **红黑树**实际也是一种二叉搜索树,只是它的节点不是通过平衡因子来控制树的形状,而是为节点设置了两种颜色来控制,使得树中**最长路径中节点个数不会超过最短路径节点个数的两倍**,这样就能保证树触发旋转的几率...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,535
精华内容 11,814
关键字:

红黑树插入删除复杂度