为什么黑了 算法：什么是红黑树
专业出黑
红黑树的定义
红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
红色节点不能连续
从任意节点出发，到其所有叶子节点的简单路径上都包含相同数目的黑色节点.
红黑树的发明过程 平衡二叉查找树
我们以这样一个数组为例 [42，37，18，12，11，6，5] 构建一棵二叉搜索树，由于数组中任意一点都可以作为二叉搜索树的根节点，因此这棵二叉搜索树并不唯一，我们来看一个极端的例子（以42作为根节点，顺序插入元素）
在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。
为了让二叉搜索树不至于太“倾斜”，我们需要构建一棵平衡二叉搜索树
可以看出，平衡二叉搜索树的搜索时间复杂度为O(logn)，避免了因为随机选取根节点构建二叉搜索树而可能造成的退化成链表的情况。下面再抄一段平衡二叉搜索树的官方定义：
平衡二叉查找树：简称平衡二叉树。是由前苏联的数学家 -和 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：
2-3树
经过上面的例子，我们可以知道，构建一颗平衡二叉搜索树的关键在于选取“正确”的根节点， 那么我们如何在每次构建平衡二叉搜索树的时候都能选取合适的根节点呢？这里就要另一种重要的树：2-3树（读作二三树），2-3树和红黑树是等价的，理解2-3树对理解红黑树以及B类树都有很大的帮助。
为什么有了2-3树还需要有红黑树呢？
既然2-3树已经能够保持自平衡，为什么我们还需要一颗红黑树呢？
首先2-3树就是一个节点有1个或者2个元素，而实际上2-3树转红黑树是由概念模型2-3-4树转换而来的。4叉就是一个节点里有3个元素，这在2-3树中会被调整，但是在概念模型中是会被保留的。
虽然2-3-4树也是具备2-3树同样的平衡树的特性，但是如果直接把这样的模型用代码实现就会很麻烦，且效率不高，这里的复杂点包括；
所以，希望找到一种平衡关系，既保持2-3树平衡和O(logn)的特性，又能在代码实现上更加方便，那么就诞生了红黑树。
也就是说：2-3树这种每个节点存储1-2个元素以及拆分节点向上融合的性质不便于代码操作。因此我们希望通过一些规则，将2-3树转换成二叉树，而且转换后的二叉树依然能够保持平衡。
红黑树实际上就是2-3树的二分搜索树表示，其中红节点于其父节点组合形成3节点，没有红色孩子节点的节点就是2节点
例如这颗红黑树中，这个红色的节点与其父节点（元素11所在的节点）组成一个3节点，这颗红黑树等价于以下的2-3树
总结：我们怎么将2-3树转换为红黑树
为什么说红黑树是“近似平衡”的
平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”可以等价为性能不会退化的太严重
二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近n 就好了。
那怎么推导红黑树的高度呢？
（1）首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？
（2）那我们现在把红色节点加回去，高度会变成多少呢？
所以，红黑树的高度只比高度平衡的AVL树的高度n仅仅大了一倍，在性能上，下降的并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。
为什么工程中都用红黑树这种二叉树？
平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？
所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树
小结我们学习数据结构和算法，要学习它的由来、特性、适用的场
红黑树它算是最难掌握的一种数据结构。不过呢，我认为，我们其实不应该把学习的侧重点，放到它的实现上。我们学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树，也不例外。你如果能搞懂这几个问题，其实就已经足够了。
所谓的动态数据结构是什么意思：
面试题 红黑树 VS 二叉平衡树 参考
面经手册 · 第6篇《带着面试题学习红黑树操作原理，解析什么时候染色、怎么进行旋转、与2-3树有什么关联》
