C++数据结构与算法（红黑树）

墨蓝 2021-10-31 15:54 328阅读 0赞

> **前情回顾：**一棵高度为h的二叉搜索树，它可以支持任何一种基本动态几何操作，如查找、插入、删除等，其时间复杂度为O(h)。因此，如果搜索树的高度较低时，这些集合操作会执行得较快。然而，如果树的高度较高，这些集合操作可能比链表慢。红黑树（red-black tree）是许多“平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度为O(logn)。

# **Q1：什么是红黑树？** #

>  **红黑树**是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而近似于是平衡的。

**性质：**

*  树的每个节点包含5个属性：color，key，left，right，p（父节点）；
 *  每个节点不是红色的就是黑色的；
 *  根节点是黑色的；
 *  每个叶节点（NIL）是黑色的；
 *  如果一个节点是红色的，则它的两个子节点都是黑色的；
 *  对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点（黑高相同，即根节点的黑高等于红黑树的黑高）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

> 以上性质造就了红黑树确保没有一条路径会比其他路径长出2倍，因而近似于是平衡的。 又因为插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

>  **注意：**如果一个节点没有子节点或父节点，则该节点相应指针属性的值为NIL。把这些NIL视为指向二叉搜索树的叶节点（**外部节点**）的指针，而把带关键字的节点视为树的**内部节点**。

引理1：一颗有n个内部节点的红黑树的高度至多为2log(n+1)；

# Q2：什么是旋转？ #

![20190815174801976.png][]

*  用途：指针结构的修改是通过旋转来完成的。
 *  时间复杂度：O(1)。
 *  注意：在旋转过程中，只有指针改变，其他属性都保持不变。

> **前提**：在进行插入和删除之后，红黑树**必须满足**前面提到的每条性质，为了符合上面的规则，会把节点由黑变红或者由红变黑，这种操作称为**变色**。

以下变色示例只是红黑树中的一部分（注：25并非根节点）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

![20190815202327307.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

## 插入 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3][]

> **分析：**由上面的性质可知，不满足性质5和6，所以必须变色。但是，不需要整个红黑树的节点变色，只需要将待插入节点所在部分进行变色即可。

变色后：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4][]

> 出现连续两个红色节点（17和25），不符合性质5，所以变色至此已经失效，对其进行旋转操作。首先选择在13——>8——>17左旋，左旋结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5][]

> 由于根节点必须为黑色，所以进行变色：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6][]

> 其中两条路径（17——>13——>8——>1——>6——>NIL）的黑色节点个数为4不为3，所以继续选择旋转（右旋），注意17的右子树选择不变，只对左子树选择右旋：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 7][]

> 最后根据规则变色：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 8][]

> 这样，得到一颗红黑树，满足上述的所有性质。参考：[https://blog.csdn.net/mxway/article/details/29216199][https_blog.csdn.net_mxway_article_details_29216199]

## 删除 ##

1）对于红色节点，删除就好；

2）对于黑色节点，如果要删除的话，需要考虑沿着这条路径的黑色节点是否与未删除节点的所在路径的黑色节点数是否一致，不一致就需要变色。

*  如果删除的黑色节点仅有左子树或者右子树，则直接将其用它的子节点替换掉即可。
 *  如果删除的黑色节点既有左子树又有右子树，情况详见：[https://www.cnblogs.com/qingergege/p/7351659.html][https_www.cnblogs.com_qingergege_p_7351659.html]

# Q3：红黑树与AVL树的区别是什么？ #

> AVL树是一种高度平衡的二叉搜索树，对于每个节点，其左子树与右子树的高度至多差1.
> 
>  *  红黑树不追求“完全平衡”，AVL是严格平衡的；
>  *  增加或者删除节点的时引起的失衡，都需要通过旋转来解决，红黑树的复衡效率高；
>  *  AVL树比红黑树查找效率高，红黑树的查询次数最多比AVL多一次；
>  *  红黑树开销小，AVL开销大。

> **总结：若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。**

# Q4：红黑树能干什么？ #

> STL中的set/multiset和map/multimap都是基于红黑树实现的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211031/a583262095cc4af38bdd9174e4eabcbe.png
[20190815174801976.png]: /images/20211031/7c255330555a408989244ab66e47c1e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211031/4da79a2020f74bb99398d887873eabe1.png
[20190815202327307.png]: /images/20211031/447a727581234a179d6bbd7a91e4bcf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211031/acf9fe6b5c104f199cf6feec5fee0e7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3]: /images/20211031/74c31baa17044266a5fc77bc284a3150.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4]: /images/20211031/6d0858b8cdf9491cbca0e5f915688bc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5]: /images/20211031/fdc07ea7cf9049e2b333f59198532e48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6]: /images/20211031/f8f2abb90e14465982dcfda500b05184.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 7]: /images/20211031/30500ed9de0c46aca2cbc224cb018b4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 8]: /images/20211031/91a08759b2424c3ea9335af0430ede3a.png
[https_blog.csdn.net_mxway_article_details_29216199]: https://blog.csdn.net/mxway/article/details/29216199
[https_www.cnblogs.com_qingergege_p_7351659.html]: https://www.cnblogs.com/qingergege/p/7351659.html