知識星球（點選上方公眾號，可快速關註）
轉自：劉毅
https://61mon.com/index.php/archives/221/
前面已經分別介紹了兩種平衡二叉樹：AVL 樹 和 紅黑樹，先讓我們來簡單回顧下。
AVL 樹，規定其任一結點下左右子樹高度不超過 1。
紅黑樹，規定其必須滿足四個性質：
-
每個結點要麼是紅的，要麼是黑的；
-
根結點是黑色的；
-
如果一個結點是紅色的，則它的兩個孩子都是黑色的；
-
對於任意一個結點，其到葉子結點的每條路徑上都包含相同數目的黑色結點。
對比之下，我們發現：AVL 樹可以說是完全平衡的平衡二叉樹，因為它的硬性規定就是左右子樹高度差不超過 1；而紅黑樹，更準確地說，它應該是 “幾於平衡” 的平衡二叉樹，在最壞情況下，紅黑相間的路徑長度是全黑路徑長度的 2 倍。
有趣的是，某些底層資料結構（如 Linux, STL ……）選用的都是紅黑樹而非 AVL 樹，這是為何？
-
對於 AVL 樹，在插入或刪除操作後，都要利用遞迴的回溯，去維護從被刪結點到根結點這條路徑上的所有結點的平衡性，回溯的量級是需要
O ( l o g n ) ” role=”presentation” style=”font-size: 15px; box-sizing: border-box; outline: 0px; display: inline-block; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial;” tabindex=”0″> 的，其中插入操作最多需要兩次旋轉，刪除操作可能是 1 次、2 次或 2 次以上。而紅黑樹在 insert_rebalance 的時候最多需要 2 次旋轉，在 erase_rebalance 的時候最多也只需要 3 次旋轉。 -
其次，AVL 樹的結構相較紅黑樹來說更為平衡，故在插入和刪除結點時更容易引起不平衡。因此在大量資料需要插入或者刪除時，AVL 樹需要 rebalance 的頻率會更高，相比之下，紅黑樹的效率會更高。
另外，讀者需要註意的是，insert_rebalance 操作也可能會有
當程式進入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恤￥搶先預覽（長按複製整段文案，開啟手機淘寶即可進入活動內容）
近期，北京地區正常發貨，但派件時間有所延長。
