二叉查找树是最常用二叉树，支持快速插入、删除、查找，时间复杂度跟高度成正比，理想时间复杂度是O(logn)。

二叉查找树在频繁动态更新过程中，可能会出现 $树高度>>log2n$的情况，导致各个操作的效率下降。极端退化为链表，时间复杂度O(n)。
要解决这个复杂度退化的问题，要设计一种平衡二叉查找树。

什么是“平衡二叉查找树”？
二叉树中任意一个节点的左右子树的高度相差不能大于1。
完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL树，即任何节点的左右子树高度相差不超过1。

但很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于1），比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
学习数据结构和算法是为了应用到实际的开发中的，没必要死抠定义。对于平衡二叉查找树这个概念，要从这个数据结构的由来，理解“平衡”。
平衡二叉查找树的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，时间复杂度退化问题。

所以“平衡”是让整棵树左右看起来比较“对称”、比较“平衡”，不要左子树很高、右子树很矮，整棵树的高度相对低，插入、删除、查找等操作的效率高一些。

所以，现在设计一个新的平衡二叉查找树，只要树高度不比log2n大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但仍可说，是一个合格的平衡二叉查找树。

如何定义一棵“红黑树”？

平衡二叉查找树很多，如Splay Tree（伸展树）、Treap（树堆），但提到平衡二叉查找树，基本都是红黑树。出镜率甚至高于“平衡二叉查找树”几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那我们现在就来看看这个“明星树”。
“Red-Black Tree”，简称R-B Tree，不严格的平衡二叉查找树，究竟是怎么定义的？
红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
根节点是黑色的；

每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

这里的第二点要求“叶子节点都是黑色的空节点”，稍微有些奇怪，它主要是为了简化红黑树的代码实现而设置的，下一节我们讲红黑树的实现的时候会讲到。这节我们暂时不考虑这一点，所以，在画图和讲解的时候，我将黑色的、空的叶子节点都省略掉了。

为了让你更好地理解上面的定义，我画了两个红黑树的图例，你可以对照着看下。

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

平衡二叉查找树初衷是解决二叉查找树因为动态更新导致的性能退化。
“平衡”等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 $log2n$，所以要证明红黑树近似平衡，只需分析，红黑树高度是否比较稳定趋近 $log2n$。

如果将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

上一节我们说，完全二叉树的高度近似log2n，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过log2n。

我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变成多少呢？

从上面我画的红黑树的例子和定义看，在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过log2n，所以加入红色节点之后，最长路径不会超过2log2n，也就是说，红黑树的高度近似2log2n。

所以，红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

为什么都喜欢用红黑树这种平衡二叉查找树

Treap、Splay Tree，绝大部分情况下，它们操作的效率都很高，但也无法避免极端情况下时间复杂度退化。尽管概率不大，但对单次操作时间非常敏感的场景，它们并不适用。
AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。

红黑树只是做到了近似平衡，不是严格平衡，所以维护平衡成本比AVL树低。

所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

小结

不应该把学习的侧重点，放到实现上。那红黑树，究竟要掌握？
学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树，也不例外。

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。

因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现，难度有些高，更倾向用跳表。