（点击上方公众号，可快速关注）
https://61mon.com/index.php/archives/221/
前面已经分别介绍了两种平衡二叉树：AVL 树和红黑树，先让我们来简单回顾下。
AVL 树，规定其任一结点下左右子树高度不超过 1。
红黑树，规定其必须满足四个性质：
每个结点要么是红的，要么是黑的；
根结点是黑色的；
如果一个结点是红色的，则它的两个孩子都是黑色的；
对于任意一个结点，其到叶子结点的每条路径上都包含相同数目的黑色结点。
对比之下，我们发现：AVL 树可以说是完全平衡的平衡二叉树，因为它的硬性规定就是左右子树高度差不超过 1；而红黑树，更准确地说，它应该是 "几于平衡" 的平衡二叉树，在最坏情况下，红黑相间的路径长度是全黑路径长度的 2 倍。
有趣的是，某些底层数据结构（如 Linux, STL ......）选用的都是红黑树而非 AVL 树，这是为何？
对于 AVL 树，在插入或删除操作后，都要利用递归的回溯，去维护从被删结点到根结点这条路径上的所有结点的平衡性，回溯的量级是需要O(logn)" role="presentation"> O ( l o g n ) 的，其中插入操作最多需要两次旋转，删除操作可能是 1 次、2 次或 2 次以上。而红黑树在 insert_rebalance 的时候最多需要 2 次旋转，在 erase_rebalance 的时候最多也只需要 3 次旋转。
其次，AVL 树的结构相较红黑树来说更为平衡，故在插入和删除结点时更容易引起不平衡。因此在大量数据需要插入或者删除时，AVL 树需要 rebalance 的频率会更高，相比之下，红黑树的效率会更高。
另外，读者需要注意的是，insert_rebalance 操作也可能会有O(logn)" role="presentation"> O ( l o g n ) 量级的回溯，证明如下：
当程序进入insert_rebalance()的while (x != root()
Case 2；
Case 3 ----> Case 4；
Case 4;
因为 4~6 分别是 1~3 的后缀，所以我们只需考虑 1~3 即可。
读者可以自己脑补下 1~3 的运行流程就会发现，while (x != root()
while (x != root()
if (y
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 = 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()
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)
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)
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恤￥抢先预览（长按复制整段文案，打开手机淘宝即可进入活动内容）
近期，北京地区正常发货，但派件时间有所延长。
【文章转自中东服务器 http://www.558idc.com/dibai.html欢迎留下您的宝贵建议】