就像低代码不懂零代码如何带着技术小白起飞

写在最后

最后，如果你被问到红黑树，也许你可以试着反问面试官一个问题：“您应该知道红黑树的五条定义，如果我构造一颗只有黑色节点的红黑树，这样子可行吗?因为这样子没有破坏任何一条红黑树的规则。”

如果他回答可行。

继续问：“那么请问红黑树中要红节点干什么呢?红节点的真实意义是什么呢?”

你们的故事就开始了，而我和你的算法故事也才刚开始。
 

总结

这篇文章的目的旨在从概念模型2-3树出发介绍一颗红黑树的前世今生。希望大家能够跳出枯燥的五条定义，更加本质地认识红黑树中的各种操作来源。

虽然本文只是介绍了相对简单的左倾红黑树，但是如果能够将左倾红黑树认识的很清楚，那么普通红黑树也只是多了一些情况而已。

对于还有精力阅读算法导论的读者，我给出一点自己的经验：

• 插入阶段与左倾红黑树比较相似
• 配图中的部分节点标识不太清楚，要反复对照原文阅读
• 删除阶段，算法导论中将删除黑节点X带来的黑色平衡破坏解释为，给X的子节点添上额外的一层黑色，让X的子节点变为【双重黑】或者【既黑又红】的。 我其实不太接受这种解释，经过考虑，我认为其实这个表达可以更直接一点：既然删除了某个黑色节点，那么必然会破坏以这个黑色节点为路径上的黑色平衡，表现为路径中缺少一个黑。 如果你仔细研究算法导论中的四个删除场景，会发现它们在做的事情其实都是从兄弟节点的路径想办法移动一个黑色节点过来。 因此，如果实在无法理解【双重黑】，【既黑又红】，那么直接按照“某条路径欠黑，所以要想办法补充一个黑色节点”这个思路来思考吧!
• 还是删除阶段，四个删除场景该如何记忆?我们假设删除的是某个左倾节点，其实决定场景变化的就是三个因素：这个节点的兄弟颜色;兄弟的左右儿子的颜色;这个节点的父节点的颜色。这样子粗略估计有2x2x2x2共16种情况。实际上会少很多，我们从兄弟的颜色入手。请注意如果兄弟是红色，那么当前节点的父亲和兄弟的儿子其实都是黑色。而当兄弟是黑色的时候，我们只需要满足兄弟的右儿子是红色，就能通过一次调整来实现平衡(具体请参照算法导论)。 另外提醒注意的是，一定要想好记忆的顺序。算法导论中的删除调平4种情况中，只有情况4是绝对终态，也就是说到达了这种状态后只需要一次调整绝对能达到平衡。所以我们的出发点一定是从这种状态开始，对于另外几种情况，我们要想的不是怎么去达到最终平衡，而是怎么能让它一步一步转为情况4。这样子你的思路就会清晰很多，记忆的压力也会减小。如果细心的话，你可以回想一下本文是按照怎样的顺序介绍左倾红黑树的插入的，为什么是这样的顺序?
• 一个数据结构可视化网站，它的红黑树是基于2-3-4树的，跟算法导论中基本一样(除了删除时候对前驱/后继节点的选择)，可以用它当做检验。

（编辑：鹰潭站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!