精华内容
下载资源
问答
  • 红黑树时间复杂度为什么是O(logn)?

    千次阅读 2019-12-07 11:49:10
    一、红黑树性质 结点必须是红色或者黑色。 根节点必须是黑色。...接下来我们将通过“数学归纳法”对红黑树的时间复杂度进行证明,保证让您看得明明白白! 首先我们要知道O(logn)中的n是指红黑树节...

    一、红黑树性质

    1. 结点必须是红色或者黑色。
    2. 根节点必须是黑色。
    3. 叶节点(NIL)必须是黑色(NIL节点无数据,是空节点)。
    4. 如果一个节点是红色的,则它的子节点必须是黑色的。
    5. 从任一节点出发到其每个叶子节点的路径,黑色节点的数量必须相等。

    二、时间复杂度证明

    接下来我们将通过“数学归纳法”对红黑树的时间复杂度进行证明,保证让您看得明明白白!

    首先我们要知道O(logn)中的n是指红黑树节点个数。

    已知一条关于红黑树的定理:一棵有n个节点的红黑树高度h至多为2log(n+1)。(h <= 2log(n+1)

    只要证明这条定理成立,时间复杂度也就成立的(因为红黑树查询的时间复杂度其实就是从根节点开始往下查询,最大查询时间也就是到叶节点终止,即为树的高度),接下来就来证明这条定理。

    1. h <= 2log(n+1)可推出n >= 2^(h/2)-1。得出定理的逆否命题是 "高度为h的红黑树,它包含的节点个数至少为 2^(h/2)-1个"。我们只需证明逆否命题为真,即证明了原命题为真。
    2. 从某个节点x出发(不包括该节点)到达一个叶节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)
    3. 根据性质五可知,从节点x出发到达所有的叶节点都具有相同数目的黑节点。这也就意味着,bh(x)的值是唯一的
    4. 根据性质四可知,从节点x出发到达叶节点"所经历的黑节点数目">= "所经历的红节点的数目"(画个红黑树数数就理解了)。假设x是根节点,则可以得出结论"h/2 <= bh(x) < h" (h=黑高度+红高度)。
    5. 因此接下来只需证明"高度为h的红黑树,它包含的节点个数至少为 2^bh(x)-1个"。(n >= 2^bh(x)-1)

    下面通过"数学归纳法"论证n >= 2^bh(x)-1:

    • 当bh(x)=0时,节点数n(b) = 2^(0)-1 = 0,原命题成立;
    • 当bh(x)=k时,假设该树至少有2^bh(x)-1 = 2^k-1个节点;
    • 当bh(x)=k+1时,根节点的两棵子树的黑高度肯定都为k(根据性质二和性质五),则两棵子树上的节点个数和至少为2*(2^bh(x)-1) = 2^(k+1)-2,那么该树共有2^(k+1)-2+1(加上根节点) = 2^(k+1)-1个节点,与右式相等,原命题成立。

    因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)” => 红黑树时间复杂度为O(logn)

    展开全文
  • 红黑树的时间复杂度分析

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

    展开全文
  • 红黑树插入和遍历时间复杂度分析    在平常的工作中,最常用的一种数据结构恐怕是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;

    }

    展开全文
  • 不论是数组、链表还是二叉树、二叉排序树(搜索树)、红黑树,我们要找到其中特定的一个元素,方法只有一个那就是挨个比较直到找到为止,这就造成了查找的时间复杂度总是与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
    展开全文
  • 红黑树插入与删除

    千次阅读 2016-05-26 15:09:52
    红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。红黑树可以在O(log n)时间内完成查找,插入和删除操作。 二叉搜索树可以看 二叉搜索树 AVL树可以看 ...
  • 红黑树的查找时间复杂度O(logn)

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

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

    万次阅读 多人点赞 2015-01-14 11:11:47
    红黑树是建立在二叉查找树的基础之上的,关于二叉查找树可以参看【算法导论】二叉搜索树的插入和删除和【算法导论】二叉树的前中后序非递归遍历实现。对于高度为h的二叉查找树而言,它的SEARCH、INSERT、DELETE、...
  • 排序二叉树是一种特殊结构的二叉树,可以非常方便地对中所有节点进行排序和检索。 排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树: ? 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值...
  • 红黑树插入和删除

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

    2018-05-04 13:24:38
    本次代码的实现请点击:红黑树实现代码 – gist红黑树基础知识定义红黑树是带有 color 属性的二叉搜索树,color 的值为红色或黑色,因此叫做红黑树。对红黑树的每个结点的结构体定义如下:struct RBNode { int ...
  • 红黑树插入

    千次阅读 2018-07-12 23:36:18
    本篇目录****************************************************************** 红黑树的概念及性质 ******** 利用图示法介绍红黑树插入是怎么实现的 ********************...
  • 红黑树的引入是对AVL树的一种性能上的提升,使删除操作的时间复杂度也可在常数时间内完成。 外部节点 与B树一样,在末端节点处增加外部节点。可以说,红黑树在一定意义上是满二叉树。 规则: (1) 树根结点必须是...
  • 红黑树

    2020-03-22 18:44:11
    所以,最后的答案是,平衡树是为了解决二叉查找树退化为链表的情况,而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。 不过,红黑树还有挺多其他的知识点可以考,例如红黑树有哪些应用场景?向集合...
  • 红黑树插入删除详解

    万次阅读 多人点赞 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).根结点到达每个叶子结点的路径中黑色结点的个数是一样的;那么,为什么...
  • 红黑树 插入算法(一)

    千次阅读 2020-03-31 00:54:16
    红黑树在数据结构里面,是一种能自动平衡的树,它的查询速度很快,因为能够用到二分法,二分法的查询复杂度只有O(log2(N)),几万条的数据也就只需查十几次,不过要维持那么高的查询速度也是有代价,它的添加和删除节点都...
  • 3.红黑树 4.二叉查找树 5.替罪羊树 1. AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log ...
  • 红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内...
  • 不平凡的二叉弱平衡搜索树)3、红黑树的特性4、红黑树的属性介绍5、红黑树插入代码解析1、没有根节点(直接插入)2、父节点黑色、叔节点任意(直接插入)3、父节点红、叔节点黑(LL、LR、RL、RR)1、LL旋转2、LR...
  • 超详细图解红黑树插入操作过程

    千次阅读 2020-04-07 16:33:00
    红黑树的定义与性质、插入过程、修复方法等
  • 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 ...
  • **红黑树**实际也是一种二叉搜索树,只是它的节点不是通过平衡因子来控制树的形状,而是为节点设置了两种颜色来控制,使得树中**最长路径中节点个数不会超过最短路径节点个数的两倍**,这样就能保证树触发旋转的几率...
  • 平衡二叉树与红黑树

    千次阅读 2019-08-19 17:37:43
    平衡二叉树与红黑树一、红黑树的性质:二、红黑树的主要用途,和其他树的比较:三、运用场景 一、红黑树的性质:    红黑树是一颗二叉搜索树,通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束,红黑...
  • 红黑树的一些基本概念 在讲TreeMap前还是先说一下红黑树的一些基本概念,这样可以更好地理解之后TreeMap的源代码。 二叉查找树是在生成的时候是非常容易失衡的,造成的最坏情况就是一边倒(即只有左子树/右子树)...
  • 红黑树的时间复杂度为: O(lgn)下面通过“数学归纳法”对红黑树的时间复杂度进行证明。 定理:一棵含有n个节点的红黑树的高度至多为2log(n+1). 证明: "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题...
  • 红黑树与平衡二叉树

    千次阅读 2018-09-07 09:44:52
    1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。 2、平衡二叉树追求绝对平衡,条件比较苛刻,实现...

空空如也

空空如也

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

红黑树插入复杂度