一文彻底理解红黑树

红黑树？好熟悉，一文理解，走起！

什么是红黑树

首先，红黑树也是一种平衡二叉搜索树，也是一种平衡树，就是不会出现严重“瘸腿”的现象，出现了就会自动触发平衡操作来维持整棵树的平衡！

为了解决二叉搜索树的平衡问题出现了平衡树，而平衡树的两大代表可以说就是AVL树和红黑树，就目前这状况，红黑树更加吃香！

既然有了AVL树为什么还要有红黑树呢？

自然是AVL还不够好，某些方面还能优化改进，首先大家应该知道，AVL树的平衡是依据平衡因子，就是左右子树高度差不能大于1，这个规则其实过于严格，带来的结果就是几乎每次的插入删除新节点都会破坏平衡！

平衡一旦被破坏就会触发自平衡操作，也就是通过左旋或者右旋来自平衡，所以在插入删除比较多的操作中，AVL会进行频繁的旋转，这就造成了性能下降，可以说，红黑树就是为了解决这个问题！

我们知道这些数据结构都是进行一步步的优化，由原先的数据结构加上新的规则然后产生新的数据机构，红黑树可以说是AVL的进一步优化吧，所以自然是多了一些规则的，红黑树具有如下特点：

1. 也是一种二叉查找树，所以具有二叉查找树的特点，也就是比左边的都大，比右边的都小
2. 根节点是黑色
3. 默认将空节点作为叶子结点，且是黑色
4. 红色节点的左右孩子必须是黑色
5. 每个节点到达其所有可达叶子节点路径上的黑色节点数量必须一致
6. 每个节点要么红色要么黑色

满足上述规则的就是一个红黑树了，画个图，直观感受一下：

这就是一个基本的红黑树了！

解读红与黑

我们直观的去看红黑树，与AVL最大的区别可能就是红色与黑色了，在红黑树中，用红色和黑色给每个节点着色，通过颜色来维持平衡！

也就是说，在红黑树中，每个节点都有一个颜色属性，也就是每个节点要么是黑色，要么就是红色，而且每个节点的红色黑色也不是随意的，而是有规则的！

比如根节点必须是黑色，然后红色节点的两个孩子必须是黑色等等，也就是红黑树的一些特性，主要就是对红色和黑色的节点分布做控制，从而达到一种平衡！

那为什么是红色和黑色而不是蓝色和绿色呢？

不知道大家有没有想过这个问题，其实吧，你叫蓝绿树也行！

什么意思呢？

红黑树这个名字自然是发明者给起的，红黑树是由R. Sedgewick和他的学弟L. J.Guibas两个人合作研究出来的！

至于为啥叫红黑树，可能他们俩都比较喜欢红黑这两种颜色吧，又或者红色和黑色对比更加明显，不像黑色和灰黑色这种，对比不明显！

那有人说了，为什么不黑白呢？岂不是对比更明显，这样说你就没有考虑打印的场景，一般纸都是白色的，你打印出来，那不就看不见了～

所以这个颜色为啥是红色和黑色，完全不用深究，我们需要关注是应该是使用两种颜色来达到维持平衡的目的！

红黑树的破坏

上面我们也说了，红黑树主要就是依据红黑两种颜色作为限制去维持一个平衡，那什么情况下，或触发自平衡，也就是什么情况下平衡被打破了，我们来看一个例子：

此时还是一颗红黑树吗？答案是的，因为现在依然符合红黑树的规则，这个时候就不用做任何调整，但是如果是下面这样：

此时就不是红黑树了，为啥？因为它破坏了红黑树的这个规则：

任意节点到该节点可达叶子结点路径上的所有黑色节点数量是一样的

咋回事，看图：

这个时候就得进行调整了，也就是会触发自平衡，通过调整重新让它符合红黑树的规则！

那该怎么调整呢？

红黑树的平衡

对于红黑树的平衡，有两种方法：

1. 通过旋转，也就是和AVL的旋转一样，左旋和右旋
2. 通过改变节点的颜色，也就是对节点重新着色

变色

我们先来看变色，现在是这样：

也就是插入了一个黑色节点31导致红黑树失衡了，怎么搞？通过变色也就是对节点重新变色来重新达到红黑树平衡！

那怎么变呢？首先插入的31是黑色节点，导致这个路径上的黑色节点多了一个，所以我们需要减少一个黑色节点，这个时候就需要把一个黑色节点给变成红色节点！

这个时候我们看，根节点20没法变，必须是黑色，然后29本身就是红色节点，咋搞，只能是黑色节点变成红色了，也就是这样：

但是这个时候也有问题了，不满足：

一个红色节点的两个孩子必须是黑色

咋搞，只能把节点29变黑了，也就是这样：

这个时候就要注意看了，此时根节点20的右子树路径上的黑色节点都是一样的，都是3个，此时会发现，左子树上的少一个黑色节点，也就是只需要把节点10变成黑色，整个红黑树就平衡了

以上就是通过变色的方式去调整使得红黑树再次达到平衡！

旋转

接下来我们再来看如何通过旋转来调整红黑树，在说之前，有必要先来了解下旋转的基础操作左旋和右旋，看图：

要记住，左旋是逆时针操作，而右旋是顺时针操作，如图：

这里有个左右旋的口诀：

左旋：左右左，也就是左旋是把该节点作为其右孩子的左孩子

右旋：右左右，也就是右旋就是把该节点作为其左孩子的右孩子

看个例子：

以上就是一个左旋的案例，也就是对节点5进行左旋，根据口诀“左右左”，就是对节点5左旋，然后将节点5作为自己右孩子节点7的左孩子，这里会遇到位置被占用的情况，那这个时候的做法就是将占用位置的节点6作为节点5的右孩子！

所以把口诀补充一下就是：

左旋：左 - 右 - 左 - 右（把赶走的节点作为该节点的右孩子）

右旋：右 - 左 - 右 - 左（把赶走的节点作为该节点的左孩子）

关于左右旋，主要的就是先搞懂旋转的方向，然后对旋转的节点依据口诀来操作，这块自己可以多练习一下，就会慢慢体会到口诀的妙处了！

接着我们来看通过旋转的操作使得红黑树达到重新平衡，看下面的一个案例：

我们看这样的一颗红黑树，此时没啥问题，不过如果我要加入一个新的红色节点21会怎样？是不是就成了这样：

这样红黑树就不平衡了，不满足：

每个红色节点的左右孩子必须是黑色节点

怎么弄？你可能会说变色啊，好，那我们试试变色，此时新插入的节点是红色节点21，变色的话那就是把其父节点24由红色变成黑色，也就是此时这样：

但是现在也出现新问题了，就是每条路径上的黑色节点数量不一致，怎么办？黑色节点25由黑变红？

这样可以了吗？答案是不可以，请一定注意看这条规则：

每个节点到达其所有可达叶子节点路径上的黑色节点数量必须一致

有人可能会说，这不是一致的吗，黑色节点不都是两个，大家一定注意了，不是这样的，不知道大家在看红黑树定义的时候有没有疑惑这条规则：

默认将空节点作为叶子结点，且是黑色

据我了解，很多人会把这个规则忽视掉，而一旦把这个规则忽视，你就会对红黑树的一些平衡产生疑问，甚至深陷其中，根据这个规则，我们把上面的情况补充下就是这样的：

我相信大家看到这个就会一眼看出问题所在吧，也就是红色节点25，它的左右子树路径上的黑色节点可是不一样的啊！发现没？

所以，我建议学习红黑树自己画图的时候最好是把黑色空节点给画出来！这样你才能真正的去理解红黑树的一些规则！避免不必要的一些误解！

那此时我们再看这个该怎么处理：

此时节点25红色，但是该节点的左右子树路径上的黑色节点不一致，在往上变色已经没意义了，所以此时要对红色节点25进行旋转操作，怎么选？可以发现它的左子树过深，所以进行右旋：

最终也就是成了这个样子：

这块一定要理解，很多人对红黑树理解的不透彻，比较模糊，有一部原因就是因为这个，为了帮助大家理解，我再继续讲解这块的要点！

重点理解

有一条红黑树的规则千万不要忽视：

默认将空节点作为叶子结点，且是黑色

这个是帮助我们更好理解：

每个节点到达其所有可达叶子节点路径上的黑色节点数量必须一致

我们继续看一个例子，假如我们从头开始构建一颗红黑树，首先插入第一个节点，红色节点24：

因为是第一个节点，所以根节点必须是黑色，因此我们需要把颜色变成黑色：

此时其实就是一颗红黑树，我们补充叶子空节点：

这样看着是不是更加顺眼，接着我们加入新的红色节点21，如图：

没啥问题，此时依然是一颗红黑树，不用做任何调整，接下来我们再次加入新的红色节点18:

此时就有问题了，不能有两个连续的红色节点，也就是每个红色节点的左右孩子必须是黑色，这个时候怎么办？

记住，红黑树失衡后，可以通过变色和旋转来重新平衡，有的时候只需要单独变色或者旋转即可以平衡，而有的时候需要两者结合才能达到平衡，如果是两者结合的话，先变色还是先旋转其实都可以，我习惯先变色

这个时候我们可以通过变色去处理，那变色有什么规律吗？

我们一般插入的新节点默认都是红色，为什么？

这是因为更好的适应红黑树的这条规则：

每个节点到达其所有可达叶子节点路径上的黑色节点数量必须一致

试想一下，如果默认插入是黑色，那一定会破坏平衡，每次插入都需要重新平衡，而默认红色就不一定每次都破坏平衡，所以默认都是插入的红色节点！

了解了这个我们继续把注意力拉回到这张图上：

此时我们新插入的红色节点18导致了红黑树失衡，然后我们通过变色，怎么变？记住，向上变，也就是变其父节点的颜色，这里就是把红色节点21变成黑色：

经过变色，现在就成了这样，要记住，此时依然是不平衡的，依然不满足：

每个节点到达其所有可达叶子节点路径上的黑色节点数量必须一致

不满足的点就是根节点24，我们称之为失衡点，那继续变色啊，此时继续向上变色，也即是把根节点24变成红色：

可以看到此时，红黑树依然不平衡，咋整？没节点可以继续变色啦，已经变到根节点了，那此时就要进行旋转了，怎么旋转，左侧深，那就是右旋，就是对根节点24（因为24是一个失衡点，左右路径上黑色节点不一致）进行右旋操作：

如此一来，红黑树重新达到平衡！

这里有几个关键点要知道：

1、要清楚为什么每次插入的都是红色节点

2、要注意存在空子树的时候是否符合任意节点路径上的黑色节点数量一致

3、可以通过变色和旋转来重新平衡，需要两者结合的时候，先变色或者先旋转都行，只要最后达到平衡即可

红黑树的删除

接下来聊聊红黑树的删除操作，直接看例子：

这是一颗正儿八经的红黑树，现在我们删除一个节点，比如删除节点31，成了这样：

直接删除即可，依然保持平衡，不用做任何操作（红色叶子节点直接删除），但是如果我们删除的是这个节点呢？

随之而来的问题就是节点13和节点20哪个与根节点25相连？

删除的节点是非叶子节点，则用对应的中序遍历的前继节点顶替要删除节点的位置，删除之后再做重新平衡的操作（如有需要）

然后我们来看该二叉树的中序遍历顺序：

这里中序遍历有个技巧，就是：

按照节点值大小从小到那排序即可

知道了中序遍历的顺序以后，我们就可以进行红黑树的删除了，比如删除节点16，那就需要找到节点16的前驱节点也就是节点13将其替代，也就是这样：

此时原本黑色节点16就被它的前驱节点也即是红色节点13覆盖了，覆盖完以后需要把原来的节点13删掉，也就成了这样：

此时发现红黑树不平衡了，就需要进行调整，怎么调整呢？自然是变色，需要把新上位的节点13从原来的红色变成黑色：

最终这样就达到了平衡，来动图感受一下：

紧接着，我们再看一种情况，还是下面这棵红黑树：

假如现在我要删除根节点25会怎样？直接动图感受一下：

根据动图我们可以发现，先找到要删除的节点25，然后就去找25的前驱节点20，将20复制一份覆盖掉要删除的节点25，然后删除掉节点20，因为节点20是红色，根节点必须黑色，所以覆盖后还需要将节点20调整为黑色，至此红黑树平衡！

对于删除，重要的就是找到要代替删除节点的新节点，删除后如果红黑树平衡遭到破坏就需要进行自平衡以达到红黑树的再次平衡！

关于红黑树的删除操作，公认是比较难且复杂的，对于学习来说，我们需要掌握最基本的红黑树规则，然后知晓一些替换技巧等，剩下的就是依据具体删除的节点去做自平衡操作，也就是删除节点后，需要进行一系列的操作将红黑树再次达到平衡！

重点推荐一个可视化网站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

小结

红黑树是个比较难的高级数据结构，我们需要掌握最核心的理论知识，理解其红黑两种颜色对平衡的制约，以及熟悉平衡树的旋转操作，剩下的就是根据情况，在红黑树平衡遭到破坏以后依据变色和旋转来重新修复红黑树，使其在此达到平衡！

对于红黑树的代码，这里不做讲解，因为的确很复杂（想看看的可以往上搜搜吗，各个语言版本都有），没必要花那个时间去研究甚至手写红黑树代码，重点是理解红黑树是怎么一回事，而不是要你可以手撸红黑树，如果面试的时候，让我手写红黑树，我只能说一句“告辞！”

对了，另外还需知晓一下红黑树的插入和删除操作的时间复杂度都是O(logN)！

ok，关于红黑树，我们就聊到这里！、

本文由哈喽比特于2年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/oTlFo_piNnqEAN0JWboMQQ