8分钟，复习一遍红黑树

た入场券 2024-04-08 13:43 6阅读 0赞

![46bd51f7c85347659dd86447b916d0b2.png][]

## 简单介绍 ##

### 什么是红黑树？ ###

红黑树（Red Black Tree）是一种平衡二叉搜索树。红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

> 关于AVL树可以查看我的博客:[juejin.cn/post/713638…][juejin.cn_post_713638]

### 为什么使用红黑树？ ###

红黑树相比AVL树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。

其次红黑树不像AVL树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，AVL树调平衡有时候代价较大，所以效率不如红黑树。红黑树只是做到了近似平衡，并不严格的平衡，所以在维护的成本上，要比AVL树要低。

红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上却好很多。

红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

## 红黑树的前身 234树（4阶B树） ##

它的效率不如红黑树

234树：是一种多叉树，它的每个节点最多有3个数据项和四个子节点。

节点分为3类：

*  2节点：存储1个数据项，2个子节点

![34a5b4bc2c4b4c1b913b01daf4ad2cb2.png][]

3节点：存储2个数据项，3个子节点

![25afc154693641efbe1fdc2f0b2cc51d.png][]

\- 4节点：存储3个数据项，4个子节点

![936a4a5c766d49c79a7a8810571f2ba4.png][]

### 插入操作 ###

我们将1~10依次插入到234树中，观察如何平衡调整。

首先是1~3的插入，插完以后已经变成一个4节点了。

![2552175a69c94e9ead5f028393cf56bd.png][]

接着我们插入4，但是234树最多就是4节点，不能直接接在后面了。我们需要进行一步**节点上溢**操作。上溢中间的节点2，形成一个新的二节点，然后4就接在3后面。接着插入5就直接接在4后面形成4节点了。

![c8349b3d68344e929b8cc2683e0b9947.png][]

接着插入6，由于不能超过4节点又要进行**节点上溢**了，这里4上溢，然后形成的新树和2要进行合并。

![aef56dc31136481ca5c281fa3668e93c.png][]

同理插入到8的时候也一样。

![bd832227dc394ec299018b4e0279337b.png][]

最后插入10的时候，将8进行上溢。

![ca27039ce0354b40be4055381379c17c.png][]

上溢并合并以后发现一久大于4节点，于是再将4进行上溢。

![3059baddfbb345e38f74dcb45c1e4833.png][]

最终我们的234树为

![6cd3bec77e2146a68855f028b18b35cb.png][]

### 234树与红黑树的关联 ###

左边是一棵红黑树，我们将红色节点上移到和他们的父节点同一高度上，实际上就是一棵234树。

![4b85a1f907f64d36b0248c8b1611f8b3.png][]

所以**红黑树和234树是具有等价性的**。

红黑树的黑色节点个数=234树的节点数

234树的每一个节点中：

黑色节点必为父节点，红色节点为子节点（黑色中间，红色两边）

**那么红黑树的每一种插入情况我们都可以转换为234树来理解。**

### 23树 ###

根据234树的逻辑我们可以完美套用到23树上，只需要知道234树最大是4节点，23树最大是3节点就行了。

## 红黑树的性质 ##

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉搜索树的基础上，对于任何有效的红黑树有如下性质:

*  性质1. 结点是红色或黑色。
 *  性质2. 根结点是黑色。
 *  性质3. 所有叶子都是黑色，且都为空。
 *  性质4. 每个红色结点的父节点 and 子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
 *  性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

## 234树思维理解红黑树的操作 ##

> 下面我们采用234树来辅助理解红黑树的插入操作和删除操作。

### 红黑树的插入操作 ###

如果插入的是根节点，则为黑色。

**其余情况插入的节点最开始一定为红色**。（如果插入红色节点，仅有一种冲突状况，就是可能出现连续两个红色节点，这时候只需要旋转和变色进行调整。）

红黑树的插入操作分为12种情况：

*  插入节点的父节点为黑色（4种）：**直接插入，不做调整**。因为不会影响到它红黑树的性质。

![4982067ffbf94b18a7d2815c71e2bb82.png][]

叔父节点不是红色（4种）：变色+旋转。

![f0b34c9f03ec4e99a46043bf4397d905.png][]

**对于（6)RR型** 以234树的思维进行构想，我们会把13加在12的后面，但是红黑树不能有两个一样的红节点，所以我们需要进行变色，将中间的12变成黑色，两边的节点变成红色。

![8887f9da09914bae949e4028258cf62e.png][]

光变色还是不行的，因为黑色节点必须是父节点。我们得进行一次左旋操作。

![8687776df53046199199ffd3d0585666.png][]

**对于（7)LL型** 同理上面的RR型，直接染色加右旋即可。 **对于（5）RL型** 我们实际上希望11是在10和12中间的，这样的话一次旋转操作是不够的，需要做**两次旋转**。

![1ce4e2f8c39d4e0d82ddaebb079cf146.png][]

首先插入节点染成黑色，然后插入节点的祖父节点也就是10染成红色。

![75640ef78b9d456e850dabd9080bd574.png][]

染色到此为止，接下来是旋转操作 首先是父节点12进行一次右旋

![6d1c8973e68047baaaf1bf5cab45b9c4.png][]

然后祖父节点10进行一次左旋。最终到了下图所示的状态，这个是满足红黑树的性质的。

![e3752d751520448fae6fb6b6ec1f78b8.png][]

*  
 *  **对于（8)LR型** 和上面的RL型同理，染色然后对父节点进行一次左旋，然后对祖父节点进行一次右旋。
 *  叔父节点是红色（4种上溢）：变色。

![496dce201a404d868f5533e2ed17466c.png][]

我们依旧用234树的思维来理解，这里无论是哪种情况都是肯定需要上溢的（将4抬高)

![5707f10f02a449c9a0103fb79b80227f.png][]

然后开始染色，将插入节点的父节点和叔父节点染成黑色。上溢节点4作为新节点染成红色插入到上面一层。

![7003f74ced664960aea3e6cbecbbc2ae.png][]

接着由于上溢节点在逻辑上是新插入到上一层的，于是依旧需要再用上面的方式再处理一次4这个节点。从整体上来看就是一种**递归**的形式。

其他的情况实际上都是一样的，首先将父节点和叔父节点染黑，将祖父节点染红，祖父作为新插入节点上溢，然后递归处理。（写代码的时候需要将4种情况写明，毕竟位置不同。）

### 红黑树的删除操作 ###

> 什么是**下溢**？

讲删除之前首先还是讲下溢，上溢情况我们知道是超过了4节点了需要把中间节点抬高。下溢则是原来是一个2||3||4节点，但是删除掉下面一层的节点后子节点数目和2||3||4节点需要的数目对不上了。

讲完下溢之后

[46bd51f7c85347659dd86447b916d0b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b9046bbac58c4e8a8e6d46e0f5b8f61e.png
[juejin.cn_post_713638]: https://juejin.cn/post/7136389871266070564
[34a5b4bc2c4b4c1b913b01daf4ad2cb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0d9ca29d53804eafaaeedf715390f519.png
[25afc154693641efbe1fdc2f0b2cc51d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2938a6f8f9254e4a9c525599fe679bba.png
[936a4a5c766d49c79a7a8810571f2ba4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c8cd64dac2254bbfb745d5f5bbd148a8.png
[2552175a69c94e9ead5f028393cf56bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/baca4717104644febe1cdc5c8a335145.png
[c8349b3d68344e929b8cc2683e0b9947.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1f236c49090142f7be0e4197ecfab47c.png
[aef56dc31136481ca5c281fa3668e93c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c4209e9f67904a78945af13049aa6f50.png
[bd832227dc394ec299018b4e0279337b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/279b72222dd247a5b1061d7ac086d295.png
[ca27039ce0354b40be4055381379c17c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/3fa718a60b00465ba1566f83546c1b4e.png
[3059baddfbb345e38f74dcb45c1e4833.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4643aa58793b487f9fb26d534e501674.png
[6cd3bec77e2146a68855f028b18b35cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/55ccb52ec0314733867bf88357b79401.png
[4b85a1f907f64d36b0248c8b1611f8b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d5443f51688441e98ff1539c071e63b6.png
[4982067ffbf94b18a7d2815c71e2bb82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0c4bdcc1ca8f47ff8c3f18bedb52d538.png
[f0b34c9f03ec4e99a46043bf4397d905.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e86a38cc7b5d4605bcb7c6b8e188b4c0.png
[8887f9da09914bae949e4028258cf62e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/840cf60990bc4b62ba305baa6fd2f706.png
[8687776df53046199199ffd3d0585666.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/a2c33ed6d23b4c3fa4bf0fdcecbcf776.png
[1ce4e2f8c39d4e0d82ddaebb079cf146.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0ad160b85fee41efb09db915049e9329.png
[75640ef78b9d456e850dabd9080bd574.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/5b677b291f484cf4a2ef20073ad8fa22.png
[6d1c8973e68047baaaf1bf5cab45b9c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/21e2341e5c6d4c368b6b26114b75342e.png
[e3752d751520448fae6fb6b6ec1f78b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/da3dae8d966b48f4a0748ac1d5712c4b.png
[496dce201a404d868f5533e2ed17466c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/89dcfd2a975a413a9f80cb6711e7a5e4.png
[5707f10f02a449c9a0103fb79b80227f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/9169d730494c4337b264747903c0d205.png
[7003f74ced664960aea3e6cbecbbc2ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/66abc38c8af04fb487c3a0021b71ab8a.png