最近花了些時間重拾數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識，先嘗試了紅黑樹，花了大半個月的時間研究其原理和實(shí)現(xiàn)，下面是學(xué)習(xí)到的知識和一些筆記的分享。望各位多多指教。本次代碼的實(shí)現(xiàn)請點(diǎn)擊：

紅黑樹基礎(chǔ)知識

定義

紅黑樹是帶有 color 屬性的二叉搜索樹，color 的值為紅色或黑色，因此叫做紅黑樹。

對紅黑樹的每個結(jié)點(diǎn)的結(jié)構(gòu)體定義如下：

struct RBNode {
     int color;
     void *key;
     void *value;
     struct RBNode *left;
     struct RBNode *right;
     struct RBNode *parent;
};

設(shè)根結(jié)點(diǎn)的 parent 指針指向 NULL，新結(jié)點(diǎn)的左右孩子 left 和 right 指向 NULL。葉子結(jié)點(diǎn)是 NULL。

定義判斷紅黑樹顏色的宏為

#define ISRED(x) ((x) != NULL && (x)->color == RED)

因此，葉子結(jié)點(diǎn) NULL 的顏色為非紅色，在紅黑樹中，它就是黑色，包括黑色的葉子結(jié)點(diǎn)。

黑高的定義，從某個結(jié)點(diǎn) x 觸發(fā)（不含該結(jié)點(diǎn)）到達(dá)一個葉結(jié)點(diǎn)的任意一條簡單路徑上的黑色結(jié)點(diǎn)個數(shù)稱為該結(jié)點(diǎn)的黑高（black-height），記作 bh(x)。

紅黑樹的性質(zhì)

1. 每個節(jié)點(diǎn)不是紅色就是黑色；
2. 根節(jié)點(diǎn)是黑色；
3. 每個葉子節(jié)點(diǎn)是黑色；
4. 如果節(jié)點(diǎn)是紅色，那么它的兩個孩子節(jié)點(diǎn)都是黑色的；
5. 對每個節(jié)點(diǎn)來說，從節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑包含相同數(shù)目的黑色節(jié)點(diǎn)。

下面是一個紅黑樹的例子

紅黑樹的旋轉(zhuǎn)

旋轉(zhuǎn)操作在樹的數(shù)據(jù)結(jié)構(gòu)里面很經(jīng)常出現(xiàn)，比如 AVL 樹，紅黑樹等等。很多人都了解旋轉(zhuǎn)的操作是怎么進(jìn)行的（HOW），在網(wǎng)上能找到很多資料描述旋轉(zhuǎn)的步驟，但是卻沒有人告訴我為什么要進(jìn)行旋轉(zhuǎn)（WHY）？為什么要這樣旋轉(zhuǎn)？通過與朋友交流，對于紅黑樹來說，之所以要旋轉(zhuǎn)是因?yàn)樽笥易訕涞母叨炔黄胶猓醋笞訕浔扔易訕涓呋蛘哂易訕浔茸笞訕涓摺Ｄ敲矗宰笮秊槔ㄟ^左旋轉(zhuǎn)，就可以將左子樹的黑高 +1，同時右子樹的黑高 -1，從而恢復(fù)左右子樹黑高平衡。

以右旋為例，α 和 β 為 x 的左右孩子，γ 為 y 的右孩子，因?yàn)?y 的左子樹比右子樹高度多一，因此以 y 為根的子樹左右高度不平衡，那么以 y-x 為軸左旋使其左右高度平衡，左旋之后 y 和 β 同時成為 x 的右孩子，然而因?yàn)橐D(zhuǎn)的是 x 和 y 結(jié)點(diǎn)，因此就讓 β 成為 y 的左孩子即可。

旋轉(zhuǎn)的算法復(fù)雜度：從圖示可知，旋轉(zhuǎn)的操作只是做了修改指針的操作，因此算法復(fù)雜度是 O(1)。

紅黑樹的算法復(fù)雜度分析

紅黑樹的所有操作的算法復(fù)雜度都是 O(lgn)。這是因?yàn)榧t黑樹的最大高度是 2lg(n+1)。

證明如下：

設(shè)每個路徑的黑色節(jié)點(diǎn)的數(shù)量為 bh(x)`，要證明紅黑樹的最大高度是 2lg(n+1)，首先證明任何子樹包含 2^bh(x) - 1 個內(nèi)部節(jié)點(diǎn)。

下面使用數(shù)學(xué)歸納法證明。

當(dāng) bh(x) 等于 0 時，即有 0 個節(jié)點(diǎn)，那么子樹包含 2^0 - 1 = 0 個內(nèi)部節(jié)點(diǎn)，得證。

對于其他節(jié)點(diǎn)，其黑高為 bh(x) 或 bh(x) - 1，當(dāng) x 是紅節(jié)點(diǎn)時，黑高為 bh(x)，否則，為 bh(x) - 1。對于下一個節(jié)點(diǎn)，因?yàn)槊總€孩子節(jié)點(diǎn)都比父節(jié)點(diǎn)的高度低，因此歸納假設(shè)每個子節(jié)點(diǎn)至少有 2^bh(x)-1 - 1 個內(nèi)部節(jié)點(diǎn)，因此，以 x 為根的子樹至少有 2^(bh(x)-1) - 1 + 2^(bh(x)-1) - 1 = 2^bh(x) - 1個內(nèi)部節(jié)點(diǎn)。

設(shè) h 是樹高，根據(jù)性質(zhì) 4 可知道，每一條路徑至少有一半的節(jié)點(diǎn)是黑的，因此 bh(x) - 1 = h/2。

那么紅黑樹節(jié)點(diǎn)個數(shù)就為 n >= 2^h/2 - 1。

可得 n + 1 >= 2^h/2。兩邊取對數(shù)得：

    log(n+1) >= h/2

=>  2log(n+1) >= h

=>  h <= 2log(n+1)

由上面的證明可得，紅黑樹的高度最大值是 2log(n+1)，因此紅黑樹查找的復(fù)雜度為 O(lgn)。對于紅黑樹的插入和刪除操作，算法復(fù)雜度也是 O(lgn)，因此紅黑樹的所有操作都是 O(lgn)`的復(fù)雜度。

紅黑樹的插入操作分析

紅黑樹的插入操作，先找到要新節(jié)點(diǎn)插入的位置，將節(jié)點(diǎn)賦予紅色，然后插入新節(jié)點(diǎn)。最后做紅黑樹性質(zhì)的修復(fù)。

新節(jié)點(diǎn)賦予紅色的原因

因?yàn)椴迦氩僮髦豢赡軙`反性質(zhì) 2、4、5，對于性質(zhì) 2，只需要直接將根節(jié)點(diǎn)變黑即可；那么需要處理的就有性質(zhì) 4 和性質(zhì) 5，如果插入的是黑節(jié)點(diǎn)，那么就會影響新節(jié)點(diǎn)所在子樹的黑高，這樣一來就會違反性質(zhì) 5，如果新節(jié)點(diǎn)是紅色，那么新插入的節(jié)點(diǎn)就不會違反性質(zhì) 5，只需要處理違反性質(zhì) 2 或性質(zhì) 4 的情況。即根節(jié)點(diǎn)為紅色或者存在兩個連續(xù)的紅節(jié)點(diǎn)。簡而言之，就是減少修復(fù)紅黑性質(zhì)被破壞的情況。

插入算法偽代碼

RB-INSERT(T, node)
    walk = T.root
    prev = NULL
    while (walk != NULL)
        prev = walk
        if (node.key < walk.key)
            walk = walk.left
        else walk = walk.right
    node.parent = walk
    if (walk == NULL)
        T.root = node
    else if (node.key < walk.key)
        walk.left = node
    else walk.right = node
    RB-INSERT-FIXUP(T, node)

插入算法流程圖

插入的修復(fù)

插入之后，如果新結(jié)點(diǎn)（node）的父結(jié)點(diǎn)（parent）或者根節(jié)點(diǎn)（root）是紅色，那么就會違反了紅黑樹的性質(zhì) 4 或性質(zhì) 2。對于后者，只需要直接將 root 變黑即可。

而前者，違反了性質(zhì) 4 的，即紅黑樹出現(xiàn)了連續(xù)兩個紅結(jié)點(diǎn)的情況。修復(fù)的變化還要看父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左孩子還是右孩子，左右兩種情況是對稱的，此處看父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左孩子的情況。要恢復(fù)紅黑樹的性質(zhì)，那么就需要將 parent 的其中一個變黑，這樣的話，該結(jié)點(diǎn)所在的子樹的黑高 +1，這樣就會破壞了性質(zhì) 5，違背了初衷。因此需要將 parent->parent(grandparent)的另一個結(jié)點(diǎn)（uncle 結(jié)點(diǎn)）的黑高也 +1 來維持紅黑樹的性質(zhì)。

如果 uncle 是紅色，那么直接將 uncle 變?yōu)楹?色，同時 parent 也變黑。但是這樣一來，以 grandparent 為根所在的子樹的黑高就 +1，因此將 grandparent 變紅使其黑高減一，然后將 node 指向 grandparent，讓修復(fù)結(jié)點(diǎn)上升兩個 level，直到遇到根結(jié)點(diǎn)為止。

如果 uncle 是黑色，那么就不能將 uncle 變黑了。那么只能將紅節(jié)點(diǎn)上升給祖父節(jié)點(diǎn)，即將祖父結(jié)點(diǎn)變紅，然后將父結(jié)點(diǎn)變黑，這樣一來，以父結(jié)點(diǎn)為根的子樹的左右子樹就不平衡了，此時左子樹比右子樹的黑高多 1，那么就需要通過將祖父結(jié)點(diǎn)右旋以調(diào)整左右平衡。

插入修復(fù)算法的偽代碼

RB-INSERT-FIXUP(T, node)
    while IS_RED(node)
        parent = node->parent
        if !IS_RED(parent) break
        grandparent = parent->parent
        if parent == grandparent.left
            uncle = grandparent.right
            if IS_RED(uncle)
                parent.color = BLACK
                uncle.color = BLACK
                grandparent.color = RED
                node = grandparent
            elseif node == parent.right
                LEFT_ROTATE(T, parent)
                swap(node, parent)
            else
                parent.color = BLACK
                grandparent.color = RED
                RIGHT_ROTATE(T, grandparent)
        else
            same as then clause with "right" and "left" exchanged
    
    T.root.color = BLACK

插入修復(fù)算法的流程圖

插入的算法復(fù)雜度分析

插入的步驟主要有兩步

a. 找到新結(jié)點(diǎn)的插入位置 b. 進(jìn)行插入修復(fù)。而插入修復(fù)包括旋轉(zhuǎn)和使修復(fù)結(jié)點(diǎn)上升。

對于 a，從上面可知，查找的算法復(fù)雜度是 O(lgn)。

對于 b，插入修復(fù)中，每一次修復(fù)結(jié)點(diǎn)上升 2 個 level，直到遇到根結(jié)點(diǎn)，走過的路徑最大值是樹的高度，算法復(fù)雜度是 O(lgn)；由旋轉(zhuǎn)的描述可得其算法復(fù)雜度是 O(1)，因此插入修復(fù)的算法復(fù)雜度是 O(lgn)。

綜上所述，插入的算法復(fù)雜度 O(INSERT) = O(lgn) + O(lgn) = O(lgn)。

紅黑樹的刪除操作分析

紅黑樹的刪除操作，先找到要刪除的結(jié)點(diǎn)，然后找到要刪除結(jié)點(diǎn)的后繼，用其后繼替換要刪除的結(jié)點(diǎn)的位置，最后再做紅黑樹性質(zhì)的修復(fù)。

紅黑樹的刪除操作比插入操作更復(fù)雜一些。

要刪除一個結(jié)點(diǎn)（node），首先要找到該結(jié)點(diǎn)所在的位置，接著，判斷 node 的子樹情況。

• 如果 node 只有一個子樹，那么將其后繼（successor）替換掉 node 即可；
• 如果 node 有兩個子樹，那么就找到 node 的 successor 替換掉 node；
• 如果 successor 是 node 的右孩子，那么直接將 successor 替換掉 node 即可，但是需要將 successor 的顏色變?yōu)?node 的顏色；
• 如果 successor 不是 node 的右孩子，而因?yàn)?node 的后繼是沒有左孩子的（這個可以查看相關(guān)證明），所以刪除掉 node 的后繼 successor 之后，需要將 successor 的右孩子 successor.right 補(bǔ)上 successor 的位置。

刪除過程中需要保存 successor 的顏色 color，因?yàn)閯h除操作可能會導(dǎo)致紅黑樹的性質(zhì)被破壞，而刪除操作刪除的是 successor。因此，每一次改變 successor 的時候，都要更新 color。

刪除時用到的 TRANSPLANT 操作

TRANSPLANT(T, u, v) 是移植結(jié)點(diǎn)的操作，此函數(shù)的功能是使結(jié)點(diǎn) v 替換結(jié)點(diǎn) u 的位置。在刪除操作中用來將后繼結(jié)點(diǎn)替換到要刪除結(jié)點(diǎn)的位置。

刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)沒有左孩子證明

用 x 表示有非空左右孩子的結(jié)點(diǎn)。在樹的中序遍歷中，在 x 的左子樹的結(jié)點(diǎn)在 x 的前面，在 x 的右子樹的結(jié)點(diǎn)都在 x 的后面。因此，x 的前驅(qū)在其左子數(shù)，后繼在其右子樹。

假設(shè) s 是 x 的后繼。那么 s 不能有左子樹，因?yàn)樵谥行虮闅v中，s 的左子樹會在 x 和 s 的中間。（在 x 的后面是因?yàn)槠湓?x 的右子樹中，在 s 的前面是因?yàn)槠湓?x 的左子樹中。）在中序遍歷中，與前面的假設(shè)一樣，如果任何結(jié)點(diǎn)在 x 和 s 之間，那么該結(jié)點(diǎn)就不是 x 的后繼。

刪除算法偽代碼

RB-DELETE(T, node)
    color = node.color
    walk_node = node
    if IS_NULL(node.left)
        need_fixup_node = node.right
        transplant(T, node, need_fixup_node)
    elseif IS_NULL(node.right)
        need_fixup_node = node.left
        transplant(T, node, need_fixup_node)
    else
        walk_node = minimum(node.right)
        color = walk_node.color
        need_fixup_node = walk_node.right
        if walk_node.parent != node
            transplant(T, walk_node, walk_node.right)
            walk_node.right = node.right
            walk_node.right.parent = walk_node
        transplant(T, node, walk_node)
        walk_node.left = node.left
        walk_node.left.parent = walk_node
        walk_node.color = node.color
    
    if color == BLACK
        RB-DELETE-FIXUP(T, need_fixup_node)

注：筆者參考的是算法導(dǎo)論的偽代碼，但是在實(shí)現(xiàn)的時候，因?yàn)橛?NULL 表示空結(jié)點(diǎn)，如果需要修復(fù)的結(jié)點(diǎn) need_fixup_node為空時無法拿到其父結(jié)點(diǎn)，因此保存了其父結(jié)點(diǎn) need_fixup_node_parent 及其所在方向 direction，為刪除修復(fù)時訪問其父結(jié)點(diǎn)及其方向時做調(diào)整。

刪除操作流程圖

刪除的修復(fù)操作分析

刪除過程中需要保存 successor 的顏色 color，因?yàn)閯h除操作可能會導(dǎo)致紅黑樹的性質(zhì)被破壞，而刪除操作刪除的是 successor。因此，每一次改變 successor 的時候，都要更新 color。

會導(dǎo)致紅黑樹性質(zhì)被破壞的情況就是 successor 的顏色是黑色，當(dāng) successor 的顏色是紅色的時候，不會破壞紅黑樹性質(zhì)，理由如下：

• 性質(zhì) 1，刪除的是紅結(jié)點(diǎn)，不會改變其他結(jié)點(diǎn)顏色，因此不會破壞。
• 性質(zhì) 2，如果刪除的是紅結(jié)點(diǎn)，那么該結(jié)點(diǎn)不可能是根結(jié)點(diǎn)，因此根結(jié)點(diǎn)的性質(zhì)不會被破壞。
• 性質(zhì) 3，葉子結(jié)點(diǎn)的顏色保持不變。
• 性質(zhì) 4，刪除的是紅結(jié)點(diǎn)，因?yàn)樵瓉淼臉涫羌t黑樹，所以不可能出現(xiàn)連續(xù)兩個結(jié)點(diǎn)為紅色的情況。因?yàn)閯h除是 successor 只是替換 node 的位置，但是顏色被改為 node 的顏色。另外，如果 successor 不是node 的右孩子，那么就需要先將 successor 的右孩子 successor->right 替換掉 successor，如果 successor 是紅色，那么 successor->right 肯定是黑色，因此也不會造成兩個連續(xù)紅結(jié)點(diǎn)的情況。性質(zhì) 4 不被破壞。
• 性質(zhì) 5，刪除的是紅結(jié)點(diǎn)，不會影響黑高，因此性質(zhì) 5 不被破壞。

如果刪除的是黑結(jié)點(diǎn)，可能破壞的性質(zhì)是 2、4、5。理由及恢復(fù)方法如下：

• 如果 node 是黑，其孩子是紅，且 node 是 root，那么就會違反性質(zhì) 2；（修復(fù)此性質(zhì)只需要將 root 直接變黑即可）
• 如果刪除后 successor 和 successor->right 都是紅，那么會違反性質(zhì) 4；（直接將 successor->right 變黑就可以恢復(fù)性質(zhì)）
• 如果黑結(jié)點(diǎn)被刪除，會導(dǎo)致路徑上的黑結(jié)點(diǎn) -1，違反性質(zhì) 5。

那么剩下性質(zhì) 5 較難恢復(fù)，不妨假設(shè) successor->right 有一層額外黑色，那么性質(zhì) 5 就得以維持，而這樣做就會破壞了性質(zhì) 1。因?yàn)榇藭r new_successor 就為 double black（BB）或 red-black（RB）。那么就需要修復(fù)new_successor 的顏色，將其“額外黑”上移，使其紅黑樹性質(zhì)完整恢復(fù)。

注意：該假設(shè)只是加在 new_successor 的結(jié)點(diǎn)上，而不是該結(jié)點(diǎn)的顏色屬性。

如果是 R-B 情況，那么只需要將 new_successor 直接變黑，那么“額外黑”就上移到 new_successor 了，修復(fù)結(jié)束。

如果是 BB 情況，就需要將多余的一層“額外黑”繼續(xù)上移。此處還要看 new_successor 是原父結(jié)點(diǎn)的左孩子還是右孩子，這里設(shè)其為左孩子，左右孩子的情況是對稱的。

如果直接將額外黑上移給父結(jié)點(diǎn)，那么以 new_successor 的父結(jié)點(diǎn)為根的子樹就會失去平衡，因?yàn)樽笞訕涞暮诟?-1 了。因此需要根據(jù) new_successor 的兄弟結(jié)點(diǎn) brother 的顏色來考慮調(diào)整。

如果 brother 是紅色，那么 brother 的兩個孩子和 parent 都是黑色，此時額外黑就無法上移給父結(jié)點(diǎn)了，那么就需要做一些操作，將 brother 和 parent 的顏色交換，使得 brother 變黑， parent 變紅，這樣的話，brother 所在的子樹黑高就 +1 了，以 parent 為根做一次左旋恢復(fù)黑高平衡。旋轉(zhuǎn)之后，parent 是紅色的，且 brother 的其中一個孩子成為了 parent 的新的右孩子結(jié)點(diǎn)，將 brother 重新指向新的兄弟結(jié)點(diǎn)，然后接著考慮其他情況。

如果 brother 是黑色，那么就需要通過將 brother 的黑色和 successor 的額外黑組成的一重黑色上移達(dá)到目的，而要上移 brother 的黑色，還需要考慮其孩子結(jié)點(diǎn)的顏色。

如果 brother->right 和 brother->right 都是黑色，那么好辦，直接將黑色上移，即 brother->color = RED。此時包含額外黑的結(jié)點(diǎn)就變成了 parent。parent 為 RB 或 BB，循環(huán)繼續(xù)。

如果 brother->left->color =RED，brother->right->color = BLACK，將其轉(zhuǎn)為最后一種情況一起考慮。即將 brother->right 變紅。轉(zhuǎn)換步驟為：將 brother->left->color = BLACK; brother->color = RED。這樣的話 brother 的左子樹多了一層黑，右旋 brother，恢復(fù)屬性。然后將 brother 指向現(xiàn)在的 parent 的右結(jié)點(diǎn)，那么現(xiàn)在的 brother->right 就是紅色。轉(zhuǎn)為最后一種情況考慮。

如果 brother->right->color = RED。那么就要將 brother->right 變黑，使得 brother 的黑色可以上移而不破壞紅黑樹屬性，上移步驟是使 brother 變成 brother->parent 的顏色，brother->parent 變黑這樣一來，黑色就上移了。然后左旋 parent，這樣 successor 的額外黑就通過左旋加進(jìn)來的黑色抵消了。但是 parent 的右子樹的黑高就 -1 了，而通過剛剛將 brother->right 變黑就彌補(bǔ)了右子樹減去的黑高。現(xiàn)在就不存在額外黑了，結(jié)束修復(fù)，然后讓 successor 指向 root，判斷 root 是否為紅色。

刪除修復(fù)算法偽代碼

while node != root && node.color == BLACK)
    parent = node.parent
    if node = parent.left
        brother = parent.right
        if IS_RED(brother)
            brother.color = BLACK
            parent.color = RED
            LEFT_ROTATE(T, parent)
            brother = parent.right
        
        if brother.left.color == BLACK and brother.right.color == BLACK
            brother.color = RED
            node = parent
        elseif brother.right.color = BLACK
            brother.left.color = BLACK
            brother.color = RED
            RIGHT_ROTATE(T, brother)
            brother = parent.right
        else
            brother.color = parent.color
            parent.color = BLACK
            brother.right.color = BLACK
            LEFT_ROTATE(T, parent)
            node = root
    else (same as then clause with “right” and “left” exchanged)
node.color = BLACK

刪除修復(fù)算法的流程圖

刪除操作的算法復(fù)雜度分析

刪除的操作主要有查找要刪除的結(jié)點(diǎn)，刪除之后的修復(fù)。

修復(fù)紅黑樹性質(zhì)主要是旋轉(zhuǎn)和結(jié)點(diǎn)上移。對于查找來說，查找的算法復(fù)雜度是O(lgn)，旋轉(zhuǎn)的復(fù)雜度是O(1)，結(jié)點(diǎn)上移，走過的路徑最大值就是紅黑樹的高，因此上移結(jié)點(diǎn)的復(fù)雜度就是O(lgn)。

綜上所述，刪除算法的復(fù)雜度是 O(DELETE) = O(lgn) + O(1) + O(lgn) = O(lgn)。

資源分享

如果對部分步驟不理解，可以到這個網(wǎng)站看看紅黑樹每一步操作的可視化過程：。

本次代碼的實(shí)現(xiàn)請點(diǎn)擊：

總結(jié)

因?yàn)榛A(chǔ)知識比較薄弱，所以想補(bǔ)一下自己的基礎(chǔ)，無奈悟性較低，花了大半個月時間才把紅黑樹給理解和實(shí)現(xiàn)出來。中途跟朋友討論了很多次，因此有以上的這些總結(jié)。之前一直不敢去實(shí)現(xiàn)紅黑樹，因?yàn)橛X得自己根本無法理解和實(shí)現(xiàn)，內(nèi)心的恐懼一直壓抑著自己，但經(jīng)過幾次掙扎之后，終于鼓起勇氣去研究一番，發(fā)現(xiàn)，只要用心去研究，就沒有解決不了的問題。糾結(jié)了很久要不要發(fā)這篇博文，這只是一篇知識筆記的記錄，并不敢說指導(dǎo)任何人，只想把自己在理解過程中記錄下來的筆記分享出來，給有需要的人。但其實(shí)想想，糾結(jié)個蛋，讓筆記作為半成品躺在印象筆記里沉睡，還不如花時間完善好發(fā)布出來，然后有興趣的繼續(xù)探討一下。

如果真的要問我紅黑樹有什么用？為什么要學(xué)它？我真的回答不上，但是我覺得，基礎(chǔ)的東西，多學(xué)一些也無妨。只有學(xué)了，有個思路在腦海里，以后才能用得上，不然等真正要用才來學(xué)的話，似乎會浪費(fèi)了很多學(xué)習(xí)成本。

本文轉(zhuǎn)載自