14-红黑树 ReaBlackTree（未更完）

学习资源：慕课网liyubobobo老师的《玩儿转数据结构》

1、简介
2、2-3树
- 2.1、简介
- 2.2、2-3树是如何添加新结点的
3、红黑树的实现

1、简介

1.1、定义

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 O(log n) 时间内完成查找、插入和删除，这里的 n 是树中元素的数目。

1.2、用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用，如实时应用中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了 O(log n) 的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

1.3、性质

红黑树是每个结点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

结点是红色或黑色。
根结点是黑色。
所有叶子都是黑色（叶子是NIL结点）。
每个红色结点必须有两个黑色的子结点。（从每个叶子到根的所有路径上不能有两个连续的红色结点。）
从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。

下面是一个具体的红黑树的图例：

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色结点就足够了。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。

在很多树数据结构的表示中，一个结点有可能只有一个子结点，而叶子结点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用"nil叶子"或"空（null）叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些结点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有结点都有两个子结点，尽管其中的一个或两个可能是空叶子。

2、2-3树

2.1、简介

2–3树是一种树型数据结构，内部结点（存在子结点的结点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子结点没有孩子，并且有1个或2个数据元素。

如果一个内部结点拥有一个数据元素、两个子结点，则此结点为2结点。
如果一个内部结点拥有两个数据元素、三个子结点，则此结点为3结点。
当且仅当以下叙述中有一条成立时，T为2–3树：

T 为空。即T不包含任何结点。
T 为拥有数据元素a的2结点。若T的左孩子为L、右孩子为R，则
- L和R是等高的非空2–3树；
- a大于L中的所有数据元素；同时
- a小于等于R中的所有数据元素。
T 为拥有数据元素a和b的3结点，其中a < b。若T的左孩子为L、中孩子为M、右孩子为R，则
- L、M、和R是等高的非空2–3树；
- a大于L中的所有数据元素，并且小于等于M中的所有数据元素；同时
- b大于M中的所有数据元素，并且小于等于R中的所有数据元素。

2-3树实例：

2-3树是一棵绝对平衡的树，绝对平衡：从根结点到任意一个叶子结点所经过的结点数量是相同的。

2.2、2-3树是如何添加新结点的

新结点不会直接添加到空的位置，而是会和由二分搜索的添加规则所能找到的叶子结点进行融合。
紧接上一步的添加融合：
- 如果融合后是一个3结点，融合完成；
- 如果融合后是一个4结点，且当前融合后的结点是根结点，那么此时这个4结点就要拆解为3个2结点；
- 如果融合后是一个4结点，且当前叶子结点不是根结点，那么就需要先将当前这个4结点拆解为3个2结点，并将3个2结点中的根结点向上与其父亲结点做融合。
紧接上一步的向上融合：
- 如果融合后是一个3结点，融合完成；
- 如果融合后是一个4结点，且当前融合后的结点是根结点，那么此时这个4结点就要拆解为3个2结点；
- 如果融合后是一个4结点，且当前叶子结点不是根结点，那么就需要先将当前这个4结点拆解为3个2结点，并将3个2结点中的根结点向上与其父亲结点做融合；
- 向上融合的过程，直至到达根结点结束。

动态图讲解（凑合看哈^-）:

2-3

3、红黑树的实现

红黑树与2-3树是等价的：3结点 ===> 1个红结点+1个黑结点，并且规定红结点是左倾斜的。

红黑树的性质归纳：

每个结点或者是红色的，或者是黑色的
根结点是黑色的
每一个叶子结点(最后的空结点)是黑色的
如果一个结点是红色的，那么它的孩子结点都是黑色的
从任意一个结点到叶子结点，经过的黑色结点是一样的

所以红黑树是保持"黑平衡"的二叉树，严格意义上，不是平衡二叉树

3.1、保持根结点为黑色

由红黑树的性质可得根结点必定是黑色的，但结点默认是红色，所以根结点的颜色需要特别处理。

新结点就是根结点
颜色反转（对应2-3树中的向上融合到达根结点）