红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的

红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的一篇搞定红黑树:从原理到应用实战前言:红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,他称之为”对称二叉B树

一篇搞定红黑树:从原理到应用实战   前言:红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,他称之为”对称二叉B树”,它现代的名字是在 Leo J.Guibas 和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(logn)时间内做查找,插入和删除,这里的n是树中素的数目。   精品文章推荐:C/C++发展方向(强烈推荐!!)Linux C/C++开发上线项目(后端、音视频、存储、QT)2023年Linux的知识技术合集(基础入门到高级进阶)2023年C/C++高性能技术知识大整理(进阶到大神级别)2023年音视频开发知识技术合集(基础入门到高级进阶)   一、红黑树的概念   红黑树,是一种二叉搜索树,但在每个节点上增加一个存储位表示节点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个节点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   红黑树的特性:(1)每个节点要么是黑色,要么是红色。(2)根节点为黑色(3)每个叶子节点(NIL)均为黑色。[注:这里的叶子节点指的是空(NIL或者NULL)的叶子节点!!!](4)如果一个节点是红色的,那么它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点NIL的所有路径上包含相同数目的黑节点。[注:这里指到叶子节点的路径]   特别说明:①特性(3)中的叶子节点,指的是只为空(NIL或NULL)的节点。②特性(5),确保没有一条路径会比其他路径长出两倍。因为,红黑树是相对接近平衡二叉树。   所以红黑树中最短路径是全部都由黑色节点组成的路径,最长的路径是由红黑节点交替组成的路径。假设全部的黑色节点有N个,那么最短路径长度为logN ,整棵树的节点数量在N ~ 2N之间,所以最长路径长度为2logN 。   这些约束强制了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。   二、红黑树的操作   2.1红黑树的定义   红黑树节点的结构体中多了一个表示颜色的枚举。需要注意的是,在红黑树节点的拷贝构造中,对于颜色的默认值给的是RED。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   这是因为如果新插入的节点是黑色的,那么一定会违反红黑树的性质4,即导致每条路径上的黑色节点不一致。而如果插入的节点是红色的,则不一定会使红黑树违反性质3,只有在新插入的红色节点的父亲也是红色节点时,才需要进行改动。   2.2红黑树的插入   红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:按照二叉搜索的树规则插入新节点检测新节点插入后,红黑树的性质是否造到破坏   因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整。但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论。约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点   1)cur为红,p为红,g为黑,u存在且为红
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   cur和p均为红,违反了性质三。解决方式:将p、u改为黑,g改为红,然后把g当成cur,继续向上调整。   实现代码:   2)cur为红,p为红,g为黑,u不存在/u存在且为黑
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   情况2一定是由2.1的情况变换过来,并继续向上更新的,否则插入前的状态就不符合红黑树。其演变过程:
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   此时 c 子树一定包含一个黑节点,d、e子树只能是一个红节点。解决方式:p为g的左孩子,cur为p的左孩子,则进行右单旋转p为g的右孩子,cur为p的右孩子,则进行左单旋转p、g变色–p变黑,g变红   3)cur为红,p为红,g为黑,u不存在/u存在且为黑(变种)
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   解决方法:p为g的左孩子,cur为p的右孩子,则针对p做左单旋转p为g的右孩子,cur为p的左孩子,则针对p做右单旋转   此时,情况三变为了情况二,再使用 2.2 的方法就可以。   实现代码:   2.3红黑树的验证   红黑树的检测分为两步:检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质   (1)检测一 编写测试代码:
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   观察到该树满足二叉搜索树。   (2)检测二根据红黑树的性质编写代码:   
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   观察到满足红黑树的性质。   2.4红黑树的性能   红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是 O(log N) ,红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。   附完整代码:   三、红黑树的应用   红黑树的应用十分广泛,以至于我们多多少少了解一些总是有好处的。红黑树可以用来储存有序数据[1],时间复杂度是O(logn),效率非常高。   例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树实现的。   3.1红黑树左旋和右旋   红黑树虽然特殊,但它也是一种树类型的数据结构,少不了增删查这类的操作。但在介绍添加、删除之前,我们需要先介绍一下旋转操作,这主要是出于对红黑树特性的考虑。毕竟在删除或者添加节点之后,很有可能会破坏原有的红黑树结构特性,这时候旋转操作就必不可少了,这和AVL树有一点点相像。总而言之,旋转的目的是让树保持红黑树的特性。   旋转包含两种:左旋和右旋。下面会分别进行介绍。   (1)左旋
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   对节点F进行左旋,意味着将节点F变为其右孩子节点R的左孩子节点,并将节点R的左子树变为节点F的右子树。可参考下图进行理解(此处暂时忽略节点的颜色问题):
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   对左旋稍微有点概念之后,可以结合伪代码进行理解“如何对节点x进行左旋”。   理解左旋之后,不妨进行一个小测验吧,如下图所示是红黑树操作过程的某个状态,现在我们要对节点0040进行左旋,自己动手尝试一下吧,答案点这里哟。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   (2)右旋
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   对节点F进行右旋,意味着将节点F变为其左孩子节点L的右孩子节点,并将节点L的右子树变为节点F的左子树。   对右旋稍微有点概念之后,可以结合伪代码进行理解“如何对节点x进行右旋”。   理解右旋之后,同样进行一个小测验,如下图所示是红黑树操作过程的某个状态,现在我们要对节点0040进行左旋,自己动手尝试一下吧,答案点这里哟。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   旋转总结:   ⒈左旋和右旋是相对应的两个概念(比较一下就会发现),理解了一个,另一个自然信手拈来。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   ⒉左旋示例图(以x为节点进行左旋):   对x进行左旋,意味着将“x的右孩子”设为“x的父亲节点”;即,将 x变成了一个左节点(x成了为z的左孩子)。因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”。   ⒊右旋示例图(以x为节点进行右旋):   对x进行右旋,意味着将“x的左孩子”设为“x的父亲节点”;即,将 x变成了一个右节点(x成了为z的右孩子)。因此,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”。   3.2红黑树添加   将一个节点插入到红黑树中,需要执行哪些步骤呢? ⑴首先,红黑树是一棵二叉查找树,节点插入规则是插入的数若小于当前节点,则往左子树深入,否则往右子树深入;⑵然后,将插入的节点着色为红色;⑶最后,通过旋转和重新着色操作来修正该树的红黑树特性。详细步骤如下:   第一步:将节点按照二叉查找树的插入规则进行节点插入。   红黑树本身就是一棵二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一棵二叉查找树的事实。   好了,那接下来,我们就想方设法通过旋转以及重新着色,使这棵树重新成为红黑树即可。   第二步:将插入节点着色为红色。   为什么着色成红色,而不是黑色呢?在回答之前,我们需要重新温习一下红黑树的特性:(1)每个节点要么是黑色,要么是红色。(2)根节点为黑色(3)每个叶子节点(NIL)均为黑色。[注:这里的叶子节点指的是空(NIL或者NULL)的叶子节点!!!](4)如果一个节点是红色的,那么它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点NIL的所有路径上包含相同数目的黑节点。[注:这里指到叶子节点的路径]   将插入的节点着色为红色,不会违背“特性⑸”。少违背一条特性,就意味着我们需要处理的情况越少。接下来,只要努力让这棵树满足其它性质即可。都满足了的话,它就又是一棵红黑树了。   第三步:通过旋转和重新着色操作来修正该树的红黑树特性。   第二步中,将插入节点着色为“红色”之后,不会违背“特性⑸”。那它到底会违背哪些特性呢?对于“特性⑴”,显然不会违背,因为我们已经将它涂成红色了。对于“特性⑵”,显然也不会违背。在第一步中,我们是按二叉查找树的规则执行的插入操作,而根据二叉查找树的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。对于“特性⑶”,显然不会违背。因为这里的叶子节点指的是空叶子节点,插入非空节点并不会对它们造成影响。对于“特性⑷”,是有可能违背的。这样分析下来,我们只要满足了“特性⑷”就可以将树重新构造成红黑树了。接下来我们一起来看一下伪代码,随后会对各种情况进行分析。   添加操作的伪代码:   结合伪代码及注释,先理解RB-INSERT节点插入过程。之后,我们对节点重新着色和旋转操作进行说明。   添加修正操作的伪代码   根据被插入节点的父节点的情况,可以将“节点z插入红黑树中并着色为红色”划分为三种情况来处理。   第一种情况说明: 被插入节点是根节点。   处理方法: 直接把该节点涂为黑色。   第二种情况说明: 被插入节点的父节点是黑色。   处理方法: 无需处理,节点插入后不影响红黑树特性。   第三种情况说明: 被插入节点的父节点是红色。   处理方法: 该情况与红黑树“特性⑸”冲突。该情况下,被插入节点必定存在非空祖父节点(原因: 被插入节点的父节点是红色,所以必定不是根节点,那么必定有一个黑色的祖父节点)。进一步说明,被插入节点也一定存在叔叔节点(即便叔叔节点是空叶子节点,我们也认为存在,因为空叶子节点本身就是黑色)。理解这点之后,我们又可以根据叔叔节点的情况进一步划分出三种情况(Case)。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   注:此表仅考虑被插入节点的父节点为祖父节点的左孩子的情况,另一种情况与之对称。   以上三种情况处理问题的核心思想都是:将红色节点移到根节点;然后将根节点设为黑色。下面将进行详细介绍。   (Case 1)叔叔节点是红色   1.现象说明   当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色   2.处理策略⑴将“父节点”设为黑色⑵将“叔叔节点”设为黑色⑶将“祖父节点”设为红色⑷将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作   下面分析一下为什么要这样处理(建议结合示意图进行理解):   “当前节点”和“父节点”都是红色,违背“特性⑷”。所以,将“父节点”染成“黑色”这点毋庸置疑。   但是,将“父节点”由“红色”染成“黑色”之后,违背了“特性⑸”:因为,包含“父节点”的这条分支的黑色节点总数增加了1。 解决这个问题的办法是:将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”。关于这里,说明几点:第一,为什么“祖父节点”之前是黑色?这个应该很容易想明白,因为在变换操作之前,该树是红黑树,“父节点”是红色,那么“祖父节点”一定是黑色; 第二,为什么将“祖父节点”由“黑色”变成“红色”,同时,将“叔叔节点”由“红色”变成“黑色”?因为这样能解决“包含‘父节点’的分支的黑色节点总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”,既然这样,我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题; 但是,这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”,现在我们已知“叔叔节点”是“红色”,将“叔叔节点”设为“黑色”就能解决这个问题。 所以,将“祖父节点”由“黑色”变成“红色”,同时,将“叔叔节点”由“红色”变成“黑色”,就解决了该问题。   按照上面的步骤处理之后:当前节点、父节点、叔叔节点之间都不会违背红黑树特性,但祖父节点却不一定。若此时,祖父节点是根节点,直接将祖父节点设为“黑色”,那就完全解决这个问题了;若祖父节点不是根节点,那我们需要将“祖父节点”设为“新的当前节点”,接着对“新的当前节点”进行分析。   3.示意图
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   过程模拟   第一步:
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   第二步:修复操作(当前节点是20,用cur表示)
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   第三步:继续对新的当前节点进行修复操作   这里因为到达了根节点,所以停止了修复,如果当前节点不是根节点,或者当前节点的父节点不是黑色节点,那么就需要继续向上修复。   第四步:继续插入新节点
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   第五步:插入新节点–再接再厉
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   这时候面临的是叔叔节点不是红色,不再满足case1的情况,继续分析。   (Case 2)叔叔节点是黑色,且当前节点是右孩子   1.现象说明   当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子   2.处理策略⑴将“父节点”作为“新的当前节点”⑵以“新的当前节点”为支点进行左旋   下面分析一下为什么要这样处理(建议结合示意图进行理解):   首先,将“父节点”作为“新的当前节点”;接着,以“新的当前节点”为支点进行左旋。 为了便于理解,我们先说明第⑵步,再说明第⑴步;为了便于说明,我们设置“父节点”的代号为F(Father),“当前节点”的代号为S(Son)。   为什么要“以F为支点进行左旋”呢?其实这里是为case 3这种情况做的准备(可以结合case 3一起理解 or 先理解case 3的策略),我们修复红黑树秉持着能少处理就少处理的原则,但是此处单纯依靠重新染色操作无法避免与“特性⑷”和“特性⑸”相违背,迫于无奈只能采取变动稍大的旋转操作。而此处的左旋是和case 3的右旋相对应的,假设我们没有进行左旋,而是对祖父节点直接进行右旋,那么只是将“违背特性⑷”的问题换了一个分支,但问题依然存在。如下图,当前节点是60,父节点是40,叔叔节点是90,祖父节点是80,若我们不对父亲节点左旋,而是直接采取case 3的操作,就会发现,问题并没有解决,只是把皮球抛给了对方。综上,这也就是这里为什么要“以F为支点进行左旋”的原因。
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   按照上面的步骤(以F为支点进行左旋)处理之后:若S变成了根节点,那么直接将其设为“黑色”,就完全解决问题了;若S不是根节点,那我们需要执行步骤⑴,即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理,而需要以F为新的当前节点来进行处理呢?这是因为“左旋”之后,F变成了S的“子节点”,即S变成了F的父节点;而我们处理问题的时候,需要从下至上(由叶到根)方向进行处理;也就是说,必须先解决“孩子”的问题,再解决“父亲”的问题;所以,我们执行步骤⑴:将“父节点”作为“新的当前节点”。   3.示意图   动图演示
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   过程模拟
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   该过程提前剧透了case 3的处理策略,可以先看看。   (Case 3)叔叔节点是黑色,且当前节点是左孩子   1.现象说明   当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子   2.处理策略⑴将“父节点”设为黑色⑵将“祖父节点”设为红色⑶以“祖父节点”为支点进行右旋   下面分析一下为什么要这样处理(建议结合示意图进行理解):   为了便于说明,我们设置“当前节点”为S(Son),“叔叔节点”为U(Uncle),“父节点”为F(Father),祖父节点为G(Grand-Father)。   目前,所有分支的黑色节点个数是一致的,现在出现两个连续红色节点S和F,那么简单点,将其中一个改成黑色节点,将父节点F变成黑色,那么以父节点F的局部子树是平衡的,但是 父节点的兄弟节点U可能是不平衡的,因为父节点F路径多了一个黑色,那么这个黑色节点放在哪里? 只能往根节点移,将祖父G变红,这样祖父G的另一个分支将少一个黑色节点,再把祖父G右旋,这样父节点F代替了原来的祖父G,也就相当于把多的黑色节点,放在了公共的祖父位置上。   示意图
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   过程模拟
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   至此,红黑树的添加操作终于完成了。   3.3红黑树删除   将红黑树内的某一个节点删除,需要执行哪些步骤呢? ⑴首先,红黑树是一棵二叉查找树,按照二叉查找树的节点删除规则删除该节点;⑵然后,通过旋转和重新着色操作来修正该树的红黑树特性。详细步骤如下:   第一步:将节点按照二叉查找树的删除规则进行节点删除。   这和“删除常规二叉查找树中的节点方法是一样的”。分3种情况:   Ⅰ.被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。   Ⅱ.被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。   Ⅲ.被删除节点有两个儿子。那么,先找出它的[前驱节点/后继节点];然后把“它的[前驱节点/后继节点]的内容”复制给“该节点”;之后,删除“它的[前驱节点/后继节点]”。在这里,[前驱节点/后继节点]相当于替身,在将[前驱节点/后继节点]的内容复制给”被删除节点”之后,再将[前驱节点/后继节点]删除。这样就巧妙的将问题转换为“删除[前驱节点/后继节点]”的情况了,下面就考虑[前驱节点/后继节点]。在”被删除节点”有两个非空子节点的情况下,它的[前驱节点/后继节点]不可能是双子非空。既然”[前驱节点/后继节点]”不可能双子都非空,就意味着”该节点的[前驱节点/后继节点]”要么没有儿子,要么只有一个儿子。若没有儿子,则按”情况Ⅰ”进行处理;若只有一个儿子,则按”情况Ⅱ”进行处理。   第二步:通过旋转和重新着色操作来修正该树的红黑树特性。   因为”第一步”中删除节点之后,可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树,使之重新成为一棵红黑树。   接下来我们一起来看一下伪代码,随后会对各种情况进行分析。   删除操作的伪代码   结合伪代码及注释,先理解RB-DELETE节点删除过程。之后,我们对节点重新着色和旋转操作进行说明。   删除修正操作的伪代码   在对删除函数进行分析之前,我们再来温习一遍红黑树的几个特性:(1)每个节点要么是黑色,要么是红色。(2)根节点为黑色(3)每个叶子节点(NIL)均为黑色。[注:这里的叶子节点指的是空(NIL或者NULL)的叶子节点!!!](4)如果一个节点是红色的,那么它的子节点必须是黑色的。(5)从一个节点到该节点的子孙节点NIL的所有路径上包含相同数目的黑节点。[注:这里指到叶子节点的路径]   前面我们将”删除红黑树中的某个节点”大致分为两步,在第一步中”按照二叉查找树的节点删除规则删除该节点”后,可能违反”特性⑵、⑷、⑸”三个特性。第二步需要解决上面的三个问题,进而保持红黑树的全部特性。   通过RB-DELETE算法,我们知道:删除节点y之后,x占据了原来节点y的位置。那么,我们面临几种形态:   a)节点y为红色;这时我们无需做任何处理,因为并未违反任何一条特性   b)节点y为黑色,x为红色;此时,在删除节点y之后,我们违背了特性⑸,y所在的子树少了一个黑色节点,那我们只需要将x染为黑色补上缺掉的这个黑色节点即可   c)节点y为黑色,x为黑色,但x是根节点;这意味着原来的y就是根节点,这样相当于是所有路径共同减少一个黑色节点,依旧满足红黑树特性,故无需处理   d)节点y为黑色,x为黑色,x不是根节点;这种形态还需要细分四种子情况进行分析:
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   (Case 1)兄弟节点是红色   1.现象说明   当前节点x是黑色,当前节点的兄弟节点是红色(此时x的父节点和x的兄弟节点的子节点都是黑色)   2.处理策略⑴将“兄弟节点”设为黑色⑵将“父亲节点”设为红色⑶以“父亲节点”为支点进行左旋⑷左旋后,重新设置x的“兄弟节点”   面分析一下为什么要这样处理(建议结合示意图进行理解):   这么做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”,从而进行进一步的处理。对x的父节点进行左旋;左旋后,为了保持红黑树特性,就需要在左旋前“将x的兄弟节点设为黑色”,同时“将x的父节点设为红色”;左旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。   或者可以这么理解,由于兄弟节点是红色节点的时候,无处借调黑节点,所以需要将兄弟节点提升到父节点,由于兄弟节点是红色的,那么兄弟节点的子节点必定是黑色的,旋转之后就可以从它的子节点借调了。   3.示意图
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   4.过程模拟
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   上图删除节点42之后,若是看着不习惯,可以把空叶子节点画出来便于理解。   (Case 2)兄弟节点是黑色,兄弟节点的两个孩子节点都是黑色   1.现象说明   当前节点x是黑色,当前节点的兄弟节点也是黑色,且兄弟节点的两个孩子节点也都是黑色   2.处理策略⑴将“兄弟节点”设为红色⑵将“父节点”作为“新的当前节点””   下面分析一下为什么要这样处理(建议结合示意图进行理解):   之所以要将兄弟节点变红,是因为如果把兄弟节点直接借调过来,两边的黑色节点数依旧不一致,这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后,虽达到了局部的平衡,但是对于父节点来说,如果父节点是黑色,不符合特性⑸;若父节点是红色,则不符合特性⑷。这样就需要回溯到父节点,接着进行修复操作。   3.示意图   类型一:父节点是红色
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   类型二:父节点是黑色
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   4.过程模拟
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   兄弟节点45的左右孩子为空,可以看做是黑色的(特性⑶)。   (Case 3)兄弟节点是黑色,兄弟节点的右孩子是黑色,左孩子是红色   1.现象说明   当前节点x是黑色,当前节点的兄弟节点也是黑色,但兄弟节点的左孩子是红色,右孩子是黑色   2.处理策略⑴将“兄弟节点的左孩子”设为黑色⑵将“兄弟节点”设为红色⑶以“兄弟节点”为支点进行右旋⑷右旋后,重新设置x的“兄弟节点”   下面分析一下为什么要这样处理(建议结合示意图进行理解):   我们处理“Case 3”的目的是为了将“Case 3”进行转换,转换成“Case 4”,从而进行进一步的处理。考虑到当前分支缺少一个黑色节点,势必要从兄弟节点借调黑色,但借走黑色之后,兄弟节点的右子树会缺少一个黑色节点,如果兄弟节点的右孩子是红色还好说,可以直接染成黑色,但如果本身就是黑色,这样就无法补充缺少的黑色,故先通过case 3转换成case 4,使兄弟节点的右孩子变红。   3.示意图
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   当前节点0040(黑色),兄弟节点0100(黑色),兄弟节点的左孩子0080(红色),兄弟节点的右孩子0120(黑色)。   (Case 4)兄弟节点是黑色,兄弟节点的右孩子是红色,左孩子颜色任意   1.现象说明   当前节点x是黑色,当前节点的兄弟节点也是黑色,兄弟节点的右孩子是红色,兄弟节点的左孩子颜色任意   2.处理策略⑴将“父亲节点”的颜色赋值给“兄弟节点”⑵将“父亲节点”设为黑色⑶将“兄弟节点的右孩子”设为黑色⑷以“父节点”为支点进行左旋⑸设置“x”为根节点   下面分析一下为什么要这样处理(建议结合示意图进行理解):   为了便于说明,我们设置“当前节点”为S(Son),“兄弟节点”为B(Brother),“兄弟节点的左孩子”为BLS(Brother’s Left Son),“兄弟节点的右孩子”为BRS(Brother’s Right Son),“父节点”为F(Father)。   我们要对F进行左旋。但在左旋前,我们需要调换F和B的颜色,并设置BRS为黑色。为什么需要这样处理呢?我们可以这样理解,左旋的实际意义是将兄弟一路的黑色节点调到当前节点一路,但还不能影响兄弟一路本身的黑色节点数。   策略⑴⑵⑷的实际效果是将右路(兄弟一路)拿取一个黑色节点到左路(当前节点一路),此时,左路黑色节点数恢复原样,但右路因为拿走了一个黑色节点导致黑色节点数-1,故策略⑶就是右路恢复黑色节点数的操作。   3.示意图
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   当前节点0040(黑色),兄弟节点0080(黑色),兄弟节点的左孩子0070(黑色),兄弟节点的右孩子0100(红色)。   四、红黑树的C++实现   下面附上C++代码及测试代码:   4.1红黑树的实现文件(RBTree.h)   4.2红黑树的测试文件(main.cpp)   4.3C++程序运行结果   红黑树是一种特殊的二叉查找树,故而数据在其内部是有序的。 ↩︎左旋小测验答案:
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   3.右旋小测验答案:
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的   
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的
红黑树的原理图怎么画出来_红黑树的原理图怎么画出来的

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/49856.html

(0)
上一篇 2024年 9月 3日
下一篇 2024年 9月 3日

相关推荐

关注微信