数据结构与算法——红黑树(上)

墨蓝 2022-11-17 13:50 209阅读 0赞

# 为什么工程中都用红黑树这种二叉树？ #

上两节，我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成  
正比，理想情况下，时间复杂度是O(logn)。  
不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2n的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间  
复杂度会退化到O(n)。我上一节说了，要解决这个复杂度退化的问题，我们需要设计一种平衡二叉查找树，也就是今天要讲的这种数据结构。  
很多书籍里，但凡讲到平衡二叉查找树，就会拿红黑树作为例子。不仅如此，如果你有一定的开发经验，你会发现，在工程中，很多用到平衡二叉查找树的地方  
都会用红黑树。你有没有想过，为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？

# 什么是“平衡二叉查找树”？ #

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平  
衡二叉树，但是非完全二叉树也有可能是平衡二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70]  
　　平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是[AVL树][AVL]，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过1，是一种高度平衡的二叉查找树。  
　但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于1），比如我们下面要讲的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。  
我们学习数据结构和算法是为了应用到实际的开发中的，所以，我觉得没必去死抠定义。对于平衡二叉查找树这个概念，我觉得我们要从这个数据结构的由来，去理解“平衡”的意思。发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。  
　所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。  
所以，如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比log2n大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。

# 如何定义一棵“红黑树”？ #

平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。它的出镜率甚至要高  
于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那我们现在就来看看这个“明星树”。  
　[红黑树][Link 1]的英文是“Red-Black Tree”，简称R-B Tree。它是一种不严格的平衡二叉查找树，我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。那红黑树究竟是怎么定义的呢？  
　顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

*  根节点是黑色的；
 *  每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
 *  任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
 *  每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

这里的第二点要求“叶子节点都是黑色的空节点”，稍微有些奇怪，它主要是为了简化红黑树的代码实现而设置的，下一节我们讲红黑树的实现的时候会讲到。这节我们暂时不考虑这一点，所以，在画图和讲解的时候，我将黑色的、空的叶子节点都省略掉了。  
为了让你更好地理解上面的定义，我画了两个红黑树的图例，你可以对照着看下。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70 1]

# 为什么说红黑树是“近似平衡”的？ #

我们前面也讲到，平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平  
衡”就等价为性能不会退化的太严重。  
我们在上一节讲过，二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是log2n，所以如果要证明红  
黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近log2n就好了。  
红黑树的高度不是很好分析，我带你一步一步来推导。  
首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？  
红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70 2]  
前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树  
就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

# 内容小结 #

很多同学都觉得红黑树很难，的确，它算是最难掌握的一种数据结构。其实红黑树最难的地方是它的实现，我们今天还没有涉及，下一节我会专门来讲。

不过呢，我认为，我们其实不应该把学习的侧重点，放到它的实现上。那你可能要问了，关于红黑树，我们究竟需要掌握哪些东西呢？

还记得我多次说过的观点吗？我们学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树，也不例外。你如果能搞懂这几个问题，其实就已经足够了。

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。

因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现，难度会有些高，这个时候，我们其实更倾向用跳表来替代它。

# （附）数据结构与算法知识点 #

![在这里插入图片描述][5735f148a4ca6f0c0ab4bad2c39fb036.png_pic_center]

# 附地址 #

[仓库地址][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70]: /images/20221022/32b6d41eabea4d2a8fe6c8b440a3e7d7.png
[AVL]: https://zh.wikipedia.org/wiki/AVL%E6%A0%91
[Link 1]: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70 1]: /images/20221022/55ccf17efdb34b5e9469c36db1178df1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70 2]: /images/20221022/592ac78adb944747b2155c75f93ac62c.png
[5735f148a4ca6f0c0ab4bad2c39fb036.png_pic_center]: /images/20221022/37fe14b7f00046e2939272383ac64045.png
[Link 2]: https://github.com/wangzheng0822/algo