精华内容
下载资源
问答
  • 二叉树 红黑树 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层左右。

    七、总结

    展开全文
  • 红黑树与AVL树,各自的优缺点总结

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

    本文内容来自链接:https://www.jianshu.com/p/37436ed14cc6
    特意转载来方便学习

    RB-Tree和AVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用AVL树是代替,那么为什么还需要引入RB-Tree呢?

    红黑树不追求"完全平衡",即不像AVL那样要求节点的 |balFact| <= 1,它只要求部分达到平衡,但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。
    就插入节点导致树失衡的情况,AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance,旋转的量级是O(1)
    删除节点导致失衡,AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡,旋转的量级为O(logN),而RB-Tree最多只需要旋转3次实现复衡,只需O(1),所以说RB-Tree删除节点的rebalance的效率更高,开销更小!
    AVL的结构相较于RB-Tree更为平衡,插入和删除引起失衡,如2所述,RB-Tree复衡效率更高;当然,由于AVL高度平衡,因此AVL的Search效率更高啦。
    针对插入和删除节点导致失衡后的rebalance操作,红黑树能够提供一个比较"便宜"的解决方案,降低开销,是对search,insert ,以及delete效率的折衷,总体来说,RB-Tree的统计性能高于AVL.
    故引入RB-Tree是功能、性能、空间开销的折中结果。
    5.1 AVL更平衡,结构上更加直观,时间效能针对读取而言更高;维护稍慢,空间开销较大。
    5.2 红黑树,读取略逊于AVL,维护强于AVL,空间开销与AVL类似,内容极多时略优于AVL,维护优于AVL。
    基本上主要的几种平衡树看来,红黑树有着良好的稳定性和完整的功能,性能表现也很不错,综合实力强,在诸如STL的场景中需要稳定表现。
    红黑树的查询性能略微逊色于AVL树,因为其比AVL树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较,但是,红黑树在插入和删除上优于AVL树,AVL树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于AVL树为了维持平衡的开销要小得多

    总结:实际应用中,若搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB。

    展开全文
  • 前言上一篇博客介绍了[二叉树]...阅读前须知:如果您对二叉树不太了解,请移步[二叉树]本文用到的评估红黑树效率的方法-- 大O表示法由于红黑树的实现代码过于晦涩难懂,所以本篇博客只会通过通俗易懂的语言加上一目了然...

    前言

    上一篇博客介绍了[二叉树].二叉搜索树在树是平衡的情况下搜索、插入和删除的效率都很好,但是如果二叉搜索树是不平衡的那么它的效率就不那么令人满意了,而红黑树解决了二叉搜索树的这个问题,可以始终保持树是平衡(大致平衡)的.

    阅读前须知:

    如果您对二叉树不太了解,请移步[二叉树]

    本文用到的评估红黑树效率的方法-- 大O表示法

    由于红黑树的实现代码过于晦涩难懂,所以本篇博客只会通过通俗易懂的语言加上一目了然的图片对红黑树进行讲解

    本文的侧重点是红黑树的插入过程

    假定插入红黑树的值不会重复

    1. 红黑树简介

    红黑树是什么? 其实红黑树就是加了一些特殊规则(保持树平衡的规则)的二叉搜索树.

    红黑树的两个特征:

    节点都有颜色

    在删除和插入过程中,保证这些颜色不同排列的规则(红黑规则)

    当插入(或删除)一个节点时,必须遵守红黑规则以保持树是大体平衡的,红黑规则:

    每个节点不是红色的就是黑色的

    根节点是黑色的

    所有叶子都是黑色(叶子是NIL节点或NULL). (NIL: NIL表示无值,任何变量在没有被赋值之前的值都为NIL)

    红色节点的子节点必须是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色节点),反之不成立

    从根到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(也可称为黑色高度).

    红黑规则的图解:

    图1

    FBI WARNING: 本文接下来给出的图例中将会省略规则3中的NIL叶节点, 特此强调

    关于规则5空子节点的示例,可以看到下图中根到叶节点和根到空子节点的高度不一致,违背了规则5:

    图2

    下面是红黑规则的总结,重要结论->重要结论->重要结论,红黑规则确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的(如果插入的数据是有序的,红黑树不会出现极端不平衡的情况,会自己修复),而不同于普通的二叉搜索树。

    是规则4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据规则5所有路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

    2. 了解插入过程前的一些热身准备

    在了解红黑树插入一个新节点的时候都做了什么以前,有一些插入过程中用到的概念会在本章节进行讲解,如果你对变色、旋转有所了解,可以跳过本节.

    首先红黑树新插入的节点都是红色的,并且红黑树是在插入数据的过程中对树进行平衡修复的,如果感知到违反了红黑规则,程序会进行自我修复以符合红黑规则,修复方法有且只有两种:

    改变节点的颜色

    执行旋转操作

    接下来会对一下三个方面做出解释:

    为什么新插入的节点是红色的?

    改变节点的颜色?

    旋转操作?

    2.1 新插入的节点都是红色的

    为什么新插入的节点都是红色的?不是黑色的?

    主要有两方面原因:

    不会违背规则5,从根到所有叶或空子节点的黑色高度不会改变

    虽然有可能会违背规则4出现两个连续的红色节点,但是只有50%的几率碰上,并且就算碰上了,修复规则4也比修复规则5要简单的多(只需要几次变色和几次旋转就能修复规则4).

    2.2 变色

    变色..嗯就是变色,红的变成黑的,或者黑的变成红的. 至于什么情况下需要变色,怎么变色,需要具体问题具体分析,看完章节3就晓得了.

    2.3 旋转

    树左右两边的节点数量不相同的时候树就是不平衡的了,如果这时候想把树变为平衡的,就需要旋转.

    旋转必须一次做两件事:

    使一些节点上升,一些节点下降,帮助树平衡

    保证不破坏二叉搜索树的特征.

    二叉搜索树的特征: 任何节点的左子节点及其子树的关键字都小于该节点,而它的右子节点及其子树的关键字都大于等于它.

    关于旋转这个动作的定义: 选择一个节点作为旋转的"顶端"(top),如果做一次右旋,这个"顶端节点"将会向下和向右移动到它的右子节点的位置,它的左子节点将会上移到它原来的位置.

    以关键字值为10的节点为顶端,执行左旋转和右旋转:

    图3

    注意事项: 左旋转必须有右子节点,右旋转必须有左子节点.

    关于旋转有一个情况要注意: 如果旋转的顶端节点有内侧子孙节点,那么执行完旋转操作以后,这个内侧子孙节点要断开与父节点的连接,连接到顶端节点上.

    图4

    如果内侧子孙节点是一颗子树,那么整棵树也一起移动过去.

    3. 插入数据的过程

    准备活动做完了,下面开始正题.

    在红黑树中插入一个新节点的步骤和二叉搜索树有部分是相同的:从根开始,插入节点的关键字与当前节点的关键字进行比较,如果小往左走,如果大于等于该节点往右走,直到找到一个合适的位置进行插入.

    不同点:

    在向下比较的过程中需要变色

    在向下比较的过程中需要旋转

    插入新节点之后需要旋转

    下面来概述一下红黑树的插入过程: 从根开始比较关键字的值,如果小往左走,如果大于等于该节点往右走(这是相同点),从根往下走的过程中一旦发现有黑色节点有两个红色子节点的情况进行变色,变成红色节点有两个黑色节点(这是不同点1),变完色有可能会违背规则4不能出现连续的两个红色节点,这时候需要再次进行旋转和变色(这是不同点2),最后找到合适的位置插入新节点,如果新插入节点的父节点是黑色就结束了,如果是红色又违背了规则4,那么还需要旋转和变色(这是不同点3).

    现在不懂没关系, 3.1、3.2、3.3 三个章节会通过一个完整的示例,详细的讲述红黑树的插入过程.

    图5

    我们以往这棵树插入值为19的新节点为例

    3.1 在向下比较的过程中需要变色

    图6

    变色原则:

    在向下比较的过程中如果遇到一个黑色节点有两个红色节点,这时候要把它的颜色对调变成一个红色节点两个黑色节点.

    如果这个节点是根节点,那么就都变成黑色节点.

    图7

    变色后:

    图8

    至于为什么要变色: 只要应用了变色原则,插入节点后的旋转不会造成树的上方违背红黑原则.

    3.2 在向下比较的过程中需要旋转

    变色后出现了连续的红色节点,这时候我们需要进行旋转和变色修复红黑树,我们声明X、P、G三个节点:

    X是P的子节点

    P是G的子节点

    X是G的子孙节点

    图9

    X、P是连续红色节点的情况违背了规则4,这时候就要看X与G的位置关系了,X与G位置的不同,修复的步骤也不同:

    X是G外侧红色子孙节点的情况,需要旋转一次,变色两次.

    X是G内侧红色子孙节点的情况,需要旋转两次,变色两次.

    关于外侧子孙节点和内侧子孙节点位置的说明:

    如果P是G的左子节点,如果X是P的左子节点,那么X是G的外侧子孙节点

    如果P是G的左子节点,如果X是P的右子节点,那么X是G的内侧子孙节点

    (如果P是G的右子节点,X是P的右子节点,那么X是G的外侧子孙节点)

    回归正题,X是G外侧红色子孙节点的情况:

    图10

    X是G内侧红色子孙节点的情况:

    图11

    3.3 插入新节点之后需要旋转

    终于到最后一步了,新节点插入后(X),要根据父节点(P)的颜色,和它与祖父节点的位置进行调整,共有三种情况:

    P是黑色,直接结束

    P是红色,X是G的外侧子孙节点

    P是红色,X是G的内侧子孙节点

    P是红色,X是G的外侧子孙节点:

    图12

    P是红色,X是G的内侧子孙节点:

    图13

    以上就是红黑树插入一个新节点的完成过程.

    4. 红黑树的效率

    红黑树的效率与二叉搜索树相同都为为O(logN),红黑树的查找速度和二叉搜索树几乎一样,因为查找过程并没有应用红黑树的特征.只是额外增加了一些存储红-黑颜色的(boolean变量)存储空间.

    至于插入和删除因为要加入一些变色和旋转,所以要比二叉搜树慢一些,但是效率同样也为O(logN).

    5. 红黑树的总结,优缺点

    优点:

    查找速度和二叉搜索树相同

    如果插入的是有序数据效率不会慢到O(N),这点爆了二叉搜索树

    缺点:

    增、删略慢于二叉搜索树

    代码实现过于复杂...

    6. 实际中的应用

    Java中的TreeSet、TreeMap、Java8中的hashmap、Linux内核,面试官的灵魂拷问等等很多地方都用到了红黑树.

    7. 最早的平衡树AVL树

    AVL树是最早的平衡树,它是由AV(Adelson-Velskii)和L(Landis)两个发明者名字的缩写命名的.

    AVL树自平衡的方式: 在节点中保存左右子节点的高度,如果高度差大于1就进行自平衡(旋转).

    插入过程:

    插入之后,检查新节点插入点所在的最低子树的根,如果它的子节点的高度相差大于1,执行一次或者两次旋转使他们的高度相等.

    然后算法向上移动,检查上面的节点,必要时均衡高度.这个检测检查所有路径一直向上,直到根为止.

    AVL树的效率:

    查找的时间复杂度为O(logN)

    插入(或删除)由于需要扫描两趟,一次向下插入,一次向上平衡比,所以效率不如红黑树高.

    结论: AVL树因为插入(或删除)需要扫描两趟所以效率不如红黑树高,也不如红黑树常用,了解即可

    8. 下期预告

    红黑树的知识总结就到这里了,下一篇博客会更新2-3-4树、B-树(不是B减树是横杠)、B+树的知识,还有红黑树、二叉树与这些树的对比等内容,敬请期待.

    展开全文
  • 红黑树优点

    2017-06-08 11:22:29
    红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, ...
    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. 在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。 
    展开全文
  • 1、二叉查找缺点 二叉查找,相信大家都接触过,二叉查找的特点就是左子树的节点值比父亲节点小,而右子的节点值比父亲节点大,如图 基于二叉查找的这种特点,我们在查找某个节点的时候,可以采取类似于...
  • 1、二叉查找(Binary Search Tree) 很显然,二叉查找的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。 BST的操作代价分析: (1) 查找代价: 任何一个数据的查找...
  • 红黑树与2-3树

    2019-05-04 21:28:39
    算法导论中的红黑树: 1:每个结点都为红色或者黑色 2:根意结点为黑色 3:每一个叶子结点(最后的空节点)是黑色 4:如果一个意结点为红色,那么它的孩子结点为黑色 5:从任意结点到叶子结点经过的黑结点都一样(对...
  • 它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n)。 红黑树(red-black tree) 是一棵满足下述性质的二叉查找树: 1. 每一个结点...
  • 红黑树 接上篇hashmap的后续,关于红黑树的操作。 优点:红黑树查找方便,时间复杂度是树的高度。 红黑树的基本原理,大家应该都知道,我这里再写一遍: 树上的每个节点不是黑色就是红色 根节点是黑色 叶子节点是...
  • 很显然,二叉查找的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。 BST 的操作代价分析:  (1) 查找代价: 任何一个数据的查找
  • 根据离散数学的图论相关知识,可以证明2-3-4树和红黑树是等价的。对于m阶(m指的结点的最大分支数)B树,其结点的值的个数n:1&lt;=n&lt;m。因此,对于2-3-4树,其结点的值的个数1&lt;=n&lt;4,如下图...
  • 红黑树(平衡的排序二叉树),满足以下性质:1)每个结点要么是红的,要么是黑的。2)根结点是黑的。3)每个叶结点,即空结点(NIL)是黑的。4)如果一个结点是红的,那么它的俩个儿子都是黑的。5)对每个结点,从该结点到其...
  • 有序数组没法一次性加载进内存,这时候B+树的多路存储威力就出来了,可以每次加载B+树的一个结点,然后一步步往下找, 问题4:在内存中,红黑树比B树更,但是涉及到磁盘操作B树就更了,那么你能讲讲B+树吗?...
  • 链表和数组的优缺点 数组的特点 存放在内存中一块连续的区域 数组需要预留空间,可能出现数据溢出和内存浪费的情况 插入数据和删除数据的效率低,插入一个数据,后边的数据都要向后移动 随机读取的效率很高,因为...
  • 红黑树与跳表

    2020-04-12 09:46:13
    先分析一波红黑树吧。。 根节点到任意一个叶子节点所经过的节点数量是相同的 每个节点或者是红色,或者是黑色(定义) 根节点一定是黑色的(对应2-3树的2节点和3节点) 空节点是黑色的 如果一个节点是红色的,...
  • java数据结构B树 B+树 红黑树详解

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

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

    千次阅读 2018-09-27 22:36:00
    红黑树占用的内存更小(仅需要为其存在的节点分配内存),而Hash事先就应该分配足够的内存存储散列表(即使有些槽可能遭弃用)。 红黑树查找和删除的时间复杂度都是O(logn),Hash查找和删除的时间复杂度都是O(1)...
  • 索引的实现通常使用B和变种的B+(mysql常用的索引就是B+)索引是在存储引擎中实现的,也就是说不同的存储引擎,会使用不同的索引。MyISAM和InnoDB存储引擎:只支持BTREE索引,也就是说默认使用BTREE,不能够更换...
  • 红黑树讲解

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

    千次阅读 2019-06-14 20:18:11
    此外,相比于红黑树,跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点,因此 Redis 用跳表来实现有序集合   ===========================================================================...
  • 红黑树

    2020-06-16 10:25:02
    在前面,我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树,它支持快速插入、删除、查找操作,各个操作的时间复杂度跟树的高度成正比,理想...很多书籍里,但凡讲到平衡二叉查找树,就会拿红黑树
  • 二叉树,二叉查找树,平衡二叉树以及红黑树概述

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,130
精华内容 4,852
关键字:

红黑树的优缺点