精华内容
下载资源
问答
  • 二叉树 红黑树 B树 B+树的优缺点

    千次阅读 2021-04-09 09:47:58
    本文将从最普通的二叉查找开始,逐步说明各种解决的问题以及面临的新问题,从而说明MySQL为什么选择B+作为索引结构。 一、二叉查找(BST):不平衡 二叉查找(BST,Binary Search Tree),也叫二叉排序,...

    前言

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明MySQL为什么选择B+树作为索引结构。

    一、二叉查找树(BST):不平衡

    二叉查找树(BST,Binary Search Tree),也叫二叉排序树,在二叉树的基础上需要满足:任意节点的左子树上所有节点值不大于根节点的值,任意节点的右子树上所有节点值不小于根节点的值。如下是一颗BST(图片来源)。

     

     

    当需要快速查找时,将数据存储在BST是一种常见的选择,因为此时查询时间取决于树高,平均时间复杂度是O(lgn)。然而,BST可能长歪而变得不平衡,如下图所示(图片来源),此时BST退化为链表,时间复杂度退化为O(n)。

    为了解决这个问题,引入了平衡二叉树。

     

     

    二、平衡二叉树(AVL):旋转耗时

    AVL树是严格的平衡二叉树,所有节点的左右子树高度差不能超过1;AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。

    AVL实现平衡的关键在于旋转操作:插入和删除可能破坏二叉树的平衡,此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时,最多只需要1次旋转(单旋转或双旋转);但是当删除数据时,会导致树失衡,AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡,旋转的量级为O(lgn)。

    由于旋转的耗时,AVL树在删除数据时效率很低;在删除操作较多时,维护平衡所需的代价可能高于其带来的好处,因此AVL实际使用并不广泛。

    三、红黑树:树太高

    与AVL树相比,红黑树并不追求严格的平衡,而是大致的平衡:只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看,红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一,且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下(图片来源):

     

     

    与AVL树相比,红黑树的查询效率会有所下降,这是因为树的平衡性变差,高度更高。但红黑树的删除效率大大提高了,因为红黑树同时引入了颜色,当插入或删除数据时,只需要进行O(1)次数的旋转以及变色就能保证基本的平衡,不需要像AVL树进行O(lgn)次数的旋转。总的来说,红黑树的统计性能高于AVL。

    因此,在实际应用中,AVL树的使用相对较少,而红黑树的使用非常广泛。例如,Java中的TreeMap使用红黑树存储排序键值对;Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时,使用链表,当冲突节点较多时,使用红黑树)。

    对于数据在内存中的情况(如上述的TreeMap和HashMap),红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况(如MySQL等数据库),红黑树并不擅长,因为红黑树长得还是太高了。当数据在磁盘中时,磁盘IO会成为最大的性能瓶颈,设计的目标应该是尽量减少IO次数;而树的高度越高,增删改查所需要的IO次数也越多,会严重影响性能。

    四、B树:为磁盘而生

    B树也称B-树(其中-不是减号),是为磁盘等辅存设备设计的多路平衡查找树,与二叉树相比,B树的每个非叶节点可以有多个子树。因此,当总节点数量相同时,B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”),磁盘IO次数大大减少。

    定义B树最重要的概念是阶数(Order),对于一颗m阶B树,需要满足以下条件:

    • 每个节点最多包含 m 个子节点。
    • 如果根节点包含子节点,则至少包含 2 个子节点;除根节点外,每个非叶节点至少包含 m/2 个子节点。
    • 拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
    • 所有叶节点都在同一层中。

    可以看出,B树的定义,主要是对非叶结点的子节点数量和记录数量的限制。

    下图是一个3阶B树的例子(图片来源):

     

     

    B树的优势除了树高小,还有对访问局部性原理的利用。所谓局部性原理,是指当一个数据被使用时,其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点,当访问其中某个数据时,数据库会将该整个节点读到缓存中;当它临近的数据紧接着被访问时,可以直接在缓存中读取,无需进行磁盘IO;换句话说,B树的缓存命中率更高。

    B树在数据库中有一些应用,如mongodb的索引使用了B树结构。但是在很多数据库应用中,使用了是B树的变种B+树。

    五、B+树

    B+树也是多路平衡查找树,其与B树的区别主要在于:

    • B树中每个节点(包括叶节点和非叶节点)都存储真实的数据,B+树中只有叶子节点存储真实的数据,非叶节点只存储键。在MySQL中,这里所说的真实数据,可能是行的全部数据(如Innodb的聚簇索引),也可能只是行的主键(如Innodb的辅助索引),或者是行所在的地址(如MyIsam的非聚簇索引)。
    • B树中一条记录只会出现一次,不会重复出现,而B+树的键则可能重复重现——一定会在叶节点出现,也可能在非叶节点重复出现。
    • B+树的叶节点之间通过双向链表链接。
    • B树中的非叶节点,记录数比子节点个数少1;而B+树中记录数与子节点个数相同。

    由此,B+树与B树相比,有以下优势:

    • 更少的IO次数:B+树的非叶节点只包含键,而不包含真实数据,因此每个节点存储的记录个数比B数多很多(即阶m更大),因此B+树的高度更低,访问时所需要的IO次数更少。此外,由于每个节点存储的记录数更多,所以对访问局部性原理的利用更好,缓存命中率更高。
    • 更适于范围查询:在B树中进行范围查询时,首先找到要查找的下限,然后对B树进行中序遍历,直到找到查找的上限;而B+树的范围查询,只需要对链表进行遍历即可。
    • 更稳定的查询效率:B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点),而B+树的查询复杂度则稳定为树高,因为所有数据都在叶节点。

    B+树也存在劣势:由于键会重复出现,因此会占用更多的空间。但是与带来的性能优势相比,空间劣势往往可以接受,因此B+树的在数据库中的使用比B树更加广泛。

    六、B+树的魅力

    前面说到,B树/B+树与红黑树等二叉树相比,最大的优势在于树高更小。实际上,对于Innodb的B+索引来说,树的高度一般在2-4层。下面来进行一些具体的估算。

    树的高度是由阶数决定的,阶数越大树越矮;而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page),页的大小为16KB,其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等),大多数空间都用来存储数据。

    • 对于非叶节点,记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录,则每条记录大约占用16字节;当索引是整型或较短的字符串时,这个假设是合理的。延伸一下,我们经常听到建议说索引列长度不应过大,原因就在这里:索引列太长,每个节点包含的记录数太少,会导致树太高,索引的效果会大打折扣,而且索引还会浪费更多的空间。
    • 对于叶节点,记录包含了索引的键和值(值可能是行的主键、一行完整数据等,具体见前文),数据量更大。这里假设每个叶节点页面存储100条记录(实际上,当索引为聚簇索引时,这个数字可能不足100;当索引为辅助索引时,这个数字可能远大于100;可以根据实际情况进行估算)。

    对于一颗3层B+树,第一层(根节点)有1个页面,可以存储1000条记录;第二层有1000个页面,可以存储1000*1000条记录;第三层(叶节点)有1000*1000个页面,每个页面可以存储100条记录,因此可以存储1000*1000*100条记录,即1亿条。而对于二叉树,存储1亿条记录则需要26层左右。

    七、总结

    展开全文
  • 红黑树的特性实现

    千次阅读 2018-04-23 00:13:34
    平衡二叉搜索树的形式多样,且各具特色。比如,伸展树实现简便、无需修改节点 结构、分摊复杂度低,但可惜最坏情况下的单次操作需要n时间,故难以适用于对可靠性稳定性要求极高的...红黑树即是针对后一不足的改进...

    平衡二叉搜索树的形式多样,且各具特色。比如,伸展树实现简便、无需修改节点 结构、分摊复杂度低,但可惜最坏情况下的单次操作需要n时间,故难以适用于对可靠性和稳定性要求极高的场合。
    反之,AVL树尽管可以保证最坏情况下的单次操作速度,但需在节点中嵌入平衡因子等标识;更重要的是,删除操作之后的重平衡可能需做多达logn次旋转,从而频繁地导致全树整体拓扑结构的大幅度变化。

    红黑树即是针对后一不足的改进。通过为节点指定颜色,并巧妙地动态调整,红黑树可保证: 在每次插入或删除操作之后的重平衡过程中,全树拓扑结构的更新仅涉及常数个节点。尽管最坏情况下需对多达logn个节点重染色,但就分摊意义而言仅为O(1)个

    当然,为此首先需在AVL树“适度平衡”标准的基础上,进一步放宽条件。实际上,红黑树所采用的“适度平衡”标准,可大致表述为:任一节点左、右子树的高度,相差不得超过两倍。

    定义与条件

    为便于对红黑树的理解、实现与分析,这里不妨下图所示统一地引入n + 1个外部节点,以保证原树中每一节点(现称作内部节点,白色八角形)的左、右孩子均非空—尽管有可能其中之一甚至二者同时是外部节点。
    这里写图片描述

    这些外部节点的引入只是假想式的,在具体实现时并 不一定需要兑现为真实的节点。如此扩展之后的便利 之处在于,我们的考查范围只需覆盖真二叉树。

    由红、黑两色节点组成的二叉搜索树若满足以下条件,即为红黑树(red-black tree):

    • (1) 树根始终为黑色
    • (2) 外部节点均为黑色
    • (3) 其余节点若为红色,则其孩子节点必为黑色
    • (4) 从任一外部节点到根节点的沿途,黑节点的数目相等

    条件(1)和(2)意味着红节点均为内部节点,且其父节点及左、右孩子必然存在。
    条件(3)意味着红节点之父必为黑色,因此树中任一通路都不含相邻的红节点。

    由此可知,在从根节点通往任一节点的沿途,黑节点都不少于红节点。除去根节点本身,沿 途所经黑节点的总数称作该节点的黑深度(black depth)–根节点的黑深度为0,其余依此类推。故条件(4)亦可等效地理解和描述为“所有外部节点的黑深度统一”。
    由条件(4)可进一步推知,在从任一节点通往其任一后代外部节点的沿途,黑节点的总数亦 必相等。除去(黑色)外部节点,沿途所经黑节点的总数称作该节点的黑高度(black height)。 如此,所有外部节点的黑高度均为0,其余依此类推。
    特别地,根节点的黑高度亦称作全树的黑高度,在数值上与外部节点的黑深度相等。

    在红黑树与4阶B-树之间,存在极其密切的联系; 经适当转换之后,二者相互等价!

    具体地,自顶而下逐层考查红黑树各节点。每遇到一个红节点,都将对应的子树整体提升一 层,从而与其父节点(必黑)水平对齐,二者之间的联边则相应地调整为横向。

    这里写图片描述

    照此理解,此时的关键码也被赋予了对应的颜色。对照红黑 树的条件,(2,4)B-树中的每个节点应包含且仅包含一个黑关键码,同时红关键码不得超过两个。 而且,若某个节点果真包含两个红关键码,则黑关键码的位置必然居中。

    与前文介绍二叉平衡树的其他成员的时候一样,接下来将学习在插上,删除的等操作的时候如何保障其红黑树的特性。

    红黑树的节点新增

    红黑数的新增过程,经调用查找之后,确认目标节点尚不存在。于是,在查找终止的位置x处创建节点,并随即将其染成红色(除非此时全树仅含一个节点)。

    现在,对照红黑树的上述四项条件,唯有(3)未必满足,此时x的父亲也可能是红色。

    因新节点的引入,而导致父子节点同为红色的此类情况,称作“双红”(double red)。 此时,当前节点x的兄弟及两个孩子(初始时都是外部节点),始终均为黑色。

    将x的父亲与祖父分别记作p和g。既然此前的红黑树合法,故作为红节点p的父亲,g必然存 在且为黑色。g作为内部节点,其另一孩子(即p的兄弟、x的叔父)也必然存在,将其记作u。 以下,视节点u的颜色不同,分两类情况分别处置。

    双红修正-u为黑色
    这里写图片描述

    此时红黑树条件(3)的违反,从B-树角度等效地看,即同一节点不应包含紧邻的红色关键码。

    故按如上图(c’)所示,只需令黑色关键码与紧邻的红色关键码互换颜色。从图(c)红黑树的角度看,这等效于按中序遍历次序,对节点x、p和g及其四棵子树,做一次局部“3 + 4”重构(对于“3 + 4”重构,详见:https://blog.csdn.net/canot/article/details/78946450)。
    由于该3+4重构过程中,根节点b最终肯定为黑色,不会导致向上传播的现象。

    双红修正-u为红色
    节点u为红色的情况。此时,u的左、右孩子非空且均为黑色,其黑高度必与x的兄弟
    以及两个孩子相等。

    这里写图片描述

    如上图的a,b两种情况。此时红黑树条件(3)的违反,从B-树角度等效地看,即该节点因超过4度而发生上溢。
    从图(c)红黑树的角度来看,只需将红节点p和u转为黑色,黑节点g转为红色,x保持红色。从图(c’)B-树的角度来看,等效于上溢节点的一次分裂。
    如此调整之后局部子树的黑高度复原。然而,子树根节点g转为红色之后,有可 能在更高层再次引发双红现象。 即B-树中的上溢的传播,此时可以等效地将g视作新插入的节点,同样地分以上两类情况如法处置。请注意, 每经过一次这样的迭代,节点g都将在B-树中(作为关键码)上升一层,而在红黑树中存在双红缺陷的位置也将相应地上升两层,故累计至多迭代O(logn)次。若最后一步迭代之后导致原树根的分裂,并由g独立地构成新的树根节点,则应遵 照红黑树条件(1)的要求,强行将其转为黑色。此时,全树的黑高度随即增加一层。

    红黑树节点删除

    假设删除节点为x。在删除x的过程中,如果x不是叶子节点,在将x与其中序遍历中的后继节点交换。此时x则一定为叶子节点,并且一定无左孩子,假设其删除后的接替节点即右孩子为r。并设p = _hot为x的父亲。

    这里写图片描述

    如上图所示,除了其接替者r, x还应有另一个孩子—左孩子w,且w必为(黑色的)外部节点 NULL。
    如图(a)和(a’)所示,若x为红色,则在删除x并代之以r后,条件 (3~4)依然满足;
    反之,若x为黑色, 则要看其替代者r的颜色,如图(b)和(b’)所示,若r为红色,则只需将其翻转为黑色,即可使条件(3~4)重新满足。

    然而如图(c)和(c’)所示,若x和r均为黑色,则为使条件(3~4)重新成 立,还需要做略微复杂一些的处理。
    因某一无红色孩子的黑节点被删除,而导致的此类复杂情况,称作“双黑”(double black) 现象。

    原黑节点x的兄弟必然非空(保证节点到所有外部节点到黑节点数量一致),将其记作s;
    x的父亲记作p,其颜色不确定(八角形示意)。以下视s和p颜色的不同组合,按四种情况分别处置。

    双黑修正—1

    这里写图片描述

    既然节点x的另一孩子w = NULL,故从B-树角度看节点x被删除之后的情况(上图a’),
    可以等效地理解为: 关键码x原所属的节点发生下溢;此时,t和s必然属于B-树的同一节点,且该节点就是下溢节点的兄弟。故可参照B-树的调整方法,下溢节点从父节点借出一个关键码(p), 然后父节点从向下溢节点的兄弟节点借出一个关键码(s),调整后的效果如图(b’)。

    从红黑树的角度(图(b))来看, 上述调整过程等效于,对节点t、s和p 实施“3 + 4”重构。
    此外,根据红黑树与B-树的对应关系不难理解,若这三个节点按中序遍历次序重命名为a、b和c,则还需将a 和c染成黑色,b则继承p此前的颜色。 就上图具体实例而言,也就是将t和p染成黑色,s继承p此前的颜色。注意,整个过程中节点r保持黑色不变。

    双黑修正—2

    这里写图片描述

    节点s及其两个孩子均为黑色时,视节点p颜色的不同,又可进一步分为两种情况。
    先考虑p为红色的情况。如上图所示。

    在对应的B-树中,关键码x的删除导致其所属的节点下溢。但因此时关键码s所在节点只有两 个分支,故下溢节点无法从父节点借出关键码(p)。

    按照前文的B-树平衡算法,此时应如图(b’)所 示,将关键码p取出并下降一层,然后以之为“粘合剂”, 将原左、右孩子合并为一个节点。从红黑树角度看,这 一过程可如图(b)所示等效地理解为: s和p颜色互换。

    由图(b)(及其对称情况)可知,经过以上处理,红黑树的所有条件都在此局部得以恢复。另外,由于关键码p原为红色,故如图8.30(a’)所示,在关键码p所属节点中,其左或右必然还有一个黑色关键码(当然, 不可能左、右兼有)–这意味着,在关键码p从其中取 出之后,不致引发新的下溢。至此,红黑树条件亦必在 全局得以恢复,删除操作即告完成。

    双黑修正–3

    这里写图片描述

    接下来,再考虑节点s、s的两个孩子以及节点p均为黑色的情况。 如图(a)所示,在对应的B-树中,因关键码x的删除,导致其所属节点发生下溢。

    因此可如图(b’)所示,将下溢节点与其兄弟合并。从红黑树的角度来看,这一过程可如图(b)所示等效地理解为: 节点s由黑转红。

    由图(b)可知,经以上处理,红黑树所有条件都在此局部得到恢复。

    然而,因s和x在此之前均为黑色,故如图(a’)所示,p原所属的B-树节点必然仅含p这一个关 键码。于是在p被借出之后,该节点 必将继而发生下溢,故有待于后续进一步修正。

    从红黑树的角度来看,此时的状态可等效地理解为: 节点p的父节点刚被删除。当然,可以 按照本节所介绍的算法,视具体的情况继续调整。
    实际上稍后总结时将会看出,这也是双黑修正过程中,需要再次迭代的唯一可能。幸运的是, 尽管此类情况可能持续发生,下溢的位置也必然不断上升,故至多迭代O(logn)次后必然终止。

    双黑修正-4

    最后,考虑节点s为红色的情况。

    这里写图片描述

    如图a所示作为红节点s的父亲,节点p必为黑色;
    同时,s的两个孩子也应均为黑色。
    于是从B-树的角度来看,只需如图(b’)所示,令关键码s与p互换 颜色,即可得到一棵与之完全等价的B-树。而从红黑树的角度来看, 这一转换对应于以节点p为轴做一次旋转,并交换节点s与p的颜色。

    经过这一转换之后,情况已经发生了微妙而本质的变化。仔细观察图(b)不难发现, 在转换之后的红黑树中,被删除节点x(及其替代者节点r)有了一个新的兄弟s’–与此前的 兄弟s不同,s’必然是黑的!这就意味着,接下来可以套用此前所介绍其它情况(1和2)的处置方法,继续并最终完成双黑修正。

    展开全文
  • 红黑树的结构优势

    千次阅读 2019-03-30 16:24:49
    红黑树的结构特点: (1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!] (4)如果一个节点是红色的,则它的子...

    首先看一下红黑树的结构:

    在这里插入图片描述
    红黑树的结构特点:
    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的。
    (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    为什么要要用红黑树?
    1、首先红黑树是不符合AVL树的平衡条件的,即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色,红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。所以红黑树的插入效率更高

    2、红黑树能够以O(log2 (n)) 的时间复杂度进行搜索、插入、删除操作

    3、简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

    红黑树和平衡树的对比和选择
    1、平衡树结构更加直观,读取性能比红黑树要高;增加和删除节点 恢复平衡的性能不如红黑树
    2、红黑树,读取性能不如平衡树;增加和删除节点 恢复平衡性能比平衡树好

    红黑树的使用场景:
    TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。

    展开全文
  • 红黑树优点

    2017-06-08 11:22:29
    它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-VelskiiLandis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树...
    1. 红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。  
    2.   
    3. 红黑树的定义如下:  
    4.   
    5.   
    6. 满足下列条件的二叉搜索树是红黑树  
    7.   
    8.     * 每个结点要么是“红色”,要么是“黑色”(后面将说明)  
    9.     * 所有的叶结点都是空结点,并且是“黑色”的  
    10.     * 如果一个结点是“红色”的,那么它的两个子结点都是“黑色”的  
    11.     * (注:也就是說,如果結點是黑色的,那么它的子節點可以是紅色或者是黑色的)。  
    12.     * 结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点  
    13.     * 根结点永远是“黑色”的  
    14.   
    15. 之所以称为红黑树的原因就在于它的每个结点都被“着色”为红色或黑色。这些结点颜色被用来检测树的平衡性。但需要注意的是,红黑树并不是平衡二叉树,恰恰相反,红黑树放松了平衡二叉树的某些要求,由于一定限度的“不平衡”,红黑树的性能得到了提升。  
    16.   
    17. 从根结点到叶结点的黑色结点数被称为树的“黑色高度”(black-height)。前面关于红黑树的性质保证了从根结点到叶结点的路径长度不会超过任何其他路径的两倍。  
    18.   
    19. 我们来解释一下这个结论。考虑一棵黑色高度为3的红黑树:从根结点到叶结点的最短路径长度显然是2(黑-黑-黑),最长路径为4(黑-红-黑-红- 黑)。由于性质4,不可能在最长路经中加入更多的黑色结点,此外根据性质3,红色结点的子结点必须是黑色的,因此在同一简单路径中不允许有两个连续的红色结点。综上,我们能够建立的最长路经将是一个红黑交替的路径。  
    20.   
    21. 由此我们可以得出结论:对于给定的黑色高度为n的红黑树,从根到叶结点的简单路径的最短长度为n-1,最大长度为2(n-1)。  
    22.   
    23. 插入和删除操作中,结点可能被旋转以保持树的平衡。红黑树的平均和最差搜索时间都是O(log2 n)。Cormen [2001]给出了对于这一结论的证明。在实际应用中,红黑树的统计性能要好于平衡二叉树,但极端性能略差。  
    24.   
    25. 红黑树中结点的插入过程  
    26.   
    27. 插入结点的过程是:  
    28.   
    29.   
    30.     * 在树中搜索插入点  
    31.     * 新结点将替代某个已经存在的空结点,并且将拥有两个作为子结点的空结点  
    32.     * 新结点标记为红色,其父结点的颜色根据红黑树的定义确定;如果需要,对树作调整  
    33.   
    34. 注意 空结点和NULL指针是不同的。在简单的实现中,可以使用作为“监视哨”,标记为黑色的公共结点作为前面提到的空结点。  
    35.   
    36. 给一个红色结点加入两个空的子结点符合性质4,同时,也必须确保红色结点的两个子结点都是黑色的(根据性质3)。尽管如此,当新结点的父结点时红色时,插入红色的子结点将是违反定义的。这时存在两种情况。  
    37.   
    38. 红色父结点的兄弟结点也是红色的  
    39.   
    40. 例如下面的情况(X是希望插入的结点,  
    41.   
    42. 简单地对上级结点重新着色将解决冲突。当结点B被重新着色之后,应该重新检验更大范围内树结点的颜色,以确保整棵树符合定义的要求。结束时根结点应当是黑色的,如果它原先是红色的,则红黑树树的黑色高度将递增1。  
    43.   
    44. 红色父结点的兄弟结点是黑色的  
    45.   
    46. 这种情形比较复杂,如下图:  
    47.   
    48. 重新对结点着色将把结点A变成黑色,于是,树的平衡将被破坏,因为左子树的黑色高度将增加,而右子树的黑色高度没有相应地改变。如果我们把结点B着上红色,那么左右子树的高度都将减少,树依然不平衡。此时,继续对结点C进行着色将导致更糟糕的情况,左子树黑色高度增加,右子树黑色高度减少。为了解决问题,需要旋转并对树结点进行重新着色。这时算法将正常结束,因为子树的根结点(A)被着色为黑色,同时,不会引入新的红-红冲突。  
    49.   
    50. 结束插入过程  
    51.   
    52. 插入结点时,可能会需要重新着色,或者旋转,来保持红黑树的性质。如果旋转完成,那么算法就结束了。对于重新着色来说,我们会在子树的根留下一个红色结点,于是需要继续向上对树进行修整,以保持红黑树的性质。最坏情况下,我们将不得不对到树根的所有路径进行处理。插入的时间复杂度为O(log2 n)。删除结点的时间复杂度与此类似。  
    53.   
    54. 结点的删除  
    55.   
    56. 红黑树的结点删除情况要比插入复杂一些。我们可以把实际的删除操作分成3种情况(先不讨论颜色),其中被删除的结点用紫色标记,蓝色表示任意颜色的结点,可能是红色,也可能是黑色:  
    57.   
    58. 情况a: 被删除的结点没有子结点(两个子结点都是空结点)  
    59.   
    60. 原先属于X的空结点被A“继承”。如果被删除结点是黑色结点,则可能造成树的黑色高度变化。  
    61.   
    62. 情况b: 有一个子结点  
    63.   
    64. B结点取代原X结点的位置。如果被删除的结点是黑色结点,则可能造成树的黑色高度发生变化;如果B是红色结点,还可能需要重新着色。  
    65.   
    66. 情况c: 有两个子结点  
    67.   
    68. 这种情形比较复杂。需要将X和它的左子树中的键值最大的结点进行交换。这通常会导致重新着色,对树的黑色高度的改变,以及随之而来的旋转。  
    69.   
    70. 需要说明的是,仅仅删除结点是不够的,因为此后很可能还需要对树进行重新着色。如果删除的是红色结点,那么没有关系,因为这不会影响树的黑色高度;而如果删除的是黑色结点,事情就没那么简单了。需要把受到影响(移动或交换)的结点标记为黑色,如果它原来已经是黑色的,那么需要标记为“双黑”(双黑,或double-black是许多英文资料中提及的一个概念。简单地说,标记为“双黑”意味着需要对周围的红色结点进行“抹黑 ”处理)。  
    71.   
    72. 包含“双黑”结点显然不符合红黑树的要求,因此必须消除这种情况。出现“双黑”的情况可以分为4种:  
    73.   
    74. 1、双黑结点的兄弟结点是红色的  
    75.   
    76. 2、双黑结点的兄弟是黑色的,并且它的兄弟有两个黑色的子结点  
    77.   
    78. 3、双黑结点的兄弟是黑色的,并且,它的兄弟的左、右子结点分别是红色和黑色  
    79.   
    80. 4、双黑结点的兄弟是黑色的,并且,它的兄弟的右子结点是红色的  
    81.   
    82. 很显然,上述四种情况包括了可能的所有状况。  
    83.   
    84. 处理双黑结点的基本思想是进行“色彩补偿”。换言之,将邻近的红色结点变为黑色,同时,此双黑结点也“还原”为黑色。  
    85.   
    86. 总结  
    87.   
    88. 红黑树引入了“颜色”的概念。引入“颜色”的目的在于使得红黑树的平衡条件得以简化。正如著名的密码学专家Bruce Schneier所说的那样,“Being Partly balanced can be good enough”,红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。  
    89.   
    90. 红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。  
    91.   
    92. 当然,红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。  
    93.   
    94. 在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。 
    展开全文
  • 红黑树与AVL树,各自的优缺点总结

    千次阅读 2020-02-19 11:56:08
    特意转载来方便学习 RB-TreeAVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用...红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要...
  • 红黑树和哈希表

    2019-11-17 09:53:55
    一、哈希表和红黑树的数据结构分析 前言: hashmap是一种很常用的数据结构,其使用方便快捷,接下来笔者将给大家深入解析这个数据结构,让大家能在用的时候知其然,也知其所以然。 一.Map 首先,从最基本的讲起,...
  • 1、二叉查找缺点 二叉查找,相信大家都接触过,二叉查找特点就是左子树的节点值比父亲节点小,而右子的节点值比父亲节点大,如图 基于二叉查找的这种特点,我们在查找某个节点的时候,可以采取类似于...
  • 为什么要使用红黑树,B树B+树

    千次阅读 多人点赞 2018-12-21 17:22:18
    一、红黑树 1、红黑树的特性 (1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!] (4)如果一个节点是红色的,...
  • 哈希表与红黑树特点及区别

    千次阅读 2018-09-27 22:36:00
    红黑树查找删除的时间复杂度都是O(logn),Hash查找删除的时间复杂度都是O(1)。 补充: 如果只需要判断Map中某个值是否存在之类的操作,当然是Hash实现的要更加高效。 如果是需要将两个Map求并集交集...
  • 跳表和红黑树和二叉树

    千次阅读 2019-06-14 20:18:11
    数据结构算法之——跳表 之前我们知道,二分查找依赖数组的随机访问,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找了吗?而实际上,我们只需要对链表稍加改造,就可以实现类似“二分”的...
  • 二叉搜索的一个缺点是不平衡,当插入的数是随机数时效果很好,当插入的是有序的数时就链表一样了,没有了插入查询都块的特点了,这里介绍一种改进保证了二叉搜索的平衡,当插入的是顺序也好随机也好都能保证...
  • 今天我们要说的红黑树就是就是一棵非严格均衡的二叉树,均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质,插入、搜索、删除的效率都比较高。红黑树也是实现 TreeMap 存储结构的基石。 文章相关视频...
  • 红黑树详解以及与BSTAVL树的比较

    千次阅读 2017-10-17 21:04:21
    1.stl中的set底层用的什么数据结构? 红黑树 2.红黑树的数据结构怎么定义? [cpp] view plain copy     enum Color  {   
  • 红黑树与跳表

    2020-04-12 09:46:13
    先分析一波红黑树吧。。 根节点到任意一个叶子节点所经过的节点数量是相同的 每个节点或者是红色,或者是黑色(定义) 根节点一定是黑色的(对应2-3树的2节点3节点) 空节点是黑色的 如果一个节点是红色的,...
  • Hash和红黑树是两种数据存储的方式。除了这两种存储方式,最常用的是线性结构存储,比如数组链表List等线性结构。 对于线性存储的数据,如果想检索一个数据,需要把所有数据都遍历一遍,然后找
  • 文章目录红黑树概念插入情况1情况2删除情况1情况2情况3情况4情况5代码插入删除双红双黑更新高度 红黑树概念 提升变换,把红孩子提到父亲就是4阶B树 高度证明 #include "BST/BST.h" //基于BST实现RedBlack template...
  • 文章目录前引推荐数据结构可视化网址推荐讲解红黑树的博客与视频红黑树介绍1、接触红黑树的原因2、二叉搜索树的介绍1、二叉搜索树BST(不自平衡)2、AVL树(完美自平衡二叉搜索树)3、红黑树(综合性能强劲 不平凡的...
  • HashMap原理讲解(一) - 红黑树

    千次阅读 2017-12-22 11:47:58
    左子树右子是有顺序的,次序不能颠倒 即使某个节点只有一个子树,也要区分左右子树 1.2 二叉树基本形态:逻辑上二叉树有五种基本形态: 空二叉树 只有一个根节点的二叉树 只有左子树 只有右子 完全二叉树 二. ...
  • 注意:本文不涉及红黑树的具体实现,并且默认读者已经对二叉树,二叉查找树,AVL树等已经了解并熟悉。 一、平衡二叉查找树 定义:树中任意一个节点的左右子树高度差不大于1。 AVL树是一种严格按照定义来实现的...
  • 特性(除了具备二叉查找树的特性外,还具备如下特性): (1)节点是红色或者黑色 (2)根节点是黑色 (3)每个叶子节点(也叫终端节点,简称“叶子”)都是黑色的空节点(NIL...红黑树从根到叶子的最长路径不会超...
  • 1、二叉查找(Binary Search Tree) 很显然,二叉查找的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。 BST的操作代价分析: (1) 查找代价: 任何一个数据的查找...
  • HashMap底层红黑树实现(自己实现一个简单的红黑树)

    千次阅读 多人点赞 2020-11-09 16:49:03
    视频学习链接:小刘老师讲解红黑树 1.树结构入门 |—树 ​ |—树结构常用语 ​ |—二叉搜索树 ​ |—查找节点 ​ |—插入节点 ​ |—遍历 ​ |—查找最大值,最小值算法 ​ |—删除节点 ​ |—①删除没有子节点的...
  • 二叉树,二叉查找树,平衡二叉树以及红黑树概述

    千次阅读 多人点赞 2019-07-05 21:17:39
    在这篇博客之前,花了些时间了解红黑树的内容,但是没有形成自己的知识图谱,也没有一条清晰的逻辑主线将知识串联起来,这次重新整理了一下。 首先,这里过滤了树模型的一些基础概念上的内容,比如父节点,子节点,...
  • 二叉查找树、红黑树

    2018-12-03 15:17:36
    1.什么是二叉查找? (解释:二叉查找,二叉搜索,二叉排序,三个都是一个意思) 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子上所有结点的值均大于或等于它的根结点的值。 3.左、右子也...
  • java数据结构B树 B+树 红黑树详解

    千次阅读 2019-10-17 16:41:21
    B树 B+树 红黑树详解 常见的查找算法 B树 查找 插入 没有破坏结构 结构破坏 分裂 删除 终端 1 直接删除 2兄弟够借 3兄弟不够借 非终端 1 2 ...
  • HashMap中的红黑树

    2018-02-13 20:21:04
    http://blog.csdn.net/u011240877/article/details/53358305 张拭心读完本文你将了解到:点击查看 Java 集合框架深入理解 系列 - - 乾杯传统 HashMap 的缺点HashMap 在 JDK 18 中新增的数据结构 红黑树HashMap 中...
  • 红黑树优点

    万次阅读 2012-09-03 21:13:42
    它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-VelskiiLandis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树...
  • mapset都是用红黑树实现的。我们熟悉的STL的map容器底层是RBtree,当然指的不是unordered_map,后者是hash。 B/B+树用在磁盘文件组织 数据索引数据库索引 Trie树 字典树,用在统计排序大量字符串 ...
  • 红黑树讲解

    2019-07-29 17:22:22
    定义:红黑树是一种含有红黑节点并能自平衡的二叉查找树,在进行插入删除等可能会破坏树的平衡的操作时,需要重新自调整达到平衡状态,这里平衡的含义是保证最长路径不超过最短路径的两倍。红黑树是一种非严格平衡...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,634
精华内容 7,853
关键字:

红黑树的优点和缺点