为什么红黑树比AVL树效率高？

前言

红黑树为什么这么火呢？大家应该都很清楚，面试的时候不管三七二十一，就问你：什么是红黑树，为什么要用红黑树？就好像他很懂，就好像知道红黑树就很牛逼一样。

whatever，如果还不懂红黑树，不管有没有基础的，希望通过本次的介绍，可以帮助你更容易的理解红黑树。

红黑树的提出

首先，什么是红黑树？红黑树也是一个自平衡的二叉查找树，如果没有基础的，可以先去前面的文章了解一下数据结构以及AVL树。

为什么要用红黑树？相比AVL树红黑树的效率更高。为什么？

我们知道AVL树是在插入或删除节点时通过旋转操作使节点的左右子树高度差不大于1，从而保证了树的平衡。但是AVL树平衡比较严格，基本上每添加或删除一个节点都会旋转一次，频繁的旋转会导致效率低下，为此红黑树就被提出了。

都知道的几个定义

相信大家在学习红黑树的时候都看过以下几个定义：

• 每个节点必须是红色或黑色。
• 根节点必须是黑色。
• 所有叶子结点都是黑色。
• 两个红节点不能相邻，如果当前节点是红色，子节点必须是黑色。
• 从任意节点到每个叶子节点的路径中，黑色节点数量是相同的。

还有等等。

这个定义看完之后你能理解为什么红黑树的效率会比AVL树高吗？反正我是理解不了，所以不要被这些定义影响，更不用死记硬背这些东西。

还有红黑树本质是2-3-4树、红黑树利用了缓存这些说法，我个人是没理解。

理解红黑树的高效

说实话，我在刚接触到红黑树的时候，首先是被开篇的定义所影响，其次发现也是通过左旋右旋保持平衡，感觉与AVL树没什么区别，反而比AVL树更加复杂，更加难以理解，所谓的“红黑树比AVL树的效率高”就更不用说了。

如何理解红黑树比AVL树的效率高呢？

红黑树相对AVL树平衡性比较宽松，没有那么严格，也就是红黑树的旋转次数不会那么频繁，这也是红黑树为什么比AVL树效率高的原因。

那么红黑树的平衡性宽松怎么体现？为什么旋转次数相对较少呢？以上的两个定义重点关注一下：

1. 两个红节点不能相邻，如果当前节点是红色，子节点必须是黑色。
2. 从任意节点到每个叶子节点的路径中，黑色节点数量是相同的。

这两个定义意味着树上的最长链上的节点是红黑相间，因为上述1。最短链全是黑节点，因为上述2。

如上图可以看到，最长链（右）和最短链（左）之间的长度差是2:4，如果此时在右树插入一个节点就会进行旋转保持平衡，如下图

因此可以知道：红黑树的最长链和最短链之间的长度差不会超过两倍，也正因如此，其旋转次数在比AVL树少的情况下也保持了相对宽松的平衡，效率也就较AVL树高一些。但是，红黑树和AVL树两者整体的复杂度都为O(log n)。

总结

1. 红黑树是为了解决AVL树频繁旋转导致效率低下被提出。
2. AVL树平衡性取决于左右子树高度差(不能大于1，比较严格)，红黑树平衡性取决于红黑节点的分布(模糊，宽松)。
3. 红黑树效率高于AVL树具体体现在：红黑树的最长链和最短链之间的长度差不会超过两倍。
4. 红黑树和AVL树两者整体的复杂度都为O(log n)。