歡迎光臨
每天分享高質量文章

詳解 AVL 樹和紅黑樹的區別

(點選上方公眾號,可快速關註)

轉自:劉毅

https://61mon.com/index.php/archives/221/

好文投稿, 請點選 → 這裡瞭解詳情

前面已經分別介紹了兩種平衡二叉樹:AVL 樹 和 紅黑樹,先讓我們來簡單回顧下。


AVL 樹,規定其任一結點下左右子樹高度不超過 1。

紅黑樹,規定其必須滿足四個性質:

  1. 每個結點要麼是紅的,要麼是黑的;

  2. 根結點是黑色的;

  3. 如果一個結點是紅色的,則它的兩個孩子都是黑色的;

  4. 對於任意一個結點,其到葉子結點的每條路徑上都包含相同數目的黑色結點。

對比之下,我們發現:AVL 樹可以說是完全平衡的平衡二叉樹,因為它的硬性規定就是左右子樹高度差不超過 1;而紅黑樹,更準確地說,它應該是 “幾於平衡” 的平衡二叉樹,在最壞情況下,紅黑相間的路徑長度是全黑路徑長度的 2 倍。

有趣的是,某些底層資料結構(如 Linux, STL ……)選用的都是紅黑樹而非 AVL 樹,這是為何?

  1. 對於 AVL 樹,在插入或刪除操作後,都要利用遞迴的回溯,去維護從被刪結點到根結點這條路徑上的所有結點的平衡性,回溯的量級是需要 O(logn)

    ” 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″>O(logn) 的,其中插入操作最多需要兩次旋轉,刪除操作可能是 1 次、2 次或 2 次以上。而紅黑樹在 insert_rebalance 的時候最多需要 2 次旋轉,在 erase_rebalance 的時候最多也只需要 3 次旋轉。

  2. 其次,AVL 樹的結構相較紅黑樹來說更為平衡,故在插入和刪除結點時更容易引起不平衡。因此在大量資料需要插入或者刪除時,AVL 樹需要 rebalance 的頻率會更高,相比之下,紅黑樹的效率會更高。

另外,讀者需要註意的是,insert_rebalance 操作也可能會有 O(logn)

” 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″>O(logn) 量級的回溯,證明如下:

當程式進入insert_rebalance()的while (x != root() && x->parent->color == red)後,它只會有如下 6 種執行方式:

  1. Case 1;

  2. Case 1 —-> Case 1 —-> Case 1 ……;

  3. Case 1 —-> …… —-> Case 2 —-> Case 3;

  4. Case 1 —-> …… —-> Case 3;

  5. Case 2 —-> Case 3;

  6. 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 種執行方式:

  1. Case 1 —-> Case 2;

  2. Case 1 —-> Case 3 —-> Case 4;

  3. Case 1 —-> Case 4;

  4. Case 2;

  5. Case 3 —-> Case 4;

  6. 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恤¥搶先預覽(長按複製整段文案,開啟手機淘寶即可進入活動內容)

近期,北京地區正常發貨,但派件時間有所延長。

贊(0)

分享創造快樂