? 红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 O(log n) 时间内完成查找、插入和删除，这里的 n 是树中元素的数目。
? 红黑树和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树。
红黑树是每个结点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
下面是一个具体的红黑树的图例：
? 这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
? 要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色结点就足够了。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。
? 在很多树数据结构的表示中，一个结点有可能只有一个子结点，而叶子结点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用"nil叶子"或"空（null）叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些结点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有结点都有两个子结点，尽管其中的一个或两个可能是空叶子。
? 2–3树是一种树型数据结构，内部结点（存在子结点的结点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子结点没有孩子，并且有1个或2个数据元素。
如果一个内部结点拥有一个数据元素、两个子结点，则此结点为2结点。
如果一个内部结点拥有两个数据元素、三个子结点，则此结点为3结点。
当且仅当以下叙述中有一条成立时，T为2–3树：
2-3树实例：
2-3树是一棵绝对平衡的树，绝对平衡：从根结点到任意一个叶子结点所经过的结点数量是相同的。
动态图讲解（凑合看哈-）:
红黑树与2-3树是等价的：3结点 ===> 1个红结点+1个黑结点，并且规定红结点是左倾斜的。
红黑树的性质归纳：
所以红黑树是保持"黑平衡"的二叉树，严格意义上，不是平衡二叉树
由红黑树的性质可得根结点必定是黑色的，但结点默认是红色，所以根结点的颜色需要特别处理。
原文：https://www.cnblogs.com/sout-ch233/p/13267712.html