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

紅黑樹基礎(chǔ)知識

定義

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

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

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

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

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

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

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

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

紅黑樹的性質(zhì)

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

下面是一個紅黑樹的例子

紅黑樹的旋轉(zhuǎn)

旋轉(zhuǎn)操作在樹的數(shù)據(jù)結(jié)構(gòu)里面很經(jīng)常出現(xiàn)，比如 AVL 樹，紅黑樹等等。很多人都了解旋轉(zhuǎn)的操作是怎么進行的（HOW），在網(wǎng)上能找到很多資料描述旋轉(zhuǎn)的步驟，但是卻沒有人告訴我為什么要進行旋轉(zhuǎn)（WHY）？為什么要這樣旋轉(zhuǎn)？通過與朋友交流，對于紅黑樹來說，之所以要旋轉(zhuǎn)是因為左右子樹的高度不平衡，即左子樹比右子樹高或者右子樹比左子樹高。那么，以左旋為例，通過左旋轉(zhuǎn)，就可以將左子樹的黑高 +1，同時右子樹的黑高 -1，從而恢復(fù)左右子樹黑高平衡。

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

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

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

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

證明如下：

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

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

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

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

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

那么紅黑樹節(jié)點個數(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é)點插入的位置，將節(jié)點賦予紅色，然后插入新節(jié)點。最后做紅黑樹性質(zhì)的修復(fù)。

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

因為插入操作只可能會違反性質(zhì) 2、4、5，對于性質(zhì) 2，只需要直接將根節(jié)點變黑即可；那么需要處理的就有性質(zhì) 4 和性質(zhì) 5，如果插入的是黑節(jié)點，那么就會影響新節(jié)點所在子樹的黑高，這樣一來就會違反性質(zhì) 5，如果新節(jié)點是紅色，那么新插入的節(jié)點就不會違反性質(zhì) 5，只需要處理違反性質(zhì) 2 或性質(zhì) 4 的情況。即根節(jié)點為紅色或者存在兩個連續(xù)的紅節(jié)點。簡而言之，就是減少修復(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é)點（node）的父結(jié)點（parent）或者根節(jié)點（root）是紅色，那么就會違反了紅黑樹的性質(zhì) 4 或性質(zhì) 2。對于后者，只需要直接將 root 變黑即可。

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

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

如果 uncle 是黑色，那么就不能將 uncle 變黑了。那么只能將紅節(jié)點上升給祖父節(jié)點，即將祖父結(jié)點變紅，然后將父結(jié)點變黑，這樣一來，以父結(jié)點為根的子樹的左右子樹就不平衡了，此時左子樹比右子樹的黑高多 1，那么就需要通過將祖父結(jié)點右旋以調(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é)點的插入位置 b. 進行插入修復(fù)。而插入修復(fù)包括旋轉(zhuǎn)和使修復(fù)結(jié)點上升。

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

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

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

紅黑樹的刪除操作分析

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

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

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

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

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

刪除時用到的 TRANSPLANT 操作

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

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

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

假設(shè) s 是 x 的后繼。那么 s 不能有左子樹，因為在中序遍歷中，s 的左子樹會在 x 和 s 的中間。（在 x 的后面是因為其在 x 的右子樹中，在 s 的前面是因為其在 x 的左子樹中。）在中序遍歷中，與前面的假設(shè)一樣，如果任何結(jié)點在 x 和 s 之間，那么該結(jié)點就不是 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)論的偽代碼，但是在實現(xiàn)的時候，因為用 NULL 表示空結(jié)點，如果需要修復(fù)的結(jié)點 need_fixup_node為空時無法拿到其父結(jié)點，因此保存了其父結(jié)點 need_fixup_node_parent 及其所在方向 direction，為刪除修復(fù)時訪問其父結(jié)點及其方向時做調(diào)整。

刪除操作流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

如果 brother->right 和 brother->right 都是黑色，那么好辦，直接將黑色上移，即 brother->color = RED。此時包含額外黑的結(jié)點就變成了 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é)點，那么現(xiàn)在的 brother->right 就是紅色。轉(zhuǎn)為最后一種情況考慮。

如果 brother->right->color = RED。那么就要將 brother->right 變黑，使得 brother 的黑色可以上移而不破壞紅黑樹屬性，上移步驟是使 brother 變成 brother->parent 的顏色，brother->parent 變黑這樣一來，黑色就上移了。然后左旋 parent，這樣 successor 的額外黑就通過左旋加進來的黑色抵消了。但是 parent 的右子樹的黑高就 -1 了，而通過剛剛將 brother->right 變黑就彌補了右子樹減去的黑高。現(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é)點，刪除之后的修復(fù)。

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

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

資源分享

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

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

總結(jié)

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

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

本文轉(zhuǎn)載自