详解 AVL 树和红黑树的区别
（点击上方公众号，可快速关注）
转自：刘毅
https://61mon.com/index.php/archives/221/
前面已经分别介绍了两种平衡二叉树：AVL 树 和 红黑树，先让我们来简单回顾下。
AVL 树，规定其任一结点下左右子树高度不超过 1。
红黑树，规定其必须满足四个性质：
每个结点要么是红的，要么是黑的；
根结点是黑色的；
如果一个结点是红色的，则它的两个孩子都是黑色的；
对于任意一个结点，其到叶子结点的每条路径上都包含相同数目的黑色结点。
对比之下，我们发现：AVL 树可以说是完全平衡的平衡二叉树，因为它的硬性规定就是左右子树高度差不超过 1；而红黑树，更准确地说，它应该是 "几于平衡" 的平衡二叉树，在最坏情况下，红黑相间的路径长度是全黑路径长度的 2 倍。
有趣的是，某些底层数据结构（如 Linux, STL ......）选用的都是红黑树而非 AVL 树，这是为何？
对于 AVL 树，在插入或删除操作后，都要利用递归的回溯，去维护从被删结点到根结点这条路径上的所有结点的平衡性，回溯的量级是需要 O(logn) 的，其中插入操作最多需要两次旋转，删除操作可能是 1 次、2 次或 2 次以上。而红黑树在 insert_rebalance 的时候最多需要 2 次旋转，在 erase_rebalance 的时候最多也只需要 3 次旋转。
其次，AVL 树的结构相较红黑树来说更为平衡，故在插入和删除结点时更容易引起不平衡。因此在大量数据需要插入或者删除时，AVL 树需要 rebalance 的频率会更高，相比之下，红黑树的效率会更高。
另外，读者需要注意的是，insert_rebalance 操作也可能会有 O(logn) 量级的回溯，证明如下：
当程序进入insert_rebalance()的while (x != root() && x->parent->color == red)后，它只会有如下 6 种运行方式：
Case 1；
Case 1 ----> Case 1 ----> Case 1 ......；
Case 1 ----> ...... ----> Case 2 ----> Case 3；
Case 1 ----> ...... ----> Case 3；
Case 2 ----> Case 3；
Case 3；
而这回溯就发生在第 2，3，4 种，我们就以第 2 种的为例，如下图，
"结点 1" 为新插入结点，此时属于 Case 1：当前结点的父亲是红色，叔叔存在且也是红色。那么我们的处理策略就是：
将 "父亲结点" 改为黑色；
将 "叔叔结点" 改为黑色；
将 "祖父结点" 改为红色；
将 "祖父结点" 设为 "当前结点"，继续进行操作。
但处理完后，根据代码while (x != root() && x->parent->color == red)，我们发现 "当前结点" 又进入了 Case 1。假设每次处理完后都会进入 Case 1，那么这样的处理操作会直到根结点才会结束。
erase_rebalance 是否也存在同样的回溯呢？事实上，它并不存在。这很好证明。
当程序进入while (x != root() && (x == nullptr || x->color == black))后，它只会有如下 6 种运行方式：
Case 1 ----> Case 2；
Case 1 ----> Case 3 ----> Case 4；
Case 1 ----> Case 4;
Case 2；
Case 3 ----> Case 4；
Case 4;
因为 4~6 分别是 1~3 的后缀，所以我们只需考虑 1~3 即可。
读者可以自己脑补下 1~3 的运行流程就会发现，while (x != root() && (x == nullptr || x->color == black))语句只会被用到一次，就是最初进入程序的那次，之后便不再使用。
经过如上分析，我们可以对insert_rebalance()和erase_rebalance()作些微小的优化：
void RBTree::insert_rebalance(Node * x)
{
x->color = red;
while (x != root() && x->parent->color == red)
{
if (x->parent == x->parent->parent->left)
{
Node * y = x->parent->parent->right;
if (y && y->color == red)
{
x->parent->color = black;
y->color = black;
x->parent->parent->color = red;
x = x->parent->parent;
}
else
{
if (x == x->parent->right)
{
x = x->parent;
rotate_left(x);
}
x->parent->color = black;
x->parent->parent->color = red;
rotate_right(x->parent->parent);
break; // add "break;"
}
}
else
{
Node * y = x->parent->parent->left;
if (y && y->color == red)
{
x->parent->color = black;
y->color = black;
x->parent->parent->color = red;
x = x->parent->parent;
}
else
{
if (x == x->parent->left)
{
x = x->parent;
rotate_right(x);
}
x->parent->color = black;
x->parent->parent->color = red;
rotate_left(x->parent->parent);
break; // add "break;"
}
}
}
root()->color = black;
}
void RBTree::erase_rebalance(Node * z)
{
if (y->color == black)
{
if (x != root() && (x == nullptr || x->color == black)) // "while" to "if"
{
if (x == x_parent->left)
{
Node * w = x_parent->right;
if (w->color == red)
{
w->color = black;
x_parent->color = red;
rotate_left(x_parent);
w = x_parent->right;
}
if ((w->left == nullptr || w->left->color == black) &&
(w->right == nullptr || w->right->color == black))
{
w->color = red;
x = x_parent;
x_parent = x_parent->parent;
}
else
{
if (w->right == nullptr || w->right->color == black)
{
if (w->left)
w->left->color = black;
w->color = red;
rotate_right(w);
w = x_parent->right;
}
w->color = x_parent->color;
x_parent->color = black;
if (w->right)
w->right->color = black;
rotate_left(x_parent);
// delete "break;"
}
}
else
{
Node * w = x_parent->left;
if (w->color == red)
{
w->color = black;
x_parent->color = red;
rotate_right(x_parent);
w = x_parent->left;
}
if ((w->right == nullptr || w->right->color == black) &&
(w->left == nullptr || w->left->color == black))
{
w->color = red;
x = x_parent;
x_parent = x_parent->parent;
}
else
{
if (w->left == nullptr || w->left->color == black)
{
if (w->right)
w->right->color = black;
w->color = red;
rotate_left(w);
w = x_parent->left;
}
w->color = x_parent->color;
x_parent->color = black;
if (w->left)
w->left->color = black;
rotate_right(x_parent);
// delete "break;"
}
}
}
if (x)
x->color = black;
}
}
觉得本文有帮助？请分享给更多人
关注「算法爱好者」，修炼编程内功
淘口令：复制以下红色内容，再打开手淘即可购买
范品社，使用￥极客T恤￥抢先预览（长按复制整段文案，打开手机淘宝即可进入活动内容）
近期，北京地区正常发货，但派件时间有所延长。