红黑树理论学习笔记

迷南。 2024-04-08 12:46 58阅读 0赞

## 红黑树 ##

### 1、查询节点 ###

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

### 2、插入节点 ###

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

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

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

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

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

![在这里插入图片描述][9ff3b57a5d0b4a0ab8f7b4108e0bfdd9.png]

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

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

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

![在这里插入图片描述][b3109ce215d544afb9ca5b31ef115496.png]

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

1.  每个节点只有两种颜色：红色和黑色。这一条满足。
2.  根节点是黑色的。这一条也满足。
3.  每个叶子节点（NIL）都是黑色的空节点。这一条满足。
4.  **从根节点到叶子节点，不会出现两个连续的红色节点。这一条发现不满足**。
5.  从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。这一条满足。

就是上面第4条规则没有满足，所以我们此时需要调整？问题来了如何调整呢？因为直接看父节点没办法实现，所以还需要观察另外的节点，也就是新节点的叔叔节点。根据叔叔节点的颜色来调整。

##### 2.3.1 叔叔节点是红色 #####

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

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

![在这里插入图片描述][9e2d9f13d26248ae81917a2e69b53dfd.png]

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

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

![在这里插入图片描述][9c5bddfa6bb14338b8e09e704f99b648.png]

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

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

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

![在这里插入图片描述][479fd08be81344da8fa510614df89c42.png]

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

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

![在这里插入图片描述][8aa976e68f9f46d9b0b06fb0d3809878.png]

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

##### 2.3.2 叔叔节点是黑色 #####

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

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

![在这里插入图片描述][17523245a9f74d8094140547d8359b88.png]

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

![在这里插入图片描述][21ebd38f4d544d81bb71f9b0abad40e2.png]

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

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

### 3、删除节点 ###

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

删除大致分了三种情况，

#### 3.1 第一种情况：要删除的节点有零个子节点 ####

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

#### 3.2 第二种情况：要删除的节点有一个子节点 ####

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

![在这里插入图片描述][8645d0e0abbf4620992b18ca2ada2f52.png]

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

#### 3.3 第三种情况：要删除的节点有两个子节点 ####

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

![在这里插入图片描述][7712a3d919c147fb954aebb1c3031928.png]

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

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

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

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

[9ff3b57a5d0b4a0ab8f7b4108e0bfdd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0cbf5f00f5f14d028b7f2504c5092e09.png
[b3109ce215d544afb9ca5b31ef115496.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/3cd8ddb22f144ad1a33cf11f75b904b3.png
[9e2d9f13d26248ae81917a2e69b53dfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1402aa7f7eee46f8b9f5ff34f38adc91.png
[9c5bddfa6bb14338b8e09e704f99b648.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/f798ccc2709a4d53b7fb30e2296f78fe.png
[479fd08be81344da8fa510614df89c42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/cfc1bf98459a4d21883bd3dd8d3fad3b.png
[8aa976e68f9f46d9b0b06fb0d3809878.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d51613b7005f41a9a53d4794cc19f8d0.png
[17523245a9f74d8094140547d8359b88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/61616b187bbd408199e368a8e4e09c9b.png
[21ebd38f4d544d81bb71f9b0abad40e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4345b10ef88e417989575a3155672130.png
[8645d0e0abbf4620992b18ca2ada2f52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d77aa544f6894c0d8b1e478282510e0e.png
[7712a3d919c147fb954aebb1c3031928.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/22092972e4664a38a7b2dc9a4324163c.png