红黑树和平衡二叉树有关系吗_二叉树有什么用

红黑树和平衡二叉树有关系吗_二叉树有什么用最容易懂得红黑树的认识总结介绍红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍微放松逛一下限制,希望找到一个能在对数时间内完成查找的数据结构。这个时候,红

最容易懂得红黑树的认识总结   介绍   红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍微放松逛一下限制,希望找到一个能在对数时间内完成查找的数据结构。这个时候,红黑树站了出来。   对红黑树的基本理解   (一)对红黑树的基本定义理解   红黑树的英文是“Red-Black Tree”,简称 R-B Tree,它是一种不严格的平衡二叉查找树   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   红黑树中的节点,一类被标记为黑色,一类被标记为红色。除此之外,一棵红黑树还需要满足这样几个要求:   根节点是黑色的;   每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据(图中将黑色的、空的叶子节点都省略掉了);   任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;   每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;   (二)对红黑树是“近似平衡”的理解   平衡二叉查找树的初衷,是为了解决二叉查找树因为动态更新导致的性能退化问题。所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。   一棵极其平衡的二叉树(满二叉树或完全二叉树)的高度大约是 log2n,所以如果要证明红黑树是近似平衡的,只需要分析,红黑树的高度是否比较稳定地趋近 log2n 就好了。   1.将红色节点从红黑树中去掉,分析包含黑色节点的红黑树的高度   红色节点删除之后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点(父节点的父节点)作为父节点。所以,之前的二叉树就变成了四叉树。   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树。所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。   完全二叉树的高度近似 log2n,这里的四叉“黑树”的高度要低于完全二叉树,所以去掉红色节点的“黑树”的高度也不会超过 log2n。   2.把红色节点加回去,分析高度变化   在红黑树中,红色节点不能相邻,也就是说,有一个红色节点就要至少有一个黑色节点,将它跟其他红色节点隔开。   红黑树中包含最多黑色节点的路径不会超过 log2n,所以加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。   所以,红黑树的高度只比高度平衡的 AVL 树的高度(log2n)仅仅大了一倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红黑树的性能更好。   (三)红黑树与AVL树的比较:   AVL树的时间复杂度虽然优于红黑树,但是对于现在的计算机,cpu太快,可以忽略性能差异   红黑树的插入删除比AVL树更便于控制操作   红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)   二、实现红黑树的基本思想分析   红黑树的平衡过程跟魔方复原非常神似,大致过程就是:遇到什么样的节点排布,我们就对应怎么去调整。只要按照这些固定的调整规则来操作,就能将一个非平衡的红黑树调整成平衡的。总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   如上,一棵合格的红黑树需要满足的四个基本要求中,在插入、删除节点的过程中,第三、第四点要求可能会被破坏,而“平衡调整”实际上就是要把被破坏的第三、第四点恢复过来。具体分析如下:   (一)理解左旋(rotate left)、右旋(rotate right)操作   左旋就是围绕某个节点的左旋,图中的 a,b,r 表示子树,可以为空。   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体代码实现:   右旋就是围绕某个节点的右旋,图中的 a,b,r 表示子树,可以为空。   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体代码实现:   (二)插入操作的平衡调整   红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。   关于插入操作的平衡调整,有这样两种特殊情况:   如果插入节点的父节点是黑色的,那我们什么都不用做,它仍然满足红黑树的定义。   如果插入的节点是根节点,那我们直接改变它的颜色,把它变成黑色就可以了。   除此之外,其他情况都会违背红黑树的定义,需要进行调整,调整的过程包含两种基础的操作:左右旋转和改变颜色。   红黑树的平衡调整过程是一个迭代的过程。把正在处理的节点叫作节点。节点会随着不停地迭代处理,而不断发生变化。最开始的节点就是新插入的节点。新节点插入之后,如果红黑树的平衡被打破,那一般会有下面三种情况:   备注:我们只需要根据每种情况的特点,不停地调整,就可以让红黑树继续符合定义,也就是继续保持平衡。为了简化描述,把父节点的兄弟节点叫作叔叔节点,父节点的父节点叫作祖父节点。   情况一:如果节点是 a,它的叔叔节点 d 是红色   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作为:将节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色;将节点 a 的祖父节点 c 的颜色设置成红色;节点变成 a 的祖父节点 c;跳到情况二或者情况三。   情况二:如果节点是 a,它的叔叔节点 d 是黑色,节点 a 是其父节点 b 的右子节点   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作为:节点变成节点 a 的父节点 b;围绕新的节点b 左旋;跳到情况三。   情况三:如果节点是 a,它的叔叔节点 d 是黑色,节点 a 是其父节点 b 的左子节点   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作为:围绕节点 a 的祖父节点 c 右旋;将节点 a 的父节点 b、兄弟节点 c 的颜色互换,调整结束。总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   以上具体代码如下:   (三)删除操作的平衡调整   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   删除操作的平衡调整分为两步:   第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后,仍然满足最后一条定义的要求,也就是说,每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;   第二步是针对节点进行二次调整,让它满足红黑树的第三条定义,即不存在相邻的两个红色节点。   1.针对删除节点初步调整   红黑树的定义中“只包含红色节点和黑色节点”,经过初步调整之后,为了保证满足红黑树定义的最后一条要求,有些节点会被标记成两种颜色,“红 – 黑”或者“黑 – 黑”。如果一个节点被标记为了“黑 – 黑”,那在计算黑色节点个数的时候,要算成两个黑色节点。   备注:如果一个节点既可以是红色,也可以是黑色,图中用一半红色一半黑色来表示。如果一个节点是“红 – 黑”或者“黑 – 黑”,图中用左上角的一个小黑点来表示额外的黑色。   情况一:如果要删除的节点是 a,它只有一个子节点 b   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作为:删除节点 a,并且把节点 b 替换到节点 a 的位置,这一部分操作跟普通的二叉查找树的删除操作一样;节点 a 只能是黑色,节点 b 也只能是红色,其他情况均不符合红黑树的定义。这种情况下,我们把节点 b 改为黑色;调整结束,不需要进行二次调整。   情况二:如果要删除的节点 a 有两个非空子节点,并且它的后继节点就是节点 a 的右子节点 c   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作为:如果节点 a 的后继节点就是右子节点 c,那右子节点 c 肯定没有左子树。我们把节点 a 删除,并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异;然后把节点 c 的颜色设置为跟节点 a 相同的颜色;如果节点 c 是黑色,为了不违反红黑树的最后一条定义,我们给节点 c 的右子节点 d 多加一个黑色,这个时候节点 d 就成了“红 – 黑”或者“黑 – 黑”;这个时候,节点变成了节点 d,第二步的调整操作就会针对节点来做。   情况三:如果要删除的是节点 a,它有两个非空子节点,并且节点 a 的后继节点不是右子节点   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作为:找到后继节点 d,并将它删除,删除后继节点 d 的过程参照 CASE 1;将节点 a 替换成后继节点 d;把节点 d 的颜色设置为跟节点 a 相同的颜色;如果节点 d 是黑色,为了不违反红黑树的最后一条定义,我们给节点 d 的右子节点 c 多加一个黑色,这个时候节点 c 就成了“红 – 黑”或者“黑 – 黑”;这个时候,节点变成了节点 c,第二步的调整操作就会针对节点来做。   2. 针对节点进行二次调整   初步调整之后,节点变成了“红 – 黑”或者“黑 – 黑”节点。针对这个节点,再分四种情况来进行二次调整。   备注:二次调整是为了让红黑树中不存在相邻的红色节点。   情况一:如果节点是 a,它的兄弟节点 c 是红色的   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作:围绕节点 a 的父节点 b 左旋;节点 a 的父节点 b 和祖父节点 c 交换颜色;节点不变;继续从四种情况中选择适合的规则来调整。   情况二:如果节点是 a,它的兄弟节点 c 是黑色的,并且节点 c 的左右子节点 d、e 都是黑色的   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作:将节点 a 的兄弟节点 c 的颜色变成红色;从节点 a 中去掉一个黑色,这个时候节点 a 就是单纯的红色或者黑色;给节点 a 的父节点 b 添加一个黑色,这个时候节点 b 就变成了“红 – 黑”或者“黑 – 黑”;节点从 a 变成其父节点 b;继续从四种情况中选择符合的规则来调整。   情况三:如果节点是 a,它的兄弟节点 c 是黑色,c 的左子节点 d 是红色,c 的右子节点 e 是黑色   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   具体操作:围绕节点 a 的兄弟节点 c 右旋;节点 c 和节点 d 交换颜色;节点不变;跳转到 CASE 4,继续调整。   情况四:如果节点 a 的兄弟节点 c 是黑色的,并且 c 的右子节点是红色的   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)   
红黑树和平衡二叉树有关系吗_二叉树有什么用
红黑树和平衡二叉树有关系吗_二叉树有什么用   总结免费领取详细资料(技术学习路线图谱、文档等、包含视频)具体操作:围绕节点 a 的父节点 b 左旋;将节点 a 的兄弟节点 c 的颜色,跟节点 a 的父节点 b 设置成相同的颜色;将节点 a 的父节点 b 的颜色设置为黑色;从节点 a 中去掉一个黑色,节点 a 就变成了单纯的红色或者黑色;将节点 a 的叔叔节点 e 设置为黑色;调整结束。   以上具体代码可见:   总结;   最后的最后的最后,一定要尝试着自己推导一下插入删除规则啊,不然经常忘,是睡一觉起来再看就有点懵逼的那种忘。   更多学习资料(包含视频、文档等 技术学习路线图谱C/C++Linux服务器开发/后台架构师【零声教育】-学习视频教程-腾讯课堂   技术点包含了C/C++,Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等方面。   后台私信《资料》免费领取

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

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

(0)
上一篇 2024年 7月 27日
下一篇 2024年 7月 27日

相关推荐

关注微信