红黑树基本操作

女爷i 2023-07-10 14:06 13阅读 0赞

很早之前就想写一篇关于红黑树的文章，但是由于担心自己理解的不透彻，就一直不敢下笔。于是在重新看了很多篇文章和资料之后，决定彻彻底底的把红黑树搞清楚。也希望让你在面试中游刃有余。OK，废话不多说，开始今天的文章。

整篇文章的思路是这样的，红黑树其实就是一种数据结构，设计它的目的就是为了高效地进行增删改查，所以我们文章的顺序也会按照这个思路来进行。我们先从二叉查找树逐渐引入到红黑树，然后再详细的讲解。你如果看过其他文章想必也一定清楚，红黑树比较麻烦，希望你有点耐心，认真理解每一张图再往下分析。

### **一、二叉查找树** ###

在正式开始了解红黑树之前呢，我们先来看一下二叉查找树的概念，从浅入深，希望你不要着急，下面就是是一颗二叉查找树：

![看了这么多篇红黑树文章，你理解了嘛？][format_png]

从这张图我们会发现如下的规律：

(1)左子树上所有节点的值均小于或等于它的根结点的值。

(2)右子树上所有节点的值均大于或等于它的根结点的值。

如果我们想要查找一个数字11，过程是怎么样的呢?

![看了这么多篇红黑树文章，你理解了嘛？][format_png 1]

上面的过程已经很清晰了，在查找的时候，先与根节点比较，比根节点大则从右子树查找，比根节点小则从左子树查找，然后重复上面的过程，一直到找到我们需要的元素为止。

这个过程是查找操作，对于添加和删除呢?其实原理也是一样的，我们第一步就是找到我们需要插入的位置，然后把元素插入即可。这样看二叉查找树挺好的呀?别着急我们继续往下看这种情况。

如果我们在刚刚开始的时候还是以9为根节点，然后依次插入13、15、17、19。我们看会发生什么情况：

![看了这么多篇红黑树文章，你理解了嘛？][format_png 2]

好好地一棵树变成了这个鬼样子，成了“一边倒”了。这时候再去查找19呢?

![看了这么多篇红黑树文章，你理解了嘛？][format_png 3]

这效率也太低下了吧，一颗二叉查找树的优势完全丧失了。怎么办呢?既然上面的二叉查找树在插入的时候变成了“一条腿”，也就是丧失了平衡，那我们干脆做出一点改进，使用平衡二叉树吧。

### **二、平衡二叉树** ###

下面就是一颗平衡二叉树。

![看了这么多篇红黑树文章，你理解了嘛？][format_png 4]

上面这颗二叉树就是平衡二叉树，也叫作AVL树。仔细分析你会发现如下特点：

(1)从任何一个节点出发，左右子树深度之差的绝对值不超过1。

(2)左右子树仍然为平衡二叉树。

现在我们再往里插入一个元素4，这时候会发生什么呢?

![看了这么多篇红黑树文章，你理解了嘛？][format_png 5]

从图中我们可以看到，插入了4之后破坏了平衡，怎么办呢?既然破坏了平衡，那就想办法纠正过来。

![看了这么多篇红黑树文章，你理解了嘛？][format_png 6]

我们发现经过调整之后，我们二叉树就重新回到了平衡。对于其他插入的情况，大家可以自己私下试一遍，最终你会发现一个结论，那就是平衡二叉树在插入时最多只需要两次旋转就会重新恢复平衡。

从上面这个过程我们会发现，平衡二叉树真的很不错，在查找时既有着二叉查找树的优越性，在插入时还能通过调整继续保持着。那么为什么还要使用到红黑树呢?我觉得可以从以下两个方面来考虑：

(1)删除：对于平衡二叉树来说，在最坏情况下，需要维护从被删节点到根节点这条路径上所有节点的平衡性，旋转的量级是O(logN)。但是红黑树就不一样了，最多只需3次旋转就会重新平衡，旋转的量级是O(1)。

(2)保持平衡：平衡二叉树高度平衡，这也就意味着在大量插入和删除节点的场景下，平衡二叉树为了保持平衡需要调整的频率会更高。

注意：在大量查找的情况下，平衡二叉树的效率更高，也是首要选择。在大量增删的情况下，红黑树是首选。

鉴于以上原因，因此我们才使用到了红黑树这种更好的结构。上面提了这么多次红黑树，相信你已经迫不及待的想要认识一下了。下面就正式拉开红黑树的序幕。

### **三、红黑树** ###

红黑树听名字就知道，里面涉及到两种颜色：红色和黑色。我们直接来看一下：

![看了这么多篇红黑树文章，你理解了嘛？][format_png 7]

上面这张图就是红黑树，你会发现他有如下特征(下面的特征最好看一个特征重新看一遍红黑树)：

(1)每个节点只有两种颜色：红色和黑色。

(2)根节点是黑色的。

(3)每个叶子节点(NIL)都是黑色的空节点。

(4)从根节点到叶子节点，不会出现两个连续的红色节点。

(5)从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

这五条就是红黑树的特征，你每看一个特征最好重新看一遍图，这样可以加深理解。这五条特征看起来真的很复杂，不过正是由于这些复杂的特征才保证了红黑树的良好特性。如何保证的呢?我们从增删改查四个角度来一个一个分析一下：

**1、查询节点**

查询节点是最简单的一个，他的查找过程和二叉查找树一样，查找元素比当前节点大，就从右子树继续查找比较，查找元素比当前节点小，就从左子树继续查找比较。查找过程就不再赘述了。

**2、插入节点**

插入节点是最麻烦的一个，它分为三种情况。我们一种一种看，这样比较有条理性。

第一种情况：新节点没有父节点

没有父节点只有一种情况，就是插入的节点是整棵树第一个节点，也就是根节点，为此我们只需要把插入节点涂成黑色就OK了。这也就保证了性质2：根节点是黑色的。

第二种情况：新节点的父节点是黑色

为此我们举一个例子，比如说上面的红黑树中，我们插入节点14。来看一下会发生什么情况?

![看了这么多篇红黑树文章，你理解了嘛？][format_png 8]

这种情况我们发现新插入节点14的父节点就是黑色的。现在为了保证红黑树的性质，我们对照每个特性来检查一遍。只要有一条不满足，我们都需要调整。我们重新对照之后会发现每一条都符合。此时不需要调整。

第三种情况：新节点的父亲节点为红色

我们还是举个例子，比如我们在最开始的红黑树基础之上插入节点21，此时会发生什么情况呢?

![看了这么多篇红黑树文章，你理解了嘛？][format_png 9]

此时还是老规矩，对照着红黑树的5个特征一个一个来看，只要是违反了一条就需要做出调整。我们来看一下：

(1)每个节点只有两种颜色：红色和黑色。这一条满足。

(2)根节点是黑色的。这一条也满足。

(3)每个叶子节点(NIL)都是黑色的空节点。这一条满足。

(4)从根节点到叶子节点，不会出现两个连续的红色节点。这一条发现不满足。

就是上面这一条规则没有满足，所以我们此时需要调整?问题来了如何调整呢?因为直接看父节点没办法实现，所以还需要观察另外的节点，也就是新节点的叔叔节点。根据叔叔节点的颜色来调整。调整的方式有两种：变色和旋转。

(1)叔叔节点是红色：

此时插入的节点是21，但是叔叔节点是27，更好是红色。我们直接来看调整的步骤：

第一步：把新节点21的父节点22变成黑色。

![看了这么多篇红黑树文章，你理解了嘛？][format_png 10]

此时重新看一下是否满足红黑树的五条特征了没，一条一条发现，第五条没有满足，也就是从任何一个节点出发，到叶子节点，这条路径上没有相同数目的黑色节点。比如从25出发。这时候怎么办呢?那就继续调整。

第二步：把22的父节点25变成红色

![看了这么多篇红黑树文章，你理解了嘛？][format_png 11]

这时候还是老规矩，不要嫌弃麻烦，因为只有经历了一步又一步的麻烦之后，你才能牢记那5条规则特征。我们对照之后会发现节点25和节点27是两个连续的红色节点，这时候又破坏了规则4。怎么办呢?那就继续调整就OK了。

难道这时候还要继续往上调整吗?如果你这样做就错了，因为不断地往上调整最后就会把根节点变成了红色，会走进死胡同。我们往下走。

第三步：把节点27变成黑色

![看了这么多篇红黑树文章，你理解了嘛？][format_png 12]

来吧，继续重新审查那5条规则特征。很明显节点17和节点25是两个连续的红色，又破坏了。是不是心太累了，调整了这么久，还是没有保证那5条规则，感觉是不是还没有平衡二叉树好。如果你现在有这种感觉，我只能说，希望你继续坚持下去，胜利就在眼前。

第四步：把节点17和节点18都变成黑色节点

![看了这么多篇红黑树文章，你理解了嘛？][format_png 13]

来来来，现在你再对照一下那5条规则，是不是完全保证了。写到这真的是太累了，和你读这篇文章的感觉一样一样的，不过这种情况也只是插入情况中的一种。继续往下看：

(1)叔叔节点是黑色：

这种情况下又分了两种情况：

第一种情况：新插入节点为父节点的左孩子

![看了这么多篇红黑树文章，你理解了嘛？][format_png 14]

第二种情况：新插入节点为父节点的右孩子

![format_png 15][]

按照第一遍的思路，我们对这两种情况执行同样的操作，最终也能保证红黑树的5条特征。

到了这一步，插入操作的所有情况就讲解完毕。另外关于左旋和右旋的知识我在这里不再说明了，因为你看到了红黑树这个程度，相信也一定看过平衡二叉树。左旋右旋哪几种情况，都会有介绍到。

**3、删除节点**

红黑树的删除说实话更加的复杂，如果你看过算法导论的话应该能明白一点，我们在这里也进行一个大概的讲解。

删除大致分了三种情况，

(1)第一种情况：要删除的节点有零个子节点

这种情况下最简单，也就是删除的是根节点或者是叶子节点(这里的叶子节点都是指非NULL的叶子节点)，根节点直接删除即可。如果叶子节点是红色的，也可以直接删除，如果叶子节点是黑色的，那么就需要进行调整，调整的步骤和插入时调整的步骤一样。

(2)第二种情况：要删除的节点有一个子节点

这时候。把子节点的值替换掉要删除的节点的值。

![format_png 16][]

现在我们的5把11替换掉之后，又回到了第一种情况。如果节点5是红色的，可以直接删除，如果节点5是黑色的，那么就需要进行调整，此时的节点5就是叶子节点。调整的步骤和插入时调整的步骤一样。

(3)第三种情况：要删除的节点有两个子节点

现在删除的节点有两个子节点，同样的我们可以执行第二种情况的操作，

![看了这么多篇红黑树文章，你理解了嘛？][format_png 17]

若节点13之前是叶子节点，那就和第一种情况一样了，如果节点13是红色的，可以直接删除，如果节点13是黑色的，那么就需要进行调整，此时的节点13就是叶子节点。调整的步骤和插入时调整的步骤一样。

若节点13之前还有子节点，那就和第二种情况一样了。那就继续替换和判断。

以上呢就是删除的情况，最后一种情况是修改，这种情况是查找和插入的结合体，也就是先找到要修改的元素，修改完值之后，继续进行调整即可。

现在还有最后一个问题了，都说红黑树很重要，为什么重要呢?我们来看一下使用场景。

### 四、使用场景 ###

红黑树的应用真的是太多了，比如说java中的HashMap和TreeMap。还有就是linux也经常使用到。这种数据结构在面试的时候是一个常问问题，希望大家能够明白和理解。如何用java手撕红黑树，在后续文章中我会添加。如有问题还请批评指正。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNC41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9iZjY5ODkzODkwMDgyYWYyYzIxYzdmMWE1MzFiMGI4YS5qcGVnLXdoXzY1MXgtc18yMjEwODI4MDU2LmpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNS41MWN0by5jb20vb3NzLzIwMTkwOS8yMy82NzY1NDczOTVhMWE1NzhiNGVjOTczMTYxM2MwNTA4MS5qcGVn?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNS41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9hODJkMTI0MTBhMjg5YTRmMjY0OTAwMmVlNjkyZGRmMC5qcGVn?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy41MWN0by5jb20vb3NzLzIwMTkwOS8yMy82ZGRlODI0OGE2ZGRlYTljMGUyM2I5MjJiNDM1ZGRjMy5qcGVn?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNC41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9jNmViMGJkYjFiMDUwMWRjMjZiZmM3ZDk3NTM2MGYzOS5qcGVn?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNS41MWN0by5jb20vb3NzLzIwMTkwOS8yMy8wNTQ1YzQ3YzY3YzljYzBkYjNjNDlmNzUyYmI2YzllOS5qcGVn?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9mMjlkNGIyMTAyNjJjNGI1ZTE0ZDhhMWU0ZGQ0M2MxNi5qcGVn?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNS41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9hNWYwMjg1NGU0MjNhZjYwMDcwZDNkNTQ2MjRjZmFiYS5qcGVn?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy41MWN0by5jb20vb3NzLzIwMTkwOS8yMy8wODg3M2M4MTNiOTY2ZTQ2Njc2ZDMzYmY2MzMyMWE2Ni5qcGVn?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi41MWN0by5jb20vb3NzLzIwMTkwOS8yMy80OGRkYjA1NjY1ZjRkNDMzOWM4YWQ5NGUxMmE1Y2NhOC5qcGVn?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNC41MWN0by5jb20vb3NzLzIwMTkwOS8yMy8wZDJmMWZkYzRjODU2ODI2YmYyODU0YTRkZmQzMjNmNC5qcGVn?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy41MWN0by5jb20vb3NzLzIwMTkwOS8yMy8zZjVjZDk2YjRjNGM1ZjZkNWVhYzFhODMwZTc1NDZmMi5qcGVn?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy41MWN0by5jb20vb3NzLzIwMTkwOS8yMy84ZmM4NGZkNzgxMmE3MzhkNjIyYjM5NDMxMWQzYTAxZS5qcGVn?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNC41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9iNGY3MDE0ZjNmMTkxNGM3NTE2ZWRlMDVmNzYxOGJjYS5qcGVn?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9jMWJhYTI1MjgwZDg4NDg3YjEwOWM0YzYxZDFiYTRmMS5qcGVn?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMi41MWN0by5jb20vb3NzLzIwMTkwOS8yMy84ODljMzMwZjZkZDE1MzNkNDkyZDBmYTQzNTRhYmE1Yy5qcGVn?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zMy41MWN0by5jb20vb3NzLzIwMTkwOS8yMy8zNmM1ZjhkZGZhZjVmYmY1OGY0ZTcwODNmMDJiZWZhMy5qcGVn?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zNS41MWN0by5jb20vb3NzLzIwMTkwOS8yMy9iOGI3Y2JkMjM0ZWVhMjZmZTM2MDhkNmMwYmI1YjEwZC5qcGVn?x-oss-process=image/format,png