史上最易懂的红黑树动态图解! |
您所在的位置:网站首页 › 冰箱原理动态图解 › 史上最易懂的红黑树动态图解! |
点击蓝色“程序猿DD”关注我 回复“资源”获取独家整理的学习资料! 本文转载自公众号:日拱一兵
通过工具 (公众号回复「工具」—>那些可以提高效率的工具—>红黑树) 动态感受红黑树的转换过程 司令:你猜我买的这个多少钱?我: 1000司令: 高了我: 500司令: 低了:我: 750...... 直到最后猜中 这样说大家应该已经猜到了是「二分查找法」,通过这个例子我想要引出的是 树,来看图片
二叉查找树,Binary Search Tree 「BST」,要想了解二叉查找树,我们首先看下二叉查找树有哪些特性呢? 某节点的左子树节点值仅包含小于该节点值 某节点的右子树节点值仅包含大于该节点值 左右子树每个也必须是二叉查找树 看个图就轻松理解上面三句话的意思了: 上图,结合二叉查找树的三条约束来看,非常好,没有什么问题。再来看一个图,依旧符合上面三条约束,感觉有问题吗? 这是一个走路一米六,一米八的树 这是一个畸形的树,大风一挂很可能被折断的树 从程序的角度来说这个树不够平衡,查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长 理科生在高中学习生物时学过一个关键字「去除顶端优势」,通过去除植物顶端优势,侧芽会迅速生长,慢慢变得强壮和平衡, 红黑树其实就是去除二叉查找树顶端优势的解决方案,从而达到树的平衡 红黑树红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST),树上的每个节点都遵循下面的规则: 每个节点都有红色或黑色 树的根始终是黑色的 (黑土地孕育黑树根,?) 没有两个相邻的红色节点(红色节点不能有红色父节点或红色子节点,并没有说不能出现连续的黑色节点) 从节点(包括根)到其任何后代NULL节点(叶子结点下方挂的两个空节点,并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点 瞬间懵逼?了解一下印象就行,开始玩魔方都是要照着魔方公式一点点玩的,多玩几次就熟悉了。红黑树也一样,红黑树有两大操作: recolor (重新标记黑色或红色) rotation (旋转,这是树达到平衡的关键) 我们会先尝试 recolor,如果 recolor 不能达到红黑树的 4 点要求,然后我们尝试 rotation,其实红黑树的关键玩法就是弄清楚 recolor 和 rotation 的规则,接下来看看详细的算法公式吧 千万别着急记忆公式,有图示会逐步说明,就像魔方一样,多玩几次就懂了:假设我们插入的新节点为 X 1. 将新插入的节点标记为红色 2. 如果 X 是根结点(root),则标记为黑色 3. 如果 X 的 parent 不是黑色,同时 X 也不是 root: 3.1.1 将 parent 和 uncle 标记为黑色 3.1.2 将 grand parent (祖父) 标记为红色 3.1.3 让 X 节点的颜色与 X 祖父的颜色相同,然后重复步骤 2、3 3.1 如果 X 的 uncle (叔叔) 是红色 话不多说,看下图 跟着上面的公式走: 将新插入的 X 节点标记为红色 发现 X 的 parent (P) 同样为红色,这违反了红黑树的第三条规则「不能有两个连续相邻的红色节点」 发现 X 的 uncle (U) 同样为红色 将 P 和 U 标记为黑色 将 X 和 X 的 grand parent (G) 标记为相同的颜色,即红色,继续重复公式 2、3 发现 G 是根结点,标记为黑色 结束 刚刚说了 X 的 uncle 是红色的情况,接下来要说是黑色的情况 3. 如果 X 的 parent 不是黑色,同时 X 也不是 root: 3.2.1 左左 (P 是 G 的左孩子,并且 X 是 P 的左孩子) 3.2.2 左右 (P 是 G 的左孩子,并且 X 是 P 的右孩子) 3.2.3 右右 (和 3.2.1 镜像过来,恰好相反) 3.2.4 右左 (和 3.2.2 镜像过来,恰好相反) 3.2 如果 X 的 uncle (叔叔) 是黑色,我们要分四种情况处理 当出现 uncle 是黑色的时候我们第一步要考虑的是 旋转 ,这里先请小伙伴不要关注红黑树的第 4 条规则,主要是为了演示如何旋转的,来一点点看,不要看图就慌,有解释的?: 左左情况这种情况很简单,想象这是一根绳子,手提起 P 节点,然后变色即可 左旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的左孩子,然后再应用 左左情况 与左左情况一样,想象成一根绳子 右旋: 使 X 的父节点 P 被 X 取代,同时父节点 P 成为 X 的右孩子,然后再应用 右右情况 你说的动图在哪里,你个大骗子,别着急,现在就为小伙伴们奉上动图演示,来说明公式的使用: 案例一插入 10,20,30,15 到一个空树中 向空树中第一次插入数字 10,肯定是 root 节点 root 节点标记成黑色 向树中插入新节点 20,标记为红色 20 > 10,并发现 10 没有叶子节点,将新节点 20 作为 10 的右孩子 向树中插入新节点 30,标记为红色 30 > 10,查找 10 的右子树,找到 20 30 > 20,继续查找 20 的右子树,发现 20 没有叶子节点,将值插在此处 30 和 20 节点都为红色,30 为右孩子,20 也为右孩子,触发了 右右情况 通过一次旋转,提起 20 节点 20 节点是根结点,标记为黑色 向树中插入新节点 15,标记为红色 通过比对大小和判断是否有叶子节点,最终插值为 10 节点的右孩子 15 和 10 节点都为红色,15 的 uncle 节点 30 也为红色 按照公式,将 15 的 parent 10 和 uncle 30 更改为黑色 让 15 节点 grand parent 20 的颜色与 15 节点的颜色一样,变为红色 20 为根结点,将其改为黑色 继续插入其他节点只不过反复应用上面的公式,上面应用到的红黑树工具,可以暂停动画效果,一帧一帧的看红黑树的转换过程,这样通过练习,查看公式,观察变化三管齐下,红黑树的入门理解应该完全不再是问题了 留言交流不过瘾?添加微信:zyc_enjoy 根据指引加入各种主题讨论群 每日一问 今日问题: 妈妈准备款待客人的糖果被偷吃了。妈妈很生气,盘问4个孩子,下面是他们的回答: A:是B吃的。 B:是D吃的。 C:我没有吃。 D:B在说谎。 妈妈不知道如何惩罚这群淘气的孩子,便询问知道详情的爸爸。孩子们用哀怜的眼神看着爸爸,希望爸爸不要“出卖”他们。于是,爸爸微笑着对妈妈说:“亲爱的,不要生气了。我想他们也是一时没有管住自己的嘴。不过我不能出卖自己的孩子们,所以,我要告诉你的是,他们中有一个说了实话,有三个说了谎话。”结果,妈妈还是知道究竟是谁偷吃了糖果。你知道是谁吗? (留言说说你的答案吧,明日推文公布答案) 昨日答案:312211 (昨日问题可在昨日推文的文末查看) 推荐阅读 Spring Cloud Alibaba即将正式毕业,Netflix之后新生力量值得期待! RabbitMQ 延迟消息的极限是多少? Spring、Spring MVC、Spring Boot还傻傻分不清楚? 可能是全网最好的MySQL重要知识点 | 面试必备 开发高质量的软件要付出什么样的代价? 来星球聊聊技术人的斜杠生活 点一点“阅读原文”小惊喜在等你 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |