红黑树上

1. 平衡二叉查找树

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。

但我们学习数据结构和算法是为了应用到实际的开发中的，没有必要死扣定义，所以，对于平衡二叉查找树这个概念，我们要从这种结构的由来去理解“平衡”的意思。

平衡二叉查找树的设计初衷是为了解决普通二叉树在频繁的插入、删除等动态更新情况下，出现复杂度退化的问题。因此，平衡二叉查找树中的“平衡”，其实就是说让整棵树左右看起来比较对称 ，比较平衡，不要出现左子树很高、右子树很矮的情况。这样整棵树的高度就能相对低一点，相应的查找、插入和删除等操作的效率就更高一些。

因此，如果我们设计出一个新的平衡二叉查找树，只要树的高度不必 大很多（比如树的高度仍然是对数级的），那么尽管这不是一个严格的平衡二叉查找树，但它也是一个合格的平衡二叉查找树。

2. 红黑树

顾名思义，红黑树中的节点，一类标记为黑色，一类标记为红色，而且还要满足以下这几个条件：

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

其中第二条每个叶子结点都是黑色的空节点，是为了简化红黑树的代码实现而设置的，我们在画图的时候都将它们省略。

一棵极其平衡的二叉树的高度大约是 ，如果红黑树的高度能比较稳定地趋近 ，那我们就可以认为红黑树是近似平衡的。

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

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

前面红黑树的定义有这么一条：每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。因此，这个四叉树的所有节点可以重组成一个完全二叉树，而这个完全二叉树的高度肯定要高于四叉树。

所以，这个只有黑色节点的树的高度不会超过 。如果加上红色节点后，由于红色节点不能相邻，所以必然是一个红色节点接着一个黑色节点，最长路径不会超过 。也就是说，红黑树的高度近似为 。

所以，相比高度平衡的二叉树的高度 ，红黑树仅仅是大了一倍，在性能上，下降得并不多，而且这里只是粗略的估计，而实际上红黑树的性能会更好。

3. 为什么工程中大家都喜欢用红黑树？

一些平衡二叉树如 Treap 、Splay Tree，绝大多数情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现的概率不大，但是对于单次操作时间敏感的场景来说，它们并不适用。

AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，每次插入、删除都要做调整，比较复杂耗时。因此，对于频繁插入和删除的数据集合，使用 AVL 树的代价就有点高。

红黑树只是做到了近似平衡，在维护成本上要比 AVL 树低，而且其插入、删除、查找操作性能都比较稳定，所以工程上更倾向于这种性能稳定的平衡二叉查找树。

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩，请关注「seniusen」!