关于linux:Linux内核红黑树原理概括

二叉查找树因为在频繁的动静更新过程中，可能会呈现树的高度远大于 log2n的状况，所以就会导致各个操作效率降落，最坏的状况下就会进化为链表，变为 O(n)．很显著，想要解决这个问题，无效的一种方法就是使得树的高度不要差很多，也就是均衡它。

最先创造的均衡二叉查找树是 AVL 树，（它严格合乎均衡二叉查找树的定义，即 任何节点的左右子树高度相差不超过 1，是一种高度均衡的二叉查找树。）然而在工程中，咱们常常听到的通常是 红黑树 ，而不是 AVL 树．那么 为什么工程中都喜爱用红黑树，而不是其余均衡二叉查找树呢？

其实在这里，咱们应该能有一些想法了．既然他严格依照规定执行，每次的插入，删除，都就会引发树的调整．调整的多了，天然会影响树的效率．那么红黑树又是怎么解决这个问题的呐？

其实，** 均衡二叉查找树中“均衡”的意思，其实就是让整棵树左右看起来比拟“对称”、比拟“均衡”，不要呈现左子树很高、右子树很矮的状况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

所以红黑树就是这种设计思路 (近似均衡) 了．

红黑树的定义

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的均衡二叉查找树．
顾名思义，红黑树中的节点，一类被标记为彩色，一类被标记为红色。除此之外，一棵红黑树还须要满足这样四个要求：

重要

• 1. 根节点是彩色的；
• 2. 每个叶子节点都是彩色的空节点，也就是说，叶子节点不存储数据；
• 3. 任何相邻的节点都不能同时为红色，也就是说，红色节点是被彩色节点隔开的；
• 4. 每个节点，从该节点达到其可达叶子节点的所有门路，都蕴含雷同数目的彩色节点；

这里的第二点要求“叶子节点都是彩色的空节点”，次要是为了简化红黑树的代码实现而设置的．当初，咱们临时不论这一点．

上面是两个红黑树的图例，你能够看下。

为什么红黑树是近似均衡的呐？

首先，咱们晓得二叉查找树很多操作的性能都跟树的高度成正比。一棵极其均衡的二叉树（满二叉树或齐全二叉树）的高度大概是 log2n，所以 如果要证实红黑树是近似均衡的，咱们只须要剖析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

首先，咱们来看，如果咱们将红色节点从红黑树中去掉，那单纯蕴含彩色节点的红黑树的高度是多少呢？

红色节点删除之后，有些节点就没有父节点了，它们会间接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

这时咱们能够将有些节点拿进去组成一个齐全二叉树，而齐全二叉树的高度是 log2n , 很显著，咱们的四叉树基本不会高于 log2n

咱们当初晓得只蕴含彩色节点的“黑树”的高度，那咱们当初把红色节点加回去，高度会变成多少呢？

从下面我画的红黑树的例子和定义看，在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至多有一个彩色节点，将它跟其余红色节点隔开．红黑树中蕴含最多彩色节点的门路不会超过 log2n，所以退出红色节点之后，最长门路不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度均衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，降落得并不多。这样推导进去的后果不够准确，实际上红黑树的性能更好。

OK，红黑树的原理咱们曾经晓得了，那么咱们当初就来理解一下它的实现思维

实现红黑树的根本思维

在极客工夫中老师用了魔方的例子来解说其思维，我感觉很失当．这里间接拿来用

不晓得你有没有玩过魔方？其实魔方的还原解法是有固定算法的：遇到哪几面是什么样子，对应就怎么转几下。你只有跟着这个还原步骤，就必定能将魔方还原。

实际上，红黑树的均衡过程跟魔方还原十分神似，大抵过程就是：遇到什么样的节点排布，咱们就对应怎么去调整。只有依照这些固定的调整规定来操作，就能将一个非均衡的红黑树调整成均衡的。

其实想想 AVL 树，不就是这样吗？在想想计算机，不就是一直 ” 反复 ” 的去做一些事件的吗？

和 AVL 树一样，在进行节点的插入和删除时，就会毁坏红黑树的一些 规定．在红黑树中次要毁坏的是以下两点：

• 1．任何相邻的节点都不能同时为红色，也就是说，红色节点是被彩色节点隔开的；
• 2． 每个节点，从该节点达到其可达叶子节点的所有门路，都蕴含雷同数目的彩色节点；

很显然，咱们须要也仅仅须要解决的就是如何把被毁坏了的这两点规定还原回去．在还原之前，咱们须要理解两个很重要的操作：左旋与右旋（围绕某个节点的右旋），
如图，其中 a，b，r 示意子树，能够为空。

感觉有个动画的成果是最好的了，哈哈哈～～不过也能够本人在脑中设想了啦

插入

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。所以，对于插入操作的均衡调整，有这样两种非凡状况，然而也都十分好解决。

• 1．如果插入节点的父节点是彩色的，那咱们什么都不必做，它依然满足红黑树的定义。
• 2. 如果插入的节点是根节点，那咱们间接扭转它的色彩，把它变成彩色就能够了。
• 其余：都会违反红黑树的定义，于是咱们就须要进行调整，调整的过程蕴含两种根底的操作：左右旋转和扭转色彩。

其余状况次要有三种，如果要实现，能够对应各个状况各个击破，红黑树的均衡调整过程是一个迭代的过程。就想魔方一样！！！对应规定调整就行了．

删除

删除操作的均衡调整分为两步，第一步是 针对删除节点初步调整 。初步调整只是保障整棵红黑树在一个节点删除之后， 依然满足最初一条定义的要求 ，也就是说，每个节点，从该节点达到其可达叶子节点的所有门路，都蕴含雷同数目的彩色节点；第二步是 针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

1. 针对删除节点初步调整

红黑树的定义中“只蕴含红色节点和彩色节点”，通过初步调整之后，为了保障满足红黑树定义的最初一条要求，有些节点会被标记成两种色彩 ，“红 – 黑”或者“黑 – 黑”。 如果一个节点被标记为了“黑 – 黑”，那在计算彩色节点个数的时候，要算成两个彩色节点。

这里具体有：三种状况

2. 针对关注节点进行二次调整

通过初步调整之后，关注节点变成了“红 – 黑”或者“黑 – 黑”节点。针对这个关注节点，咱们再分四种状况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

这里具体有：四种状况

发问：

1. 如何了解红黑树定义的＂任何相邻的节点都不能同时为红色＂？
   如果一个结点是红色的，则它的两个孩子都是彩色的．也就是说只有用线连起来的都不能同时是红色
2. 如何了解红黑树定义的＂每个节点，从该节点达到其可达叶子节点的所有门路，都蕴含雷同数目的彩色节点；＂？
   nullptr ．
3. 为什么插入的节点偏偏是红色呢？

将插入的结点着色为红色，不会违反“性质 4”。而少违反一条性质，就意味着咱们须要解决的状况越少。

1. 为什么红黑树的定义中，要求叶子节点是彩色的空节点？或者说是到底那里不便了？

只有满足这一条要求，那在任何时刻，红黑树的均衡操作都能够归结为下面的那几种状况。而且是简洁的．

1. 给红黑树增加彩色的空的叶子节点，会不会比拟节约存储空间呢?

一张图给你，立马明确：

1. 为什么均衡的二叉树（满二叉树或齐全二叉树）的高度大概是 log2n？？

工夫复杂度其实都跟树的高度成正比，也就是 O(height)。既然这样，当初问题就转变成另外一个了，也就是，如何求一棵蕴含 n 个节点的齐全二叉树的高度？

树的高度就等于最大层数减一，为了不便计算，咱们转换成层来示意。从图中能够看出，蕴含 n 个节点的齐全二叉树中，第一层蕴含 1 个节点，第二层蕴含 2 个节点，第三层蕴含 4 个节点，顺次类推，上面一层节点个数是上一层的 2 倍，第 K 层蕴含的节点个数就是 2^(K-1)。

不过，对于齐全二叉树来说，最初一层的节点个数有点儿不恪守下面的法则了。它蕴含的节点个数在 1 个到 2^(L-1) 个之间（咱们假如最大层数是 L）。如果咱们把每一层的节点个数加起来就是总的节点个数 n。也就是说，如果节点的个数是 n，那么 n 满足这样一个关系：

n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1) 

借助等比数列的求和公式，咱们能够计算出，L 的范畴是 [log2(n+1), log2n +1]。齐全二叉树的层数小于等于 log2n +1，也就是说，齐全二叉树的高度小于等于 log2n。

明天，对于红黑树原理先总体并且概括的介绍下吧，其实还有很多问题没有波及，我自己对红黑树原理非常的感兴趣，当初也在从事这方面的工作，所以当前有机会心愿和大家一起分享一些更粗疏全面的常识，鉴于自己程度无限，心愿大家能对文章中呈现的谬误给予批评指正，咱们一起提高……

以上材料 qqun:1106675687