首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
二叉查找树是最常用的一种二叉树，支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下时间复杂度是$O(logn)$。
不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 $O(n)$。为了解决这个问题，需要设计一种平衡二叉查找树。
常用的平衡二叉查找树是红黑树，为什么工程中都喜欢红黑树，而不是其他平衡二叉查找树呢？
什么是“平衡二叉查找树”？
平衡二叉树的严格定义为：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
节点的高度：节点到叶子节点的最长路径。树的高度：跟节点的高度。
所以，完全二叉树、满二叉树其实都是平衡二叉树，但非完全二叉树也有可能是平衡二叉树。如下所示：
平衡二叉查找树不仅满足平衡二叉树的定义，还满足二叉查找树的特点。最先提出的是AVL树，严格符合平衡二叉查找树的定义，是一个高度平衡的二叉查找树。
但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如红黑树。
其实不需要去死扣定义，设计平衡二叉查找树的初衷为：解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
所以，对于一种平衡二叉查找树，只要树的高度不比$log_2n$大很多（比如树的高度仍然是对数量级的），就是一个合格的平衡二叉查找树。
如何定义一棵“红黑树”？
因为红黑树被广泛提及，所以我们默认平衡二叉查找树是红黑树。红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它的定义并不严格符合平衡二叉树的定义。
红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
第二点是为了简化红黑树代码实现而设置的，这个之后再详细阐述。这节暂时不考虑这一点，下面图和讲解中，将黑色的空叶子节点均省略掉了。红黑树如下所示：
如何理解红黑树的定义
看到这么麻烦的红黑树的定义，想必大家都是一头雾水。那么如何理解红黑树的定义呢？这个问题原作者并没有说。以下内容来自清晰理解红黑树的演变—-红黑的含义。
我们都希望二叉查找树的结构都是矮矮胖胖的，如下如所示：
而不是这样的：
在这种需求下，平衡树的概念就应运而生了。红黑树就是一种平衡树，它可以保证二叉树基本符合矮矮胖胖的结构，但是理解红黑树之前，必须先了解另一种树，叫2-3树，红黑树背后的逻辑就是它。
2-3树是二叉查找树的变种，树中的2和3代表两种节点，以下表示为2-节点和3-节点。
- 2-节点即普通节点：包含一个元素，两条子链接。如下所示：
- 3-节点则是扩充版，包含2个元素和三条链接：两个元素A、B，左边的链接指向小于A的节点，中间的链接指向介于A、B值之间的节点，右边的链接指向大于B的节点。如下所示：
在这两种节点的配合下，2-3树可以保证在插入值过程中，任意叶子节点到根节点的距离都是相同的。完全实现了矮胖矮胖的目标。怎么配合的呢，下面来看2-3树的构造过程。
在二叉查找树中，插入过程从根节点开始比较，小于节点值往右继续与左子节点比，大于则继续与右子节点比，直到某节点左或右子节点为空，把值插入进去。这样无法避免偏向问题。在2-3树中，插入的过程是这样的。
如果将值插入一个2-节点，则将2-节点扩充为一个3-节点。
如果将值插入一个3-节点，分为以下几种情况。
（1）3-节点没有父节点，即整棵树就只有它一个三节点。此时，将3-节点扩充为一个4-节点，即包含三个元素的节点，然后将其分解，变成一棵二叉树。
此时二叉树依然保持平衡。
（2）3-节点有一个2-节点的父节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去。
（3）3-节点有一个3-节点的父节点，此时操作是：3-节点扩充为4-节点，然后分解4-节点，新树父节点向上融合，上面的3-节点继续扩充，融合，分解，新树继续向上融合，直到父节点为2-节点为止，如果向上到根节点都是3-节点，将根节点扩充为4-节点，然后分解为新树，至此，整个树增加一层，仍然保持平衡。
第三种情况稍微复杂点，为了便于直观理解，现在我们从零开始构建2-3树，囊括上面所有的情况。我们将{7,8,9,10,11,12}中的数值依次插入2-3树，画出它的过程：
所以，2-3树的设计完全可以保证二叉树保持矮矮胖胖的状态，保持其性能良好。但是，将这种直白的表述写成代码实现起来并不方便，因为要处理的情况太多。这样需要维护两种不同类型的节点，将链接和其他信息从一个节点复制到另一个节点，将节点从一种类型转换为另一种类型等等。
因此，红黑树出现了，红黑树的背后逻辑就是2-3树的逻辑，但是由于用红黑作为标记这个小技巧，最后实现的代码量并不大。
我们来看看红黑树和2-3树的关联，首先，来看红和黑的含义。红黑树中，所有的节点都是标准的2-节点，为了体现出3-节点，这里将3-节点的两个元素用左斜红色的链接连接起来，即连接了两个2-节点来表示一个3-节点。这里红色节点标记就代表指向其的链接是红链接，黑色标记的节点就是普通的节点。所以才会有那样一条定义，叫“从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点”，因为红色节点是可以与其父节点合并为一个3-节点的，红黑树实现的其实是一个完美的黑色平衡，如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的。所以它并不是一个严格的平衡二叉树，但是它的综合性能已经很优秀了。
如下图所示：
将红链接放平：
所以，红黑树的另一种定义是满足下列条件的二叉查找树：
- 红链接均为左链接。
- 没有任何一个结点同时和两条红链接相连。(这样会出现4-节点)
- 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
为什么说红黑树是“近似平衡”的？
前面说过，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。
红黑树是二叉查找树，很多操作的性能和树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是$log_2n$。要证明红黑树是近似平衡的，只需要看高度是否稳定地趋近$log_2n$就好了。
首先，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？
红色节点删除之后，没有父节点的会直接将其祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。
根据红黑树的定义——从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。所以从四叉树中取出某些节点放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。完全二叉树的高度近似为$log_2n$，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过$log_2n$。
那如果现在把红色节点加回去，高度会怎样变化呢？
根据红黑树中另外一个定义——红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 $log_2n$，所以加入红色节点之后，最长路径不会超过$2log_2n$，也就是说，红黑树的高度近似 $2log_2n$。
所以，红黑树的高度只比高度平衡的 AVL 树的高度（$log_2n$）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。
解答开篇
为什么在工程中常常使用红黑树这种平衡二叉查找树而不是其他平衡二叉查找树呢？
- 对于Treap、Splay Tree，绝大部分情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大，但是对于单次操作时间非常敏感的场景来说，它们并不适用。
- AVL 树是一种高度平衡的二叉树，所以查找的效率非常高。但是为了维持这种高度的平衡，每次插入、删除都要做调整，比较复杂耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。
- 红黑树是近似平衡，并不严格平衡，在维护平衡的成本上，比 AVL 树要低。它的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。
内容小结
红黑树的实现特别复杂，但是我们侧重点不在于它的实现，而是它的由来、特性、适用的场景以及它能解决的问题。
- 红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 $log_2n$，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 $O(logn)$。
- 因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。实现比较复杂经常借用跳表实现。
课后思考
动态数据结构支持动态地数据插入、删除、查找操作，除了红黑树，我们前面还学习过哪些呢？能对比一下各自的优势、劣势，以及应用场景吗？
这里首先解释一下什么是动态数据结构：动态数据结构是支持动态的更新操作，里面存储的数据是时刻在变化的，通俗一点讲，它不仅仅支持查询，还支持删除、插入数据。而且，这些操作都非常高效。如果不高效，也就算不上是有效的动态数据结构了。所以，这里的红黑树算一个，支持动态的插入、删除、查找，而且效率都很高。链表、队列、栈实际上算不上，因为操作非常有限，查询效率不高。
答：
- 散列表：插入删除查找都是O(1)，是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的，查找比较频繁的。
- 跳表：插入删除查找都是$O(logn)$，并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。
- 红黑树：插入删除查找都是$O(logn)$，中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。
