數(shù)據(jù)結構算法 - 紅黑樹

紅黑樹是一棵自平衡的二叉搜索樹，因此在學習紅黑樹之前瓤帚，我們需要回顧一下之前所學的知識二叉搜索樹和平衡二叉樹留储。

1.二叉搜索樹

二叉搜索樹又叫二叉查找樹或者二叉排序樹七嫌，它首先是一個二叉樹惩激，而且必須滿足下面的條件：

1）若左子樹不空店煞，則左子樹上所有結點的值均小于它的根節(jié)點的值蟹演；

2）若右子樹不空风钻，則右子樹上所有結點的值均大于它的根結點的值

3）左、右子樹也分別為二叉搜索樹

二叉搜索樹示例

2.平衡二叉樹

二叉搜索樹解決了許多問題酒请，比如可以快速的查找最大值和最小值骡技，可以快速找到排名第幾位的值，快速搜索和排序等等羞反。但普通的二叉搜索樹有可能出現(xiàn)極不平衡的情況（斜樹）布朦，這樣我們的時間復雜度就有可能退化成 O(N) 的情況。比如我們現(xiàn)在插入的數(shù)據(jù)是 [1,2,3,4,5,6,7] 轉(zhuǎn)換為二叉樹如下：

斜樹

由于普通的二叉搜索樹會出現(xiàn)極不平衡的情況昼窗，那么我們就必須得想想辦法了是趴，這個時候平衡二叉樹就能幫到我們了。什么是平衡二叉樹澄惊？平衡二叉搜索樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法）唆途，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹掸驱。

平衡二叉樹有一個很重要的性質(zhì)：左右兩個子樹的高度差的絕對值不超過1肛搬。那么解決方案就是如果二叉樹的左右高度超過 1 ，我們就把當前樹調(diào)整為一棵平衡二叉樹毕贼。這就涉及到左旋温赔、右旋、先右旋再左旋鬼癣、先左旋再右旋陶贼。

2.1 右旋：

右旋.png

   TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *left = pNode->left;
        TreeNode<K, V> *right = left->right;
        left->right = pNode;
        pNode->left = right;
        // 重新調(diào)整高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
        return left;
    }

2.2 左旋：

左旋

  TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *right = pNode->right;
        TreeNode<K, V> *left = right->left;
        right->left = pNode;
        pNode->right = left;
        // 重新調(diào)整高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
        return right;
    }

2.3 先右旋再左旋：

先右旋再左旋

  TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) {
    pNode->right = R_Rotation(pNode->right);
    return L_Rotation(pNode);
  }

2.4 先左旋再右旋：

先左旋再右旋

  TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) {
    pNode->left = L_Rotation(pNode->left);
    return R_Rotation(pNode);
  }

3.紅黑樹

紅黑樹用法就比較廣了，比如 JDK 1.8 的 HashMap待秃，TreeMap骇窍，C++ 中的 map 和 multimap 等等。紅黑樹學習起來還是有一點難度的锥余，這時如果我們心中有 B 樹就有助于理解它腹纳，如果沒有 B 樹也沒有關系。

紅黑樹的特性:
（1）每個節(jié)點或者是黑色，或者是紅色嘲恍。
（2）根節(jié)點是黑色足画。
（3）每個葉子節(jié)點（NIL）是黑色。 [注意：這里葉子節(jié)點佃牛，是指為空(NIL或NULL)的葉子節(jié)點淹辞！]
（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的俘侠。
（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點象缀。

紅黑樹

假設我們現(xiàn)在要插入一個新的節(jié)點，如過插入的這個新的節(jié)點為黑色爷速，那么必然會違反性質(zhì)(5)央星，所以我們把新插入的點定義為紅色的。但是如果插入的新節(jié)點為紅色惫东，就可能會違反性質(zhì)(4) 莉给，因此我們需要對其進行調(diào)整，使得整棵樹依然滿足紅黑樹的性質(zhì)廉沮，也就是雙紅修正颓遏。接下來我們只要分情況分析就可以了：

如果沒有出現(xiàn)雙紅現(xiàn)象，父親是黑色的不需要修正滞时；
叔叔是紅色的叁幢，將叔叔和父親染黑，然后爺爺染紅坪稽；
叔叔是黑色的曼玩，父親是爺爺?shù)淖蠊?jié)點，且當前節(jié)點是其父節(jié)點的右孩子刽漂，將“父節(jié)點”作為“新的當前節(jié)點”演训，以“新的當前節(jié)點”為支點進行左旋。然后將“父節(jié)點”設為“黑色”贝咙，將“祖父節(jié)點”設為“紅色”样悟，以“祖父節(jié)點”為支點進行右旋；
叔叔是黑色的庭猩，父親是爺爺?shù)淖蠊?jié)點窟她，且當前節(jié)點是其父節(jié)點的左孩子，將“父節(jié)點”設為“黑色”蔼水，將“祖父節(jié)點”設為“紅色”震糖，以“祖父節(jié)點”為支點進行右旋；
叔叔是黑色的趴腋，父親是爺爺?shù)挠夜?jié)點吊说，且當前節(jié)點是其父節(jié)點的左孩子论咏，將“父節(jié)點”作為“新的當前節(jié)點”，以“新的當前節(jié)點”為支點進行右旋颁井。然后將“父節(jié)點”設為“黑色”厅贪，將“祖父節(jié)點”設為“紅色”，以“祖父節(jié)點”為支點進行左旋雅宾；
叔叔是黑色的养涮，父親是爺爺?shù)挠夜?jié)點，且當前節(jié)點是其父節(jié)點的右孩子眉抬，將“父節(jié)點”設為“黑色”贯吓，將“祖父節(jié)點”設為“紅色”，以“祖父節(jié)點”為支點進行左旋蜀变；

上面的雙紅修正現(xiàn)象看似比較復雜悄谐，但實際上只有三種情況，一種是沒有雙紅現(xiàn)象昏苏，另一種是父親和叔叔都是紅色的尊沸，最后一種是叔叔是黑色的威沫。我們來畫個實例看下：

void solveDoubleRed(TreeNode *pNode) {
        while (pNode->parent && pNode->parent->color == red) {// 情況 1
            TreeNode *uncle = brother(parent(pNode));

            if (getColor(uncle) == red) {// 情況2
                // 設置雙親和叔叔為黑色
                setColor(parent(pNode), black);
                setColor(uncle, black);
                // 指針回溯至爺爺
                pNode = parent(parent(pNode));
            } else {
                // 父親是爺爺?shù)淖髢鹤?                if (parent(parent(pNode))->left = parent(pNode)) { // 情況 3 和 4
                    // 自己是父親的右兒子
                    if (parent(pNode)->right == pNode) {
                        pNode = parent(pNode);
                        L_Rotation(pNode);
                    }
                    // 把我自己這邊的紅色節(jié)點挪到隔壁樹上贤惯，但仍然不能違反性質(zhì) 4 和 5
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    R_Rotation(parent(parent(pNode)));
                } else { // 情況 5 和 6
                    // 自己是父親的左兒子
                    if (parent(pNode)->left == pNode) {
                        pNode = parent(pNode);
                        R_Rotation(pNode);
                    }
                    // 把我自己這邊的紅色節(jié)點挪到隔壁樹上，但仍然不能違反性質(zhì) 4 和 5
                    setColor(parent(pNode), black);
                    setColor(parent(parent(pNode)), red);
                    L_Rotation(parent(parent(pNode)));
                }
            }
        }

        // 根結點為黑色
        root->color = black;
    }

哎～好復雜這怎么記得住棒掠。如果要記住肯定不太可能而且費勁孵构，接下來我們來分析下為什么要這么操作，還有沒有更好的調(diào)整方法烟很。我們所有的調(diào)整都是為了不違反性質(zhì)4和性質(zhì)5颈墅，假設我在左邊的這個支樹上新增了一個紅色的節(jié)點，違反了性質(zhì)4 雾袱。想法就是我把左支樹上的一個紅色節(jié)點恤筛，挪動右支樹上去，這樣就解決了我有兩個連續(xù)紅色節(jié)點的問題芹橡。但挪給右支樹的過程中不能違反性質(zhì)4和性質(zhì)5毒坛，所以必須得考慮叔叔節(jié)點的顏色。

最后我們來看下紅黑樹的刪除操作林说，紅黑樹的刪除操作要比新增操作要復雜些煎殷，但總體來說都是出現(xiàn)問題就去解決問題。當我們移除的是一個紅色節(jié)點腿箩，那么根本就不會影響我們的性質(zhì)4和性質(zhì)5豪直，我們不需要調(diào)整，但倘若我們移除的是一個黑色的節(jié)點珠移，這時肯定會違反我們的性質(zhì)5弓乙，所以我們只需要調(diào)整移除黑色節(jié)點的情況末融。分情況討論下：

如果兄弟節(jié)點是紅色的，把兄弟節(jié)點染黑暇韧，父節(jié)點染紅滑潘，左/右旋父節(jié)點；
如果兄弟節(jié)點是黑色的锨咙，并且兩個侄子節(jié)點都是黑色的语卤，將兄弟節(jié)點染紅，指針回溯至父親節(jié)點酪刀；
如果兄弟節(jié)點是黑色粹舵，的并且遠侄子是黑色的，近侄子是紅色的骂倘，將進侄子染黑眼滤，兄弟染紅，左/右旋兄弟節(jié)點历涝，進入下面情況 4 诅需；
如果兄弟節(jié)點是黑色的，并且遠侄子是紅色的荧库，近侄子隨意堰塌，將兄弟節(jié)點染成父親節(jié)點的顏色，父親節(jié)點染黑分衫，遠侄子染黑场刑，左/右旋父親節(jié)點。

void solveLostBlack(TreeNode *pNode) {
        while (pNode != root && getColor(pNode) == black) {
            if (left(parent(pNode)) == pNode) {
                TreeNode *sib = brother(pNode);
                if (getColor(sib) == red) {
                    setColor(sib, black);
                    setColor(parent(pNode), red);
                    L_Rotation(parent(pNode));
                    sib = brother(pNode);
                }

                if (getColor(left(sib)) == black && getColor(right(sib)) == black) {
                    setColor(sib, red);
                    pNode = parent(pNode);
                } else {
                    if (getColor(right(sib)) == black) {
                        setColor(left(sib), black);
                        setColor(sib, red);
                        R_Rotation(sib);
                        sib = brother(pNode);
                    }

                    setColor(sib, getColor(parent(pNode)));
                    setColor(parent(pNode), black);
                    setColor(right(sib), black);
                    L_Rotation(parent(pNode));
                    pNode = root;
                }
            } else {
                TreeNode *sib = brother(pNode);
                if (getColor(sib) == red) {
                    setColor(sib, black);
                    setColor(parent(pNode), red);
                    R_Rotation(parent(pNode));
                    sib = brother(pNode);
                }

                if (getColor(left(sib)) == black && getColor(right(sib)) == black) {
                    setColor(sib, red);
                    pNode = parent(pNode);
                } else {
                    if (getColor(left(sib)) == black) {
                        setColor(right(sib), black);
                        setColor(sib, red);
                        L_Rotation(sib);
                        sib = brother(pNode);
                    }

                    setColor(sib, getColor(parent(pNode)));
                    setColor(parent(pNode), black);
                    setColor(left(sib), black);
                    R_Rotation(parent(pNode));
                    pNode = root;
                }
            }
        }
        pNode->color = black;
    }

如果有任何疑問蚪战？請大家在最后留言牵现，我一一解答。

視頻鏈接:https://pan.baidu.com/s/1wSlx2Nt4dJCBn4cSjrR2Uw
視頻密碼:731b