红黑树（上）：为什么工程中都用红黑树这种二叉树

------ 本文是学习算法的笔记，《数据结构与算法之美》，极客时间的课程 ------

上一节中提到，在频繁进行动态更新的情况下，二叉查找树可能出现其高度远超过\log_2 n的情况。这种现象会导致操作效率显著降低。极端情况下，这种结构可能退化为单链表形式，并可能导致的时间复杂度达到O(n)。为了应对这一问题，在算法领域中发展出了多种平衡二叉查找树方案。那么，在实际应用中究竟为什么会选择使用红黑树而非其他类型的平衡二叉查找树呢？

什么是平衡二叉查找树？

对于平衡二叉树的严格定义而言，在任何节点上其左右子的高度差都不超过1。由此可见，在上一节中提到的完全二叉与满结构实际上都属于该类别。

平衡二叉查找树不仅遵循上述二叉查找树定义的同时也具备特定的高度平衡特征。最早提出的这种高度平衡结构的是AVL（阿дель斯-韦斯-列宁）算法所对应的AVL树结构。该种数据结构完全符合我们刚刚介绍的二叉查找树定义即其任意节点左右子树的高度差不超过1单位是一种严格遵守高度平衡原则的数据组织方式

然而，并非所有的平衡二叉查找树都严格遵循上述定义（其中任意一个节点的左右子树的高度差不超过1）。例如，在下面的部分中介绍的红黑树，则允许从根节点到各个叶子节点的距离中最长的那个比最短的那个长出一倍。

为了更好地应用于实际开发过程中所需的各类技术问题, 我们掌握数据结构与算法的知识是为了能够高效解决问题. 其实不然, 我认为不必过分追求细节. 关于平衡二叉查找树这一概念, 我认为我们应该深入理解其发展背景, 以把握其内在逻辑.

创造平衡二叉查找树的目的在于缓解普通二叉查找树在频繁增删操作下的时间复杂度问题

为了更好地理解，在平衡二叉查找树中‘平衡’这一概念的具体含义时，请注意以下几点：其核心在于确保左子树和右子树的高度尽可能接近。这种特性不仅体现在整体结构上（即左子树与右子树的高度差不应超过一），而且还允许左子树高度较高而右子树较低的情况存在。这种结构安排有助于整体高度保持相对较低状态，并因此使得这些基本操作（如插入、删除和查找）的时间复杂度得以维持在一个较高的效率水平。

鉴于此，在构造一个新的平衡二叉查找树时，请确保其高度远超 log_2n（例如维持在数量级范围内）。然而它并不完全满足我们之前所定义的严格平衡二叉查找树的标准。不过我们仍可认为这种构造结果是一个可接受的平衡二叉查找树。

如何定义一棵红黑树？

实际上存在多种类型的平衡二叉查找树（Binary Search Trees），例如伸展树（Splay Tree）和堆（Treap）。然而，在我们的讨论中，“平衡二叉 tree”这一术语通常指代的是红黑 tree（Red-Black Tree）。这种数据结构因其普及程度之高而闻名，在相关领域中占据了重要地位

英语中被称为"Red-Black Tree"；通常简称为R-B Tree；它是一种"loose"意义上的平衡二叉查找树；如前所述；其定义并不完全符合"strictly balanced binary search tree"的标准；那么红黑树的空间是如何定义的呢？

按照名称，在红黑树中的节点中，按照颜色将它们分为两类：一类以黑色标记,另一类以红色标记.除了这些之外,在构建和维护红黑树时还需满足以下几点要求:

• root node is a black node；
• leaf nodes are empty (NIL) and can be inferred that they do not store any data；
• adjacent nodes must not be both red nodes, which must be separated by black nodes；
• for each node, all paths from the node to its reachable leaves are required to contain the same number of black nodes.

这里的第二点要求‘所有叶子节点被定义为空且涂成黑色’显得有些不寻常。这一设定的主要目的是为了简化代码实现过程。在本节中暂不对这一细节进行深入讨论，在绘图与讲解时我会省略这些黑色空节点。

为了帮助您更清晰地掌握上述定义的内容，请允许我为您绘制两棵红黑树的具体示意图。您可以参考这些图表进行分析与理解。

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

在之前的讨论中提到过，在动态更新过程中导致查找效率降低的现象是二叉查找树的一个局限性。因此，“平衡”特性意味着在每次更新后都能保持高效的查找能力。“近似平衡”状态则表示其查找效率的下降程度得到了适当的控制。

一棵高度严格满足O(\log_2 n)条件的完美或完全平衡的二叉树（即满二叉树或完全二叉树），因此，在证明红黑森林具有近似平衡性时，只需关注其高度是否稳定趋近于\log_2 n。

下面分析一下，在删除所有红色节点后的情况中, 单纯由黑色节点构成的红黑树其高度是多少?

红色标记的单元格被移除后，在某些情况下不再拥有直接上级单位, 这些被移除后的单元格则会采用这些被移除前该层所有单元格的上层上级作为新的父级. 因此原先基于二叉树的数据结构也演变为四叉树.

在红黑树定义中指出：任何两个可达叶子节点之间的路径上的黑色内结点数量保持一致。在此基础上，在原始四分法结构中选取特定分支并将其移至叶层位置后，该结构转变为标准完全二叉体形式。由此可知，在具有相同数量黑色内结点的情况下，所述特殊形态下的四分法结构高度显著低于对应标准完全二叉体的高度。

在上一节中提到，在计算机科学中完全二叉树（Complete Binary Tree）的高度大致为\log_2N。然而，在本节所讨论的四色"黑体"字系统（Quaternary Black-Body-like Structure）中发现其高度将低于标准二叉体（Standard Binary Tree），因此去除红色节点后的"黑体"字系统高度仍不超过\log_2N。

我们现在已经知道了只包含黑色节点的"黑树"的高度。那么，在将红色节点重新调整之后,其高度将会变为多少呢?

根据上述红黑村的例子及其定义，在红黑树结构中

因此，在高度上, 红黑树仅超出高度平衡的 AVL 树 (log2n) 约一倍. 其性能优势并未显著减少. 这一推论的结果略显粗略. 然而, 在实际性能方面, 红黑树表现更为卓越.

解答开篇

在之前的讨论中涉及了多种平衡二叉查找树。接下来我们将探讨，在工程实践中为何普遍采用红黑树作为一种高效的平衡二叉查找树？

我们之前讨论过的Treap和Splay Tree在大多数情况下运行效率很高；然而，在极端情况下的时间复杂度可能会显著增加。虽然这种极端情况发生的概率较低，在对单个操作的时间要求极高的场合下（如在线算法设计），这些数据结构并不适用）。

AVL树被定义为一种严格平衡的二叉树结构，在这种设计下确保了高效的查找操作速度。然而尽管其查找效率很高，在维护数据以维持严格平衡这一目标时却需要承受较高的维护成本。具体来说，在每次插入或删除数据节点后都需要进行相应的调整工作这使得这一过程相对来说较为复杂且耗时。因此对于那些需要频繁执行大量插入和删除操作的应用场景而言，在选择数据存储结构时可能会对 AVL 树的成本效益产生一定的考量

红黑树仅实现了大致的平衡状态，并未严格维持完美的平衡结构；因此，在维护成本方面相比AVL树而言更为经济。

所以，在红黑树中实施插入运算、删除运算和查找运算等各类操作时都能保持良好的稳定性表现。在实际应用中会遇到多种复杂情况需求，在这些情况下为了应对这些复杂情况并选择一种能够支持这些需求的平衡二叉查找树结构，则更适合采用AVL树的形式来实现这一目标。

内容小结

很多的人都认为红黑树非常困难。确实它在复杂的数据结构中算作最为高深难以掌握的一种。其实其核心难点在于实现我们今天还没有涉及下一节会专门讲解相关内容

然而，在我的观点中，并非应当将重点放在实现细节上。我们学习数据结构与算法时应关注其起源、特性及其适用场景和能够解决的问题。对于红黑树这一具体的数据结构而言，在深入理解其四个关键方面后便已足够掌握这一知识点的核心内容

红黑树属于一类称为平衡二叉查找树的数据结构。为了优化普通二叉查找树在数据更新时可能出现的性能问题,人们提出了红黑树这一改进方案。其高度接近log2n值时,则被视为大致平衡状态;这种特性使得红黑树在进行插入、删除以及查找操作时,均具备O(log n)的时间复杂度

由于RB Tree是一种性能卓越的二叉查找树，在实际工程应用中涉及动态数据插入、删除以及快速查找操作时都可以采用该数据结构作为基础框架。然而其实施过程较为复杂因此考虑采用更为高效的替代方案——跳跃列表（Jump List）来解决相关问题。