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

    万次阅读 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。

    展开全文
  • 红黑树时间复杂度为: O(lgn)下面通过“数学归纳法”对红黑树时间复杂度进行证明。 定理:一棵含有n个节点的红黑树的高度至多为2log(n+1). 证明: "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题...

    红黑树的时间复杂度为: O(lgn)
    下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

    定理:一棵含有n个节点的红黑树的高度至多为2log(n+1).

    证明:
        "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题是 "高度为h的红黑树,它的包含的内节点个数至少为 2h/2-1个"。
        我们只需要证明逆否命题,即可证明原命题为真;即只需证明 "高度为h的红黑树,它的包含的内节点个数至少为 2h/2-1个"。

        从某个节点x出发(不包括该节点)到达一个叶节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)。关于bh(x)有两点需要说明: 
        第1点:根据红黑树的"特性(5) ,即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知,从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着,bh(x)的值是唯一的
        第2点:根据红黑色的"特性(4),即如果一个节点是红色的,则它的子节点必须是黑色的"可知,从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点,则可以得出结论"bh(x) >= h/2"。进而,我们只需证明 "高度为h的红黑树,它的包含的黑节点个数至少为 2bh(x)-1个"即可。

        到这里,我们将需要证明的定理已经由
    "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 
        转变成只需要证明
    "高度为h的红黑树,它的包含的内节点个数至少为 2bh(x)-1个"。


    下面通过"数学归纳法"开始论证高度为h的红黑树,它的包含的内节点个数至少为 2bh(x)-1个"。

    (01) 当树的高度h=0时,
        内节点个数是0,bh(x) 为0,2bh(x)-1 也为 0。显然,原命题成立。

    (02) 当h>0,且树的高度为 h-1 时,它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的!

        下面,由树的高度为 h-1 的已知条件推出“树的高度为 h 时,它所包含的节点树为 2bh(x)-1”。

        当树的高度为 h 时,
        对于节点x(x为根节点),其黑高度为bh(x)。
        对于节点x的左右子树,它们黑高度为 bh(x) 或者 bh(x)-1。
        根据(02)的已知条件,我们已知 "x的左右子树,即高度为 h-1 的节点,它包含的节点至少为 2bh(x)-1-1 个";

        所以,节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。
        因此,原命题成立。

        由(01)、(02)得出,"高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。
        因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

     

    转载于:https://www.cnblogs.com/rcpalc/p/4055709.html

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

     

    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

    展开全文
  • 红黑树插入和遍历时间复杂度分析    在平常的工作中,最常用的一种数据结构恐怕是std::map了。因此对其的时间复杂度分析是有必要的,编写程序时做到心中有底。   一、理论分析  在stl中std::map和std::set都...

    红黑树的插入和遍历时间复杂度分析

     

           在平常的工作中,最常用的一种数据结构恐怕是std::map了。因此对其的时间复杂度分析是有必要的,编写程序时做到心中有底。

     

    一、理论分析

           在stl中std::map和std::set都采用红黑树的方式实现。我们知道插入一个元素到红黑树的时间为log(N),其中N为当前红黑树的元素个数,因此,采用插入方式构建元素个数为N的红黑树的时间复杂度为:

                  log(1) + log(2) + log(N-1) = log((N-1)!) = Nlog(N)

     

           那么采用迭代器遍历一棵红黑树的时间复杂度是多少呢? 是O(N)。 也就是说非递归遍历一棵红黑树的时间复杂度和遍历数组的时间复杂度是一样的,多么令人惊奇的结果。

           我们将分析得出这一结果。采用迭代器遍历红黑树的算法主要在迭代器增1操作:

     

    1.       判断右子树是不是空,如果不为空,找到右子树的最小值begin(right(tree)),结束。如果右子树为空,如果右子树为空,转2;

    2.       往根节点爬,直到父节点为空或者本节点是父节点的左子节点,然后取父节点的值。

     

    我们将证明红黑树的一条边最多被访问两次:一条边最多只能被从父节点到子节点访问一次和从子节点到父节点访问一次。如果有第三次访问,注意到我们的遍历过程是完全无状态的(步骤1和2判断的唯一是根据当前节点,没有任何其余状态变量)。那么必然会导致至少一个访问的重复,与现实矛盾。证明出一条边最多被访问两次。另外一条边最小要被访问一次,原因是很显然的。因此二叉树的遍历是O(E)的,其中E为树的边数,我们知道一个节点的节点数和边数的关系为N = E + 1,故得出迭代器遍历一棵红黑树的时间复杂度是O(N)。

     

    二、实验证明

     

           空口无凭,下面采用程序测试理论是否和实际相符。采用std::set<int>做为实验对象,对其分别插入和遍历10000、100000、1000000和10000000次,得到的时间消耗如下表:

     

    单位/微秒

     

    插入

    遍历

    10000次

    9070

    111

    100000次

    611655

    2641

    1000000次

    1575464

    26836

    10000000次

    12621089

    251810

     

    从遍历的时间消耗很容易看出遍历是线性时间的,并且对于比较小的遍历次数,遍历消耗的时间还会减小。

    但插入的时间消耗甚至小于线性时间(亚线性?)这可能与插入的数据有关吧,插入的数据是从0开始增1的,结果还有待分析。


    附录:

    测试程序环境

    系统:Windows 7。

    开发工具:VS208,Release编译。

    程序:

     

    #include <set>

    #include <boost/chrono.hpp>

    #include <iostream>

     

    void test(const int N)

    {

        std::cout << "N = " << N << std::endl;

        std::set<intsi;

        boost::chrono::high_resolution_clock::time_point t1 = boost::chrono::high_resolution_clock::now();

        for (int i = 0; i < Ni++)

        {

            si.insert(i);

        }

        boost::chrono::high_resolution_clock::time_point t2 = boost::chrono::high_resolution_clock::now();

        for (std::set<int>::iterator i = si.begin(); i != si.end(); ++i)

        {

            volatile int j = *i;

        }

        boost::chrono::high_resolution_clock::time_point t3 = boost::chrono::high_resolution_clock::now();

        std::cout << "insert time elapse " << boost::chrono::duration_cast<boost::chrono::microseconds>(t2 - t1) << std::endl;

        std::cout << "traverse time elapse " << boost::chrono::duration_cast<boost::chrono::microseconds>(t3 - t2) << std::endl;

    }

     

    int _tmain(int argc_TCHARargv[])

    {

        test(10000);

        test(100000);

        test(1000000);

        test(10000000);

         return 0;

    }

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

    千次阅读 2020-09-25 14:07:58
    红黑树查找时间复杂度 如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n),近似于折半查找。如果二叉排序树完全不平衡,则其深度可达到n,查找效率为O(n),退化为顺序查找。一般...
  • 不论是数组、链表还是二叉树、二叉排序树(搜索树)、红黑树,我们要找到其中特定的一个元素,方法只有一个那就是挨个比较直到找到为止,这就造成了查找的时间复杂度总是与N有关系。 数组 链表 二叉树 ...
  • 3.红黑树 4.二叉查找树 5.替罪羊树 1. AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log ...
  • 粗略推到,不一定对,大家参考 这些树的发展历程好像是:二叉树 → val树→ 红黑树→ B树→ B+树 关键在于将B树/B+树 简化成M路查找树:
  • 红黑树插入和删除原理

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

    万次阅读 多人点赞 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语言测试程序。
  • 时间复杂度:O(log(n))红黑树有如下4个性质: 1).没个结点不是红色就是黑色; 2).根结点是黑色的; 3).每个红色结点的父亲是黑色的; 4).根结点到达每个叶子结点的路径中黑色结点的个数是一样的;那么,为什么...
  • 红黑树 查找 O(h) O(lgn) 查最大/小元素 O(h) O(lgn) 前驱/后继 O(h) O(lgn) 插入 O(h) O(lgn) 删除 O(h)
  • 红黑树 插入算法(一)

    千次阅读 2020-03-31 00:54:16
    红黑树在数据结构里面,是一种能自动平衡的树,它的查询速度很快,因为能够用到二分法,二分法的查询复杂度只有O(log2(N)),几万条的数据也就只需查十几次,不过要维持那么高的查询速度也是有代价,它的添加和删除节点都...
  • 红黑树插入删除操作

    千次阅读 2016-09-26 15:42:51
     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。 红黑树的特性: (1)每个节点或者是黑色,或者是红色...
  • 引言:  目前国内图书市场上,抑或网上讲解红黑树的资料... 而我们知道,即便在经典的算法导论一书上,也没有把所有的插入、删除情况一一道尽,直接导致了不少读者的迷惑,而我的红黑树系列第4篇文章:一步一图一代
  • 红黑树插入

    千次阅读 2018-07-12 23:36:18
    本篇目录****************************************************************** 红黑树的概念及性质 ******** 利用图示法介绍红黑树插入是怎么实现的 ********************...
  • 红黑树插入与删除

    2018-08-06 16:49:16
    下面对在左子树插入(删除)进行说明,在右子树插入(删除)则是在左子树时的镜像映射。   插入:N节点为插入的节点 时间复杂度为:O(N) ①插入的点的父节点是黑色 插入后,仍然符合红黑树的...
  • 哈希表: 哈希表存储的是键值对,其查找的时间哈希复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的,因此...红黑树和B+树都是二叉树,插入都是O(lgn)没错 ...
  • 红黑树插入删除归类

    千次阅读 2012-04-03 09:10:29
    原创地址文中有,不加注。     ...介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonida
  • 我们知道一颗高度为h的二叉搜索树,可以支持任何一种基本动态集合操作,且其时间复杂度均为O(h)。...而红黑树(red-black- tree)是许多“平衡的”查找树中的一种,可以保证在最坏情况下基本动态集合。
  • 本文的思维导图解决了红黑树全部插入和删除问题,包含详细操作原理,各种情况的对比和原因 思维导图源文件已经发布在我的资源当中,有需要的可以去 我的主页 了解更多计算机学科的精品思维导图整理 本文可以转载,但...
  • 红黑树插入和删除

    2017-08-02 20:04:38
    上一章讲述了红黑树得相关性质,我们了解到红黑树确实是平衡二叉树,在时间复杂度为O(lg(n)),比二叉搜索树性能更好,性能变好的前提是算法更加复杂了,下面讲述红黑树插入和删除操作,希望对大家有所帮助。...
  • 哈希表的插入时间复杂度平均O(1),最好O(1),最差O(n)。 排序链表的插入时间复杂度平均O(n),最好O(1),最差O(n)。 数组的查询时间复杂度平均O(n),最好O(1),最差O(n)...红黑树时间复杂度平均O(logn),最好O(logn),最差O(l
  • 红黑树插入算法

    千次阅读 2009-03-26 16:11:00
    满足下面几个条件的二叉搜索树,称为红黑树:1. 任何一个节点都被着色――红色或是黑色。2. 根节点是黑色的。3. 所有的NIL节点都看成黑色(NIL节点是就是一个假想的或是无实在意义的节点,所有应该指向NULL的指针...
  • 红黑树 - 插入

    2020-11-04 09:10:01
    红黑树是许多"平衡"搜索树的一种,可以保证在最坏情况下基本动态操作集合的时间复杂度为O(lgn); 1、红黑树的性质 以上节选自《算法导论<第三版>》; 首先可以看到,红黑树是一颗二叉搜索树,那就...
  • 高效实现红黑树插入引言: 红黑树是一种特殊的二叉排序树,像java,c++的关联数组,如map都是用红黑树实现。 为什么红黑树应用比原生的二叉排序树(BST)和高度平衡二叉树(AVL)要更为广泛? 答:BST的深度...
  • 红黑树插入操作超详解

    千次阅读 2012-04-30 18:35:08
    下述图片多参照网上资源(July红黑树)或者电子书资源(STL源码剖析)等  2. 个人感觉STL中思路以及实现方式比其他版本都易懂,建议大家好好琢磨 参考:   1.STL源码剖析  2. ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,581
精华内容 14,232
关键字:

红黑树插入时间复杂度