一、为什么要引入红黑树

因为AVL树比红黑树更加平衡，但AVL树在插入和删除的时候也会存在大量的旋转操作。所以当你的应用涉及到频繁的插入和删除操作，切记放弃AVL树，选择性能更好的红黑树。

红黑树不追求”完全平衡”，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。

就插入节点导致树失衡的情况，AVL和RB-Tree都是非常多两次树旋转来实现复衡rebalance，旋转的量级是O(1)
删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree非常多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！

延伸阅读：

二、什么样的数据结构称为红黑树

红黑树（Red Black Tree）是一种自平衡的二叉查找树，它与平衡二叉树相同的地方在于都是为了维护查找树的平衡而构建的数据结构，它的主要特征是在二叉查找树的每个节点上添加了一个属性表示颜色，颜色有两种，红与黑。

性质：

每个节点是红色或者黑色；

根节点是黑色；

所有叶子节点都是黑色（叶子是NIL节点，也称为外节点）;

每个红色节点的子节点都是黑色（从每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）；

从红黑树的任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（包含黑色节点的数目称为该节点的黑高度）。

上一篇

为什么STL和linux都使用红黑树作为平衡树的实?

下一篇

什么是crm管理?