红黑树(超详解)

前言

上一篇文章我们讲了AVL树,但是AVL树只是一个过渡,我们实际当中用的更多另外一颗树还是红黑树.

也不能说红黑树就是AVL树的改进,它是用另外一种方式来控制.
这棵树更抽象一些,下一步我们来看一下.

红黑树的概念

红黑树它也一样,它是一颗搜索二叉树.
它在这个基础上,每个结点增加了一个存储颜色,
这个颜色不是红色就是黑色.所以它就叫红黑树

红黑树有两层隐含的意思:
1.它是搜索二叉树
2.它用颜色控制了每个结点

红黑树到底要干嘛呢?
它换了一种思路来控制平衡, 它为什么要换一种方式呢?
我们往后学了再来看,再来跟AVL树进行对比.

红黑树是要控制这里的颜色达到它的任意一条路径都不会超过其他路径的二倍.
它不是严格平衡,它是一个近似平衡.

注意,AVL树就是搜索二叉树最好的平衡,因为它左右高度差不超过1.

再接着,红黑树是什么呢?
你可以认为AVL树是天才设计的, 红黑树就是天才中的天才设计的.
你可以这样认为,它觉得AVL树太严格了, 它另辟蹊径找了另外一种方式来控制平衡,
保证最长路径不超过最短路径的二倍
它保持的是一个近似平衡

它怎么做到的呢?

看这四点就能保证最长路径不超过最短路径的二倍,为什么?
它通过多点规则的约束来达到这个目的.

这四条规则分别约束的是什么呢？

下面：

我们这里可以用极端场景来分析这里的问题：

这个时候，最长就是最短的2倍，但是这个时候不一定有最长的，也不一定有最短的。
那就剩下的路径都在这个中间

我们先画一棵树，每条路径都有相同数量的黑色结点
假设每条路径都有3个黑色结点，单把黑色结点拿出来它就是满二叉树

如果你想把这棵树再进一步处理一下，想让这颗树变成红黑相间

红黑相间什么样子呢？
我们想加结点，我们反过来去推，
我们不能加黑，因为加黑整条路径都得加

只能加红，一条路径最多加成类似这个样子

当然这个形状怎么变就要看这块的控制了

红黑树还有一条性质：
每个叶子结点都是黑色的（此处的叶子结点指的是空结点）

为什么要把空结点都认为是黑的？
每条路径下都有一个空结点，空结点是黑的，相当于每条路径下都增加一个黑结点，
但这些空结点不会影响黑结点数量的概念。

但是为什么要加这个黑结点呢？
看下面这棵树，有多少条路径？

这颗树不是6条

如果你认为有6条，那看一下下面这颗树是不是红黑树？

看起来好像没问题，每条路径都有相同数量的黑节点。
但是这棵树不符合红黑树的条件，每条路径黑色结点的数量不相等
他不能保证这里的规则

什么时候才能算路径呢？
一定要记住，不是走到叶子，而是走到空才能算一条路径。
所以红黑树的最后一条性质这样说：
每个叶子结点都是黑色的（此处的叶子结点指的是空结点）
也叫做NIL，图上标的NIL是为了让你更好的认清路径。

一共有11个NIL,所以上面的路径有11条

当然第五点它的概念还有一个相辅相成的意义，
如果它是一颗空树，根节点是空，根节点也是黑的

红黑树设计的人抽象思维真的是很好的，它通过约束几点规则，
把最短路径和最长路径约束出来，剩下路径都在这之间。

注意：
实际当中不一定最长路径，不一定有最短路径。

红黑树的意义

全黑有些情况不是满二叉树，我们待会再看
待会旋转的时候我们会看到其他的情况

单纯的增删查改的效率，红黑树比不上AVL树，
因为AVL树很接近完全二叉树，它是相对而言比较严格的logN
红黑树结点个数N算的只是黑色结点，不过也还好，一共才2N

大概要找多少次？

30次和60次差别大不大是相对不同的场景来区别的
从单次的角度来说，对于cpu而言一点差别都没有，cpu在二叉树查找，
理论上来说能接近上万次

红黑树有没有什么优势呢？
它没有那么严格，它不是严格平衡，它是近似平衡。
它的优势就是旋转的更少。

我们做个简单的比方：
首先下面这颗树是符合红黑树的条件的

严格平衡是通过大量的旋转的代价来达到的。
红黑树的话，相对没那么严格，性能也不弱于AVL树。

单论查找AVL树更好，但是这个好跟红黑树在同一量级，基本上影响不大
但是综合而言，红黑树更胜一筹
所以实践当中我们更喜欢用红黑树，AVL树也有人用，但是很少

红黑树的实现

红黑树的结构

红黑树也要用三叉链，因为待会涉及一些旋转更新的问题

这里红黑树还涉及一个颜色，我们用一个枚举，不用枚举也可以，用枚举稍微好一点点

这样就能保证一个结点不是红色就是黑色

红黑树的性质中，第三点和第四点是最重要的

红黑树前面的动作都跟AVL树是一样的
红黑树的实现，我们得好好实现，后面我们用来封装map和set

insert

前面这些都一样，搜索树的规则等等这些。
我们可以先把AVL树在更新平衡因子前都可以直接的拿过来。
前面搜索树叶插入规则都一样

刚插入一个结点，这个结点的颜色是黑色

问大家一个问题，如果新增一个结点，宁愿是红色的还是黑色的？
新增红还是黑是违反红黑树规则第3点还是第4点的问题。
我们肯定是违反规则3而不是规则4，因为插入黑色的结点一定违反规则4，
因为插入黑色结点不管哪个路径都有问题。

违反规则3就不一定了。
首先插入的是6这个位置，插入到这个红节点的下面
会影响当前这个局部，但是比违反规则4轻很多

还有一种情况，就是插入到11这个位置，插入到这个黑结点的下面，没有什么影响

所以我们一定新增红色结点，如果我们创建结点就把它新增成红色的。

新增是红色的，我们只需要去看这棵树是不是在这个新增的地方违反了规则。
怎么看呢？
只需要看父亲结点，如果父亲是黑的，直接可以不玩了
如果父亲是红色的，就需要处理一下

那这个时候具体怎么办呢？
红黑树在这里也分了很多点规则

大家看下面两个新增结点的位置，这两个新增结点的三个结点的关系都是固定的，
甚至暂且都可以不关心形状。

父亲是红的，父亲就一定不可能是根，因为根一定是黑的，
所以一定有祖父，祖父肯定是黑的

并且它们的位置关系都没有那么重要，你看下面假如插在这个位置，
它的形状可能是这样的，无所谓

那这个时候大家怎么想办法去处理呢？大家可以先观察一下，
直线，折线，怎么处理一下呢？

红黑树虽然比较抽象，但是红黑树的操作比AVL树简单一点点

我们看第一颗树，右边这个场景，怎么调整呢？

首先有一个很重要的结点，parent必须变黑

大家可能有个疑问，parent变黑不是相当于增加一个黑结点吗？
是的，但是你要想办法解决这个问题，因为panrent不变黑解决不了这里的问题。

parent和cur必有一黑
不可能是cur变黑，如果cur变黑，那不就把我们之前讲的所有东西都打乱了，
那我们还插入红结点干嘛，直接插入黑结点不就行了

那parnet变黑之后，咋办呢，还不符合我们的需求
这条路径多了一个黑结点。

这里的关键就是看这个uncle结点，
也就意味着红黑树的调整关键在于这个uncle结点

叔叔又有好几种情况，比如叔叔是红色的或者叔叔不存在，
这里我们只看颜色，不看形状

第2种情况和第3种情况最简单
把父亲变黑，叔叔也变黑，把祖父变红

但是这样处理以后，又引发了什么问题？
这样处理保持黑色结点数量不变

大家看，我祖父是黑的，你现在把它变红，
这个时候祖父的父亲有两种情况，如果祖父的父亲是黑的，怎么办呢？
假设是黑的就不用处理了。

假设祖父的父亲是红的，那就还得继续处理，怎么处理呢？
把祖父当作新增结点，继续算它的父亲，它的祖父。

再去看它的叔叔，如果叔叔存在且为红，继续刚才的处理，
如果叔叔不存在或者为黑那就为其他情况

注意，祖父还要变红，因为它有可能继续是子树，这里不知道它是不是子树，
最后如果发现它不是子树，它是根

再往上去看它有没有父亲，如果它有父亲，如果是红的，就继续处理。
如果它没有父亲，再处理一下，把根变成黑

大家仔细看一下，现在这颗树就是红黑树
大家看一下，黑色结点单拿出来不一定是满二叉树，
但是你可当成这个理解，很接近，影响不大

大家看，变色完了之后还有一个问题
我们再插入结点，除非在最右边和6这个位置，剩下这个位置都可以直接不用处理了了

叶子结点大多都是黑的的时候，其实非常棒，因为你插入一个结点之后，
几乎不需要动

这种变色是不需要关注形状的

我们再来看剩下一种情况，我带大家先看一下大情况，
我们待会再来看整体的情况分析

上面第一种情况变色就可以，第二种情况变色就搞不定了

我们可以看到叔叔不存在
叔叔不存在就不能把父亲变黑，但是我们前面说过红黑树百分之百
要把父亲变黑的，不把父亲变黑这个地方难以处理。

父亲变黑凭空多了一个黑结点，怎么办呢？

之前的玩法是父亲变黑，叔叔也变黑，再把祖父变红，整个路径是不会有任何影响的，
只是说它的处理还没有完全结束，我们还需要继续往上处理。

现在这种情况没办法了，那怎么办呢？
大家应该看到另一个层面，这一块也引发了它出现了另外一个问题，
它的最长路径已经可能超过最短路径的二倍了

有连续的红结点时可能导致最长路径超过最短路径的2倍
我们假设这棵树存在最短路径，也就是两个黑色结点，其实这条路径已经超了

超了只有一个方式能帮你降高度，那就是旋转

所以上面这种情况变黑之后的下一步就是旋转
把它的左给祖父的右，把祖父给它的左

然后再把祖父同时变红就好了

当然这里可能时左单旋，也可能是右单旋还可能时双旋，大家注意一下。

下一步我们开始看抽象图，抽象图看完我们就可以写代码了
严格来说分为5种情况，我们这里分了三种

叔叔存在且为红

这是抽象图，我们把它的具象图画一画让大家感受一下

我们把刚才的代码写出来，刚才的代码写起来其实也不复杂

它可能会继续往上处理

那这个时候怎么办？得先找到叔叔。
找叔叔之前得先找到祖父，祖父一定存在，因为父亲是红的，
不可能是根

第一种情况，叔叔存在且叔叔的颜色为红色
我们按照前面讲的来写代码

我们做一个双保险，不管是哪种情况，我们把根一定变成黑的。

第二种情况，叔叔有可能不存在，也可能存在且为黑
这里又有这些情况，第一种

第二种，它是一定是情况1变过来的，因为cur一定不可能是红的，
因为父亲是红的，这个位置如果是红的新增，那之前必然就不是红黑树了

它也是很多情况的组合，这种情况怎么办呢？

大家看上面 ，最短路径是2，最长路径已经超过最短路径的2倍了，
所以我们旋转+变色，只是看它是哪种旋转的问题

我们实时都在做一件事情，保持黑结点的数量不变

总结

情况三
这种情况也是跟情况二类似的，叔叔也是不存在，
情况二是单旋， 它是双旋，情况二可能是左单旋也可能是右单旋，我们只讲了左单旋

它也分两种情况，跟情况一 一样，
叔叔存在它也是从情况一变过来的

d,e要门是空，要么是一个红结点

当然还有一种情况，这个位置不只有一个黑结点，它也有可能有两个，
它可能情况一不只是变一次，也可能变两次三次

如果分析清楚了，红黑树是比AVL树更简单的

其实仔细看，大前提就分为三种情况
第一种：叔叔存在且为黑，把它两变黑，
父亲和叔叔变黑是为了替换祖父的黑，
祖父变红是为了保持这条路径黑色结点的数量不变，当然可能继续向上调节

注意，只要不旋转就不涉及是直线还是折线

第二种，叔叔不存在或者叔叔存在且为黑
这个时候无非就是单旋还是双旋的问题

接下来我们对照着上面讲的，把代码写一写

单旋

如果旋转以后，根改了，我们要不要改它呢？
这个你不用担心，旋转一定会帮你处理干净的。