精华内容
下载资源
问答
  • 红黑树时间复杂度证明(O(lgn))

    万次阅读 2019-03-18 13:05:40
    通过“数学归纳法”对红黑树的时间复杂度O(lgn)进行证明 红黑树的时间复杂度为O(lgn),当且仅当"节点数为n的一棵红黑树的高度满足O(lgn)的要求" 证明如下: 图片内容截取自博客:...

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

    红黑树的时间复杂度为O(lgn),当且仅当"节点数为n的一棵红黑树的高度满足O(lgn)的要求"

    证明如下:

    图片内容截取自博客:http://www.cnblogs.com/skywang12345/p/3245399.html

    下面通过数学归纳法,证明高度为h的红黑树,其包含的内节点个数至少为2^(bh(x)) -1

    1. 当 h = 0:
      内节点个数为0,bh(x) = 0,原命题显然成立
    2. 当 h > 0,且树的高度为h-1,其黑色高度至少为bh(x) - 1,所以该树包含的内节点个数至少为2^(bh(x)-1) -1.
    3. 当h > 0,且树的高度为h时,
      对于节点X的左右子树,其黑色高度为bh(x)或者bh(x) - 1
      根据(2)已知:X的左右子树,即为高度h-1的节点,其包含的内节点至少为2^(bh(x)-1) -1。
      因此:节点X包含的节点数至少为:2*(2^(bh(x)-1) -1) + 1 = 2^(bh(x)) -1
      所以原命题成立,证毕
    展开全文
  • 红黑树时间复杂度为什么是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)

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

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

    红黑树查找时间复杂度

    如果二叉排序树是平衡的,则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树)搜索效率要低一些。

    展开全文
  • 这里红黑树默认是 以2为底数 数据增大n倍 耗时增大 logn倍 ————————————————欢迎大家批评或鼓励——————————————————————

    这里红黑树默认是 以2为底数

    数据增大n倍 耗时增大 logn倍

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    ————————————————欢迎大家批评或鼓励——————————————————————

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

    万次阅读 2020-04-23 11:26:29
    一、红黑树的基本属性。 红黑树的每个结点,要么是黑色,要么是红色,不可能是黄色或其它颜色。 根结点(root)一定是黑色,简称为黑头。 所有红色结点不可以直接相邻。 也即是,如果一个结点为红色,那么,它的爸爸...
  • 数据结构 在C ++中实现数组,双链表,二进制堆和红黑树,并比较它们的时间复杂度
  • 红黑树复杂度证明

    千次阅读 2018-08-17 09:29:09
    证明:红黑树复杂度为O(logn),其中n为节点个数。    只需证定理:一棵有n个节点的红黑树高度h至多为2log(n+1)  h =&lt; 2log(n+1)  只需证:高度为h的红黑树,包含的节点的数至少为2^(h/2)-1    n =&...
  • 红黑树的基本性质 节点要么是红色,要么是黑色。 根节点是黑色 每一个叶子节点(最后的空节点) 是黑色的 每个红节点的两个孩子节点都是黑的 从任意节点到叶子节点 ,结果的黑色节点是一样多的 根节点为什么是黑色...
  • 排序二叉树是一种特殊结构的二叉树,可以非常方便地对中所有节点进行排序和检索。 排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树: ? 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值...
  • 红黑树的插入和遍历时间复杂度分析    在平常的工作中,最常用的一种数据结构恐怕是std::map了。因此对其的时间复杂度分析是有必要的,编写程序时做到心中有底。   一、理论分析  在stl中std::map和std::set都...
  • 红黑树算法探索笔记

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

    2020-03-22 18:44:11
    还有构建一棵节点个数为 n 的红黑树,时间复杂度是多少?红黑树与哈希表在不同应该场景的选择?红黑树有哪些性质?红黑树各种操作的时间复杂度是多少? ...
  • 红黑树的插入与删除

    千次阅读 2016-05-26 15:09:52
    红黑树(Red Black Tree) 是一种自平衡二叉查找树。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。红黑树可以在O(log n)时间内完成查找,插入和删除...
  • 3.红黑树 4.二叉查找树 5.替罪羊树 1. AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log ...
  • 红黑树复杂度的数学证明

    千次阅读 2014-03-08 14:21:23
    红黑树的时间复杂度为: O(lgn) 下面通过“数学归纳法”对红黑树的时间复杂度进行证明。 定理:一棵含有n个节点的红黑树的高度至多为2log(n+1). 证明:  "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否...
  • 包含n个内部节点的红黑树的高度是 O(log(n))。 定义: h(v) = 以节点v为根的子树的高度。bh(v) = 从v到子树中任何叶子的黑色节点的数目(如果v是黑色则不计数它)(也叫做黑色高度)。 引理: 以节点v为根的...
  • 平衡二叉树与红黑树

    千次阅读 2019-08-19 17:37:43
    平衡二叉树与红黑树一、红黑树的性质:二、红黑树的主要用途,和其他树的比较:三、运用场景 一、红黑树的性质:    红黑树是一颗二叉搜索树,通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束,红黑...
  • 红黑树与平衡二叉树

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

    千次阅读 2014-10-04 11:00:01
    红黑树本质是一颗二叉查找树,增加了着色以及相关的性质,使得红黑树的查找,插入,删除的时间复杂度最坏为O(log n)。 一、红黑树相对二叉查找树来说,有以下五个性质。 a.红黑树的节点不是红色就是黑色 b.红黑树...
  • 红黑树 查找 O(h) O(lgn) 查最大/小元素 O(h) O(lgn) 前驱/后继 O(h) O(lgn) 插入 O(h) O(lgn) 删除 O(h)
  • 红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内...
  • 红黑树的引入是对AVL树的一种性能上的提升,使删除操作的时间复杂度也可在常数时间内完成。 外部节点 与B树一样,在末端节点处增加外部节点。可以说,红黑树在一定意义上是满二叉树。 规则: (1) 树根结点必须是...
  • 红黑树的时间复杂度为: O(lgn)下面通过“数学归纳法”对红黑树的时间复杂度进行证明。 定理:一棵含有n个节点的红黑树的高度至多为2log(n+1). 证明: "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题...
  • 粗略推到,不一定对,大家参考 这些树的发展历程好像是:二叉树 → val树→ 红黑树→ B树→ B+树 关键在于将B树/B+树 简化成M路查找树:
  • 看了很多材料,关于红黑树的删除,大概所有的总结都大同小异,今天先聊聊对红黑树删除的情况分析: 红黑树的删除操作 1:节点命名约定 D表示要被删除的节点。即:取 Delete 的首字母; P 表示父节点。即:取 ...
  • B树和B+树 红黑树

    千次阅读 2018-09-14 11:32:41
    首先,B的创建就是为了优化数据库查找,如果采用二叉查找(时间复杂度只要LogN)来进行查找,那么在磁盘进行I/O操作时,(数据太大需要进行分页)每个磁盘页对应一个节点;最坏情况:查找次数等于输的高度(时间...
  • 红黑树 vs 最小堆

    2020-02-01 15:10:43
    红黑树插入是最坏情况要比较2logN次(最高的高度)外加不超过两次旋转,最小堆最坏情况是logN次 红黑树删除不需要比较只需要不超过3旋转,查找最小值需要遍历logN,如果删除最小值树调整一般很小 最小堆查询顶节点...
  • B树(B-树)与B+树与红黑树

    千次阅读 2018-10-03 10:25:17
    B是为实现高效的磁盘存取而设计的多叉平衡搜索。这个概念在文件系统,数据库系统中非常重要。当然,有关于B的产生,发展,结构等等方面的介绍已经非常详细,所以本文只是介绍有关于B和B+最核心的知识点,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,651
精华内容 18,260
关键字:

红黑树查询复杂度