Question

有了二叉树，平衡二叉树为什么还需要红黑树

Answer 1

红黑树是处于二叉树和平衡二叉树之间的一种折中方案的算法。说起来红黑树也算是比较难理解的一个数据结构了吧，因为其本身的增删节点，除了左旋右旋还需要变色的复杂操作。

为什么有平衡二叉树这种适合适合查找的数据结构在，还需要红黑树呢？还是先从二叉树说起。

二叉查找树的特点就是 左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

二叉树的查询颇有 二分查找 的思想，如果查询一个节点，n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。为什么说是正常情况，因为上面的树其实不只是二叉树而且还是平衡二叉树。

那如果不正常的情况下，二叉树是啥样的呢？下面是一种退化为类似链表的二叉树的极端情况。这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，类似于在做全表扫描，为了避免这种情况的发生，平衡二叉树在这种情况下登场了。平衡二叉树除了具有二叉树的全部特性外，加了一个规则，就是每个节点的左子树和右子树的高度差至多等于1。

嗯，这样的话就不会出现一棵链表了。平衡二叉树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。这样平衡二叉树对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。平衡二叉树通过 构建、插入、删除、左旋、右旋 等操作来达到平衡。

MySQL索引中 B树和B+树是基于平衡二叉树的进一步改进 。B+树索引按照存储方式的不同分为 聚集索引 和 非聚集索引。

二叉树的算法实现 其实就是要插入的节点都开始和根节点比，小的放节点左边大的右边，如果位置上已经有节点了就再迭代，把当前节点作为根节点来判断放左右，直到有空位置为止。

有了平衡二叉树这么优秀的结构为什么还需要红黑树，因为平衡二叉树要求 每个节点的左子树和右子树的高度差至多等于1 ，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树规则，进而我们都需要通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树。如果频繁增删就会带来性能问题。所以红黑树出现了。

红黑树特性：

1、具有二叉查找树的特点。

2、根节点是黑色的；

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

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

5、 每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。（限制了高度）

下面是两棵红黑树的例子（黑色的空叶子节点没有画出）：

上面的例子似乎有点平衡二叉树的味道，但它并不是必须满足平衡二叉树的深度差不超过1的条件，如下面的例子。

红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。但与平衡树不同的是，红黑树在插入、删除等操作， 不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整。 意思是查效率相当，但改效率高于平衡树，这也是我们为什么大多数情况下使用红黑树的原因。只不过据说单单在查找方面的效率的话，平衡树会比红黑树快点。

综上，可以说 红黑树是一种不大严格（没有深度差要求）的平衡树 。也可以说是一个折中方案。

那么红黑树如何进行左旋，右旋和变色来达到平衡呢 ?笔者也还没完全吃透，不过理解了上面的这些应该也够驰骋沙场了。

参考文献：

腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

红黑树旋转