这回是真正的理解红黑树了(Linux内核里大量用到的数据结构，且常被二货问到)

逍遥设计自动化 · 发表于 2023-12-20 09:30:00

点击上方“C语言与CPP编程”，选择“关注/置顶/星标公众号”
干货福利，第一时间送达！

vom2htxvsr564067887138.png

最近有小伙伴说没有收到当天的文章推送，这是因为微信改了推送机制，有一部分小伙伴刷不到当天的文章，一些比较实用的知识和信息，错过了就是错过了，建议大家加个星标??，就能第一时间收到推送。

mgojilcfltp64067887238.png

小伙伴们大家好，我是飞宇。
今天分享一些干的不能再干的干货-红黑树，作为一种数据结构，红黑树可谓不算朴素，因为各种宣传让它过于神秘，网上搜罗了一大堆的关于红黑树的文章，不外乎千篇一律，介绍概念，分析性能，贴上代码，然后给上罪恶的一句话，它最坏情况怎么怎么地...

ninnsuerxlx64067887338.png

我们想，一棵二叉树怎么就是最坏情况，那就是它退化为一个链表，这样查找就成了遍历。问题是，平衡二叉树怎么会退回链表！它是怎么保持平衡的？能不能简单地阐述？当然可以！一般的讲述红黑树的资料都是直接给出黑节点相同，红节点不连续等来作为一个足够硬但是又不是太硬的约束来保证树的平衡，但事实上，它还有更加简单的理解方式。
1.查找-在高度不在宽度对于查找而言，如果一棵二叉树的高度是N，那么最多可以在N步内完成查找，这个不用解释，解释这个有点喧宾夺主了。这就是说，树的高度要尽可能矮。考虑到查找的平均情况，叶子节点到根节点的距离不能差别太大。
2.二叉树的不平衡根源一棵树在查找看来变得不平衡是因为子树的高度相差很大。
二叉树为什么会这么容易变得不平衡，很简单，因为它只有二叉，左右均有50%的概率，那么插入N个节点全部都是左节点或者右节点的概率就是50%的N次方，如果是8叉树，那么这个概率就是12.5%的N次方，哪个概率大，自己算。
3.多叉树-宽度换高度在第1节以及第2节，我们已经知道，树的宽度越大，高度越小，这样查询起来越快，Cisco路由器里不是有256叉乃至1024叉树吗？但是这样真的很好吗？对于稀疏节点，这样会严重消耗内存。
如果我们考虑CPU的MMU系统，就会知道，二级页表和三级页表的区别就在于对付稀疏地址空间的效果不同。
4.权衡-2，3树我们发现，道生一，一生二，二叉树是一个完美的开始，但是我们发现它特别容易倾斜，倾斜的时候别触摸。我们也不能一下子就上256叉树，即使那样在海量节点情况下也抗不住，因此这种盲目宽度换高度的方案没有可扩展性。我们需要找出一种动态的机制，让一棵树动态调整保持平衡。
为了更加容易找出这个机制，让它更加容易现形，暂时不断增加树的宽度，如果增加到3叉树还找不到方案，就增加到4叉树...我们说的N叉树并不是说一个节点一定有N个子节点，而是说它最多有N个子节点。
迄今为止，以前都是我自己形而上的观点，几年前我的想法就到此为止，原因在于那段时间特别郁闷，就想找出些技术上的形而上思想，可是突然自己变好了，就没有继续下去。幸运的是，我现在发现确实有这么一个方案，而红黑树就是从3叉树回退过去的。
让我高兴的是，我的思路并没有跑偏。
5.2-3树的平衡变换如果是二叉树，那么你插入一个节点，你只有最多1次机会保持子树的高度不变，如果是一个三叉树，那么就有2次机会。现在开始，我们为二叉树添了一叉，变成了三叉树。
二叉树的时候，一个节点有两个分支，三叉树的时候，有三个分支。一个点可以将区间分为两个部分区域，要想将一个区间分为三个部分区域，就需要两个点，因此三叉的情形下，节点存储的是两个点而不是一个，如下图所示：

3t3dyr5vksv64067887438.jpg

现在考虑插入一个新节点，这个2-3树怎么保持平衡。非常简单，我们知道，插入的位置一定是叶子，假设当前的树是平衡的，现在分两种情况：
1).插入的新叶子节点的父节点是一个二叉节点这种情况最简单，二叉节点变三叉节点即可，如下图所示：

22jhohjmoxc64067887538.jpg

2).插入的新叶子节点的父节点是一个三叉节点这种情况比较复杂。树总是要长高的，保持平衡的方式就是同时长高，而这是不可能的，插入一个节点只能让该节点所在的子树长高。然而，如果能将这个信息上升到根部，在根部长高，就实现了“同时长高”！
还是循着上面的那个思路，我们继续增加树叉的数量，我们把它增加到4！新节点的插入如下图所示：

pbbqwajzl1j64067887638.jpg

很遗憾，没有完成任务，但是最终我们提出了两个问题，只要解决了这两个问题，所有问题就解决了。
解决这两个问题，无疑都要牵扯到节点P的父节点以及再往上的节点，有两种可能：
可能性1：P的父节点PP是一个二叉节点
这个太爽，我们直接把P以及它的子树全部提到PP节点即可，类似B插入的情景，如下图所示：

mpjb3ptkqp264067887738.jpg

问题2解决。
可能性2：P的父节点PP是一个三叉节点
这就有点不好办了，不过有最后一击！不管怎样先把P节点以及其子节点全部上提到PP，保持最底部的平衡性，这样就可以递归解决了，此时我们又一次遇到了往一个三叉节点里面插入子节点的问题了，为了不增加树高，唯一的方式就是膨胀成一个四叉节点-宽度换高度。如下图所示：

plhfcj2un0464067887838.jpg

最后，我们发现，在递归的过程中，要么碰到了P..P是个二叉节点，此时按照问题2的解决方式将当前节点的值直接提到P...P中，其子树降低一个高度，抵消增加的高度，平衡保持，递归结束，要么递归到了根节点，此时只需要一个分裂操作即可完美结束！

6.演进到红黑树很显然，通过上面的描述，我们似乎找到了一个使树保持平衡的方案，而且是相当完美的平衡！核心就是宽度和高度之间的博弈。我们总是可以用一个宽度抵消一层高度，整个过程就是一次或者多次的一加一减，最终的结果还是0！
然而，这也不再是二叉树了，有的节点变成了三叉，并且保存了两个值，该两个值将区间分割成了三部分，是为三叉！因此在使用上就不如二叉树方便，比较操作复杂化了。事实上，将三叉节点处理成二叉节点，这棵树就成了红黑树！怎么处理呢？很简单！如下图所示：

3xcx2dlu0tm64067887938.jpg

看到了吧，红色节点就是从2-3树中分出来的，为了维持一棵二叉树而不是2-3树，必须将三叉节点变成二叉节点，这是一个宽度换高度得回退，即高度换宽度，当然代价就是不再完美平衡。
按照以上的这个变换，你自己试试看，可以变出两个连续的红节点吗？NO！还在纠结红黑树的性质概念吗？看了它的演进，你会发现，很多红黑树的复杂概念和让人没有头绪的性能都是自然而然的。下面我们来看一下它的最坏情况是什么。
还是以2-3树分析，如果在一棵2-3树中，最左边路径上的节点全部是三叉节点，而最右边路径上的节点都是二叉节点，那么把它变换成二叉红黑树之后，就会发现最左边的路径上是红黑间隔的节点，而最右边的路径上全部是黑节点，它们的高度差接近2倍。出现这样的情况是令人悲哀的，但是也是极低概率的。
红黑树的所有包括旋转等操作，都可以映射到2-3树中，而我们对2-3树以及高度和宽度之间的博弈已经足够理解了。请再次去理解红黑树吧，再看看它的性质和概念，together with左旋和右旋，是不是有一种新的体会呢？
——EOF——一个我十分佩服的朋友阿秀开发了一个互联网大厂面试真题记录网站，支持按照行业、公司、岗位、科目、考察时间等查看面试真题，有意者欢迎扫码下方二维码适用~

n4wvd0bd1bk64067888039.png

你好，我是飞宇，本硕均于某中流985 CS就读，先后于百度搜索以及字节跳动电商等部门担任Linux C/C++后端研发工程师。
同时，我也是知乎博主@韩飞宇，日常分享C/C++、计算机学习经验、工作体会，欢迎点击此处查看我以前的学习笔记&经验&分享的资源。
我组建了一些社群一起交流，群里有大牛也有小白，如果你有意可以一起进群交流。

zuhifk2swu164067888139.png

欢迎你添加我的微信，我拉你进技术交流群。此外，我也会经常在微信上分享一些计算机学习经验以及工作体验，还有一些内推机会。

le32hlxrqkq64067888239.png

加个微信，打开另一扇窗

522ykse2hwb64067888339.gif