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

    万次阅读 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(logn)

    千次阅读 2020-03-22 17:50:44
    如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n),近似于折半查找。如果二叉排序树完全不...红黑树并不是一个完美平衡二叉查找树,根结点的左子树如果比右子树高,但左子树和...

    红黑树查找时间复杂度


    如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n),近似于折半查找。如果二叉排序树完全不平衡,则其深度可达到n,查找效率为O(n),退化为顺序查找。一般的,二叉排序树的查找性能在O(Log2n)到O(n)之间。因此,为了获得较好的查找性能,就要构造一棵平衡的二叉排序树。
    红黑树并不是一个完美平衡二叉查找树,根结点的左子树如果比右子树高,但左子树和右子树的黑结点的层数是相等的,也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点。所以我们叫红黑树这种平衡为黑色完美平衡。
    红黑树的主要目的是实现一种平衡二叉树,这样可以达到最优的查询性能,时间复杂度为(O(logn)、 n为数据个数。
    红黑树查找,因为红黑树是一颗二叉平衡树,并且查找不会破坏树的平衡,所以查找跟二叉平衡树的查找无异。正由于红黑树总保持黑色完美平衡,所以它的查找最坏时间复杂度为O(2lgN),也即整颗树刚好红黑相隔的时候,能有这么好的查找效率得益于红黑树自平衡的特性。
    红黑树插入操作包括两部分工作:一查找插入的位置;二插入后自平衡。
    红黑树的删除操作也包括两部分工作:一查找目标结点;而删除后自平衡。
    网上有很多使用数学归纳法来计算红黑树时间复杂度的证明了,这里就不再赘述。我们可以简单思考一下,对于一棵普通的平衡二叉搜索树来说,它的搜索时间复杂度为O(logn),而作为红黑树,存在着最坏的情况,也就是查找的过程中,经过的节点全都是原来2-3树(读作二三树)里的3-节点,导致路径延长两倍,时间复杂度为O(2logn),由于时间复杂度的计算可以忽略系数,因此红黑树的搜索时间复杂度依然是O(logn),当然,由于这个系数的存在,在实际使用中,红黑树会比普通的平衡二叉树(AVL树)搜索效率要低一些。

    展开全文
  • 不论是数组、链表还是二叉树、二叉排序树(搜索树)、红黑树,我们要找到其中特定的一个元素,方法只有一个那就是挨个比较直到找到为止,这就造成了查找时间复杂度总是与N有关系。 数组 链表 二叉树 ...

    查找时间复杂度

    不论是数组、链表还是二叉树、二叉排序树(搜索树)、红黑树,我们要找到其中特定的一个元素,方法只有一个那就是挨个比较直到找到为止,这就造成了查找的时间复杂度总是与N有关系。

    数组链表二叉树二叉排序树红黑树
    查找O(N)O(N)O(N)O(log2N)~O(N)O(log2N)
    • 数组:特指无序数组。假设数组中有N个元素,我们要找到其中一个特定的元素,通常要进过N/2次比较,所以时间复杂度上来说还是O(N)。如果数组是有序数组的话,可以折半查找,此时的时间复杂度是O(log2N)。

    • 链表:同理于数组,假设有N个元素,要找到其中一个特定的元素,时间复杂度还是O(N)。

    • 二叉树:注意是二叉树,父节点与左子节点、右子节点之间没有大小关系,实在不明白,可以看看这篇文章二叉树(从建树、遍历到存储)Java。此时要从N个节点中找到特定的节点,只能是遍历每一个元素,时间复杂度是O(N)。

    • 二叉排序树:此时父节点与左、右子节点之间就有大小关系了。在理想状态下即节点分布均匀的情况下相当于折半查找,所以时间复杂度是O(log2N),最坏情况是出现左、右斜树,此时时间复杂度会降到O(N),一般情况下时间复杂度会介于两者之间即O(N)到O(log2N)。

    • 红黑树:虽然红黑树在插入、删除操作上很是麻烦,但是对于查找操作跟二叉排序树是一模一样的,因为红黑树不过是加了平衡算法的二叉排序树而已,二叉排序树最基本的父节点与左、右子节点之间的大小关系肯定是满足的,所以时间复杂度是O(log2N)。

    只看表达式的可能感觉不强烈,那我们假设N=1000000(一百万)。

    数组链表二叉树二叉排序树红黑树
    查找1000000(一百万)1000000(一百万)1000000(一百万)20~100000020

    注意:有人可能会说,二叉排序树这个跨度也太大了吧,直接从二十到一百万,嗯嗯,这也是为什么要用红黑树的原因,想好好理解红黑树的,可以看看这篇文章关于红黑树,这篇文章你要看啊


    增加时间复杂度

    数组链表二叉排序树红黑树
    增加O(1)O(N)O(log2N)~O(N)O(log2N)
    • 数组: 与数组元素的个数N没有关系,总是存放到下一个空白的存储空间,array[index],之后index++。

    • 链表:对于链表要分情况(1)在表头插入,只需要改变几个引用值,所以时间复杂度为O(1);
      (2)在指定位置插入一个元素,比如add(int index , E element )。此时增加节点的操作就分为两步,第一步查找,第二步新增,因为查找的时间复杂度是O(N),新增的时间复杂度是O(1),所以还是O(N)。

    • 二叉树排序树: 新增一个节点需要分为两步,第一步查找(成为谁的子节点?);第二步新增。
      新增只需要改变几个引用,时间复杂度是O(1),主要的时间消耗还是在查找上,所以总的时间复杂度跟二叉排序树的查找一样是要看树节点的分布情况的,一般情况下是O(log2N)~O(N)。

    • 红黑树: 同理新增一个节点需要分为两步,第一步查找(成为谁的子节点?)时间复杂度为O(log2N) ;第二步新增,新增过程中为满足平衡而做的颜色变换和旋转所消耗的时间有以下结论(引自经典著作《Java数据结构与算法(第二版)》[美]Robert Lafore 著)。

    插入和删除的时间要增加一个常数因子,因为不得不在下行的路径上和插入点执行颜色变换和旋转。平均起来,一次插入大约需要一次旋转。因此,插入的时间复杂度还是O(log2N) 。

    为对比强烈,我们还是以N = 1000000(一百万)为例,感受一下不同数据结构的魅力。

    数组链表二叉排序树红黑树
    增加11000000(一百万)20~100000020

    删除时间复杂度

    数组链表二叉树二叉排序树红黑树
    删除O(N)O(N)O(N)O(log2N)~O(N)O(log2N)
    • 数组:删除操作也分为两步,第一步找到指定元素,第二步指定元素后的每一个元素前移一位。
      在元素个数为N的数组中查找指定元素平均需要N/2次比较,时间复杂度为O(N);将指定元素后的每一个元素前移一位,平均需要移动N/2个元素,时间复杂度为O(N)。总的时间复杂度还是O(N)。

    • 链表:删除节点的操作就分为两步,第一步查找,第二步删除。因为查找的时间复杂度是O(N),删除的时间复杂度是O(1),所以还是O(N)。

    • 二叉树: 删除节点的操作就分为两步,第一步查找,第二步删除。因为二叉树的父节点与左右子节点之间没有大小关系,要查找指定节点只能挨个比较,时间复杂度为O(N),删除只需要修改一些引用,时间复杂度是常数级的,总的时间消耗O(N)。

    • 二叉排序树红黑树: 两者的删除操作都分为两步,一步查找、二步删除。且删除节点的时间复杂度总是常数级的(只用改变几个引用),所以总的时间复杂度就是查找的时间复杂度。

    为对比强烈,我们再以N = 1000000(一百万)为例,感受一下这差距。。。

    数组链表二叉树二叉排序树红黑树
    删除1000000(一百万)1000000(一百万)1000000(一百万)20~100000020
    展开全文
  • 排序二叉树是一种特殊结构的二叉树,可以非常方便地对中所有节点进行排序和检索。 排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树: ? 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值...

     

    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

    展开全文
  • 红黑树时间复杂度为什么是O(logn)?

    千次阅读 2019-12-07 11:49:10
    一、红黑树性质 结点必须是红色或者黑色。 根节点必须是黑色。...接下来我们将通过“数学归纳法”对红黑树时间复杂度进行证明,保证让您看得明明白白! 首先我们要知道O(logn)中的n是指红黑树节...
  • 3.红黑树 4.二叉查找树 5.替罪羊树 1. AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log ...
  • 红黑树 查找 O(h) O(lgn) 查最大/小元素 O(h) O(lgn) 前驱/后继 O(h) O(lgn) 插入 O(h) O(lgn) 删除 O(h)
  • 红黑树时间复杂度为: O(lgn)下面通过“数学归纳法”对红黑树时间复杂度进行证明。 定理:一棵含有n个节点的红黑树的高度至多为2log(n+1). 证明: "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题...
  • 红黑树的插入和遍历时间复杂度分析    在平常的工作中,最常用的一种数据结构恐怕是std::map了。因此对其的时间复杂度分析是有必要的,编写程序时做到心中有底。   一、理论分析  在stl中std::map和std::set都...
  • 红黑树的引入是对AVL树的一种性能上的提升,使删除操作的时间复杂度也可在常数时间内完成。 外部节点 与B树一样,在末端节点处增加外部节点。可以说,红黑树在一定意义上是满二叉树。 规则: (1) 树根结点必须是...
  • 这个问题问的是查找时间复杂度,考察的是HashMap底层数据的存储,我们直到java8之后,HashMap的存储结构为数组+链表+红黑树。所以结合HashMap的存储结构来进行回答。 问题回答 理想情况下,哈希不冲突,可以...
  • 在二叉搜索树的插入和删除操作都必须先查找查找的效率代表了二叉搜索树中各个操作的性能 这种情况是最优的情况下,并不代表二叉搜索树的时间复杂度 在构建二叉搜索树时,如果插入元素有序...AVL树 和 红黑树 ...
  • 红黑树的插入与删除

    千次阅读 2016-05-26 15:09:52
    红黑树可以在O(log n)时间内完成查找,插入和删除操作。 二叉搜索树可以看 二叉搜索树 AVL树可以看 AVL树的插入与删除 1. 红黑树的性质 红黑树的自平衡依赖于它的以下性质: 性质1. 结点是红
  • 红黑树插入和删除原理

    千次阅读 2014-10-04 11:00:01
    红黑树本质是一颗二叉查找树,增加了着色以及相关的性质,使得红黑树查找,插入,删除的时间复杂度最坏为O(log n)。 一、红黑树相对二叉查找树来说,有以下五个性质。 a.红黑树的节点不是红色就是黑色 b.红黑树...
  • 这个问题问的是查找时间复杂度,考察的是HashMap底层数据的存储,我们直到java8之后,HashMap的存储结构为数组+链表+红黑树。所以结合HashMap的存储结构来进行回答。 问题回答 理想情况下,哈希不冲突,可以...
  • 红黑树

    2020-03-22 18:44:11
    还有构建一棵节点个数为 n 的红黑树时间复杂度是多少?红黑树与哈希表在不同应该场景的选择?红黑树有哪些性质?红黑树各种操作的时间复杂度是多少? ...
  • 时间复杂度:O(n) int SequenceSearch(int arr[], int value, int n) { int i; for(i = 0; i < n; i++) if(arr[i] == value) return i; return -1; } 二、二分查找(折半查找) 条件:有序数组 原理: 查找...
  • 几种查找时间复杂度

    千次阅读 2020-04-03 22:32:20
    时间复杂度为:O(1) (2)最坏情况:最后一个是要查找的元素。时间复杂度未:O(n) (3)平均情况下就是:(n+1)/2。 所以总的来说时间复杂度为:O(n) 2、二分查找:O(log2n)->log以2为底n的对数 解释:2^t = n; ...
  • AVL查找、删除、插入,并写了测试程序测试程序的正确性
  • 红黑树查找

    2020-09-09 09:05:40
    红黑树是基于二叉平衡搜索树的数据结构为基础,在基于红黑树结构的查找并不会破坏树的平衡,所以查找跟二叉平衡树的查找是一样的。 二 红黑树查找步骤 从根结点开始查找,把根结点设置为当前结点。 如果当前...
  • 红黑树的插入和删除

    2019-04-09 10:43:31
    1、红黑树介绍 (1)二叉查找树 二叉查找树,也称有序二叉树(orderedbinarytree),或已排序二叉树(sortedbinarytree),是指一棵空树或者具有下列性质的二叉树: 若任意节点的左子树不空,则左子树上所有结点...
  • 哈希表存储的是键值对,其查找时间哈希复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的,因此哈希表的插入,删除,查找都是O(1) 二叉树: 红黑树和B+树都是...
  • 根据百度百科给出的定义,它们之间的关系可以用下图表示,平衡二叉树(平衡二叉查找树,AVL)和红黑树都是二叉查找树的一种,区别就是平衡二叉树严格平衡,红黑树是弱平衡。 而AVL树由于实现比较复杂,而且插入和...
  • 在大量数据中常用的查找数据的做法有四类:顺序查找,二分查找,二叉树查找(BST),红黑树查找(RBT)。 这四类查找方法分别对应着四种基本思想原理: 顺序查找 —— 无序简单查找 二分查找 —— 有序查找,...
  • 最近发现了个好东西,就是一个学算法的好东西,是网易公开课的一个视频。 直通车 这是麻省理工学院的公开课,...因为在学校上课的时候没听明白,太官方了,而且课下也没钻研时间复杂度这个事,所以一直云里雾里的...
  • 算法复杂度算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。(算法的复杂性体现在运行该算法时的计算机所需资源的...
  • 【算法导论】红黑树详解之一(插入)

    万次阅读 多人点赞 2015-01-14 11:11:47
    红黑树是建立在二叉...对于高度为h的二叉查找树而言,它的SEARCH、INSERT、DELETE、MINIMUM、MAXIMUM等操作的时间复杂度均为O(h)。所以在二叉查找树的高度较高时,上述操作会比较费时,而红黑树就可以解决这种问题。
  • 字典树,又称Trie树,是一种专门用于字符串匹配的树形结构,能够高效的在一组字符串中寻找所求字符串,与红黑树,散列表类似,但是又有其优势。 如何构造一颗Trie树 假设我们有一组字符串:abc,adf,adrf,siab。...
  • 在数据量较小的情况下,采用链表可以获得较高的性能(查询时为O(n)),在数据量较大的情况下,链表的检索性能会下降,这时使用二叉树(Binary Tree)进行存储,查询时时间复杂度为O(logn)。 下面为二叉树的示意图: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,158
精华内容 14,463
关键字:

红黑树查找的时间复杂度