高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法5：2-3查找樹(shù)、紅黑樹(shù)

完美平衡（Perfect balance）：每條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑的高度都是一樣的（Every path from root to leaf has same length）。也就是每個(gè)節(jié)點(diǎn)的平衡因子為0.

1. 2-3查找樹(shù)

和二叉樹(shù)不一樣，2-3樹(shù)每個(gè)節(jié)點(diǎn)保存1個(gè)或者2個(gè)的key。對(duì)于普通的2節(jié)點(diǎn)(2-node)，要有1個(gè)key和左右兩個(gè)子節(jié)點(diǎn)。對(duì)應(yīng)3節(jié)點(diǎn)(3-node)，要有兩個(gè)Key和三個(gè)子節(jié)點(diǎn)。

No. 名稱 key個(gè)數(shù) 子節(jié)點(diǎn)個(gè)數(shù)
1 2節(jié)點(diǎn)(2-node) 1 2（二叉）
2 3節(jié)點(diǎn)(3-node) 2 3（三叉）`

2-3查找樹(shù)的定義如下：

  1. 要么為空，要么：
  2. 對(duì)于2節(jié)點(diǎn)，該節(jié)點(diǎn)保存一個(gè)key及對(duì)應(yīng)value，以及兩個(gè)指向左右節(jié)點(diǎn)的節(jié)點(diǎn)，左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值都比key有效，有節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值比key要大。
  3. 對(duì)于3節(jié)點(diǎn)，該節(jié)點(diǎn)保存兩個(gè)key及對(duì)應(yīng)value，以及三個(gè)指向左中右的節(jié)點(diǎn)。左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值均比兩個(gè)key中的最小的key還要小；中間節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，中間節(jié)點(diǎn)的key值在兩個(gè)跟節(jié)點(diǎn)key值之間；右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，節(jié)點(diǎn)的所有key值比兩個(gè)key中的最大的key還要大。

如果中序遍歷2-3查找樹(shù)，就可以得到排好序的序列。在一個(gè)完全平衡的2-3查找樹(shù)中，根節(jié)點(diǎn)到每一個(gè)為空節(jié)點(diǎn)的距離都相同。

操作

查找

2-3樹(shù)的查找和二叉查找樹(shù)類(lèi)似，要確定一個(gè)樹(shù)是否屬于2-3樹(shù)，我們首先和其跟節(jié)點(diǎn)進(jìn)行比較，如果相等，則查找成功；否則根據(jù)比較的條件，在其左中右子樹(shù)中遞歸查找，如果找到的節(jié)點(diǎn)為空，則未找到，否則返回。


插入

  • 往一個(gè)2-node節(jié)點(diǎn)插入
    往2-3樹(shù)中插入元素和BST插入元素一樣，首先要進(jìn)行查找，然后將節(jié)點(diǎn)掛到未找到的節(jié)點(diǎn)上。
    如果查找后未找到的節(jié)點(diǎn)是一個(gè)2-node節(jié)點(diǎn)，只需要將新的元素放到這個(gè)2-node節(jié)點(diǎn)里面使其變成一個(gè)3-node節(jié)點(diǎn)即可。


  • 往一個(gè)3-node節(jié)點(diǎn)插入
    往一個(gè)3-node節(jié)點(diǎn)插入一個(gè)新的節(jié)點(diǎn)可能會(huì)遇到很多種不同的情況。
    只包含一個(gè)3-node節(jié)點(diǎn)

節(jié)點(diǎn)是3-node，父節(jié)點(diǎn)是2-node
和第一種情況一樣，我們也可以將新的元素插入到3-node節(jié)點(diǎn)中，使其成為一個(gè)臨時(shí)的4-node節(jié)點(diǎn)，然后，將該節(jié)點(diǎn)中的中間元素提升到父節(jié)點(diǎn)即2-node節(jié)點(diǎn)中，使其父節(jié)點(diǎn)成為一個(gè)3-node節(jié)點(diǎn)，然后將左右節(jié)點(diǎn)分別掛在這個(gè)3-node節(jié)點(diǎn)的恰當(dāng)位置。

節(jié)點(diǎn)是3-node，父節(jié)點(diǎn)也是3-node

當(dāng)插入的節(jié)點(diǎn)是3-node的時(shí)候，將該節(jié)點(diǎn)拆分，中間元素提升至父節(jié)點(diǎn)，但是此時(shí)父節(jié)點(diǎn)是一個(gè)3-node節(jié)點(diǎn)，插入之后，父節(jié)點(diǎn)變成了4-node節(jié)點(diǎn)，然后繼續(xù)將中間元素提升至其父節(jié)點(diǎn)，直至遇到一個(gè)父節(jié)點(diǎn)是2-node節(jié)點(diǎn)，然后將其變?yōu)?-node，不需要繼續(xù)進(jìn)行拆分。

根節(jié)點(diǎn)分裂

當(dāng)根節(jié)點(diǎn)到字節(jié)點(diǎn)都是3-node節(jié)點(diǎn)的時(shí)候，這是如果要在字節(jié)點(diǎn)插入新的元素的時(shí)候，會(huì)一直查分到跟節(jié)點(diǎn)，在最后一步的時(shí)候，跟節(jié)點(diǎn)變成了一個(gè)4-node節(jié)點(diǎn)，這個(gè)時(shí)候，就需要將跟節(jié)點(diǎn)查分為兩個(gè)2-node節(jié)點(diǎn)，樹(shù)的高度加1。

本地轉(zhuǎn)換

將一個(gè)4-node拆分為2-3node涉及到6種可能的操作。這4-node可能在跟節(jié)點(diǎn)，也可能是2-node的左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)。或者是一個(gè)3-node的左，中，右子節(jié)點(diǎn)。所有的這些改變都是本地的，不需要檢查或者修改其他部分的節(jié)點(diǎn)。所以只需要常數(shù)次操作即可完成2-3樹(shù)的平衡。

2-3樹(shù)之所以能夠保證在最差的情況下的效率的原因在于其插入之后仍然能夠保持平衡狀態(tài)。

性質(zhì)

這些本地操作保持了2-3樹(shù)的平衡。對(duì)于4-node節(jié)點(diǎn)變形為2-3節(jié)點(diǎn)，變形前后樹(shù)的高度沒(méi)有發(fā)生變化。只有當(dāng)跟節(jié)點(diǎn)是4-node節(jié)點(diǎn)，變形后樹(shù)的高度才加一。

AVL與2-3查找樹(shù)比較




2. 紅黑樹(shù)(Red-Black Tree)

紅黑樹(shù)是一種具有紅色和黑色鏈接的BST。

《算法導(dǎo)論》中對(duì)紅黑樹(shù)的定義（針對(duì)的是節(jié)點(diǎn)顏色）：

  1. 節(jié)點(diǎn)是紅色或黑色。
  2. 根節(jié)點(diǎn)和葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）都是黑色。
  3. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)，也就是沒(méi)有5-node)
  4. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。(黑色節(jié)點(diǎn)完美平衡)

《算法》中對(duì)紅黑樹(shù)的定義（針對(duì)的是線的顏色）：

  1. 紅色的線永遠(yuǎn)是左側(cè)鏈接。（強(qiáng)行的規(guī)定）
  2. 沒(méi)有一個(gè)節(jié)點(diǎn)同時(shí)鏈了兩條紅色的線。（也就是沒(méi)有4-node）
  3. 任何從根到葉子節(jié)點(diǎn)的路徑上有相同顏色的黑線。(黑線節(jié)點(diǎn)完美平衡)
紅黑樹(shù)
紅黑樹(shù)節(jié)點(diǎn)顏色

int Depth(Node* node){
    if(NULL == node) return 0;
    return max(Depth(node->right),Depth(node->left))+(IsRed(node)?0:1);
}
bool Check(Node* node,int maxKey,int minKey){
    if(NULL == node) return true;
    if(IsRed(node->right)) return false;
    if(IsRed(node->left) && IsRed(node->left->left)) return false;
    if(Depth(node->right) != Depth(node->left)) return false;
    if(node->key > maxKey) return false;
    if(node->key < minKey) return false;
    return Check(node->right,maxKey,node->key) && Check(node->left,node->key,minKey);
}
bool Check(Node* node){
    return Check(node,INT_MAX,INT_MIN);
}

背景

2-3查找樹(shù)能保證在插入元素之后能保持樹(shù)的平衡狀態(tài)，最壞情況下即所有的子節(jié)點(diǎn)都是2-node，樹(shù)的高度為lgN，從而保證了最壞情況下的時(shí)間復(fù)雜度。但是2-3樹(shù)實(shí)現(xiàn)起來(lái)比較復(fù)雜。紅黑樹(shù)是一種簡(jiǎn)單實(shí)現(xiàn)2-3樹(shù)的數(shù)據(jù)結(jié)構(gòu)。

紅黑樹(shù)平衡
紅黑樹(shù)轉(zhuǎn)2-3樹(shù)

本質(zhì)：紅黑樹(shù)是對(duì)2-3查找樹(shù)進(jìn)行編碼。

對(duì)2-3查找樹(shù)中的3-nodes節(jié)點(diǎn)添加額外的信息。
紅黑樹(shù)中將節(jié)點(diǎn)之間的鏈接分為兩種不同類(lèi)型。

  • 紅色鏈接：鏈接兩個(gè)2-nodes節(jié)點(diǎn)來(lái)表示一個(gè)3-nodes節(jié)點(diǎn)。
  • 黑色鏈接：鏈接普通的2-3節(jié)點(diǎn)。

使用紅色鏈接的兩個(gè)2-nodes來(lái)表示一個(gè)3-nodes節(jié)點(diǎn)，并且向左傾斜，即一個(gè)2-node是另一個(gè)2-node的左子節(jié)點(diǎn)。這種做法的好處是查找的時(shí)候不用做任何修改，和普通的二叉查找樹(shù)相同。

從邊的顏色到節(jié)點(diǎn)的顏色
BST的每一個(gè)節(jié)點(diǎn)上增加一個(gè)新的表示顏色的標(biāo)記。該標(biāo)記指示該節(jié)點(diǎn)指向其父節(jié)點(diǎn)的顏色。

紅節(jié)點(diǎn)的含義

操作

平衡化

與AVL相同，紅黑樹(shù)也需要通過(guò)旋轉(zhuǎn)保持平衡；不同的是旋轉(zhuǎn)后，需要改變節(jié)點(diǎn)的顏色。

  • 旋轉(zhuǎn)(Rotate)

左旋:將一個(gè)向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接,將紅線鏈接的兩個(gè)節(jié)點(diǎn)中的一個(gè)較大的節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)上。


左旋
左旋

右旋:將一個(gè)向左傾斜的紅色鏈接旋轉(zhuǎn)為向右鏈接,將紅線鏈接的兩個(gè)節(jié)點(diǎn)中的一個(gè)較大的節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)上。


暫時(shí)的旋轉(zhuǎn)


旋轉(zhuǎn)顏色變化規(guī)律：上升節(jié)點(diǎn)(旋轉(zhuǎn)節(jié)點(diǎn))變?yōu)樵瓉?lái)父節(jié)點(diǎn)的顏色，下降節(jié)點(diǎn)變?yōu)榧t色。

/*
 * 左旋
 *      P                    Q
 *     / \                  / \ 
 *    A   Q     ----->     P   C 
 *       / \              / \   \ 
 *      B   C            A   B   X'  
 */
Node* LeftRotate(Node* root){
    Node* pivot = root->right; // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->right = pivot->left; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->left = root;        // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn) 
}

/*
 * 右旋
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    A   Q 
 *    / \                /   / \ 
 *   A   B              X'  B   C  
 *
 */
Node* RightRotate(Node* root){
    Node* pivot = root->left;  // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->left = pivot->right; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->right = root;       // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn)
}

AVL和紅黑樹(shù)比較

  • 顏色反轉(zhuǎn)(Color Flip)
    當(dāng)出現(xiàn)一個(gè)臨時(shí)的4-node的時(shí)候，即一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)均為紅色。子節(jié)點(diǎn)顏色為黑色，父節(jié)點(diǎn)的顏色設(shè)置為紅色；反之亦然。


    顏色反轉(zhuǎn)

// 顏色翻轉(zhuǎn)：兩個(gè)子節(jié)點(diǎn)由紅色變?yōu)楹谏?，父?jié)點(diǎn)由黑色變成紅色
// 兩個(gè)子節(jié)點(diǎn)由紅色變?yōu)楹谏腹?jié)點(diǎn)由黑色變成紅色
// 兩個(gè)子節(jié)點(diǎn)由黑色變?yōu)榧t色，父節(jié)點(diǎn)由紅色變成黑色
Node* FlipColor(Node* node){
    assert(NULL != node);
    cout<<"FlipColor"<<endl;
    if(RED == node->color){
        node->left->color = RED;
        node->right->color = RED;
        node->color = BLACK;
    }else{
        node->left->color = BLACK;
        node->right->color = BLACK;
        node->color = RED;
    }
    return node;
}

  • 紅節(jié)點(diǎn)轉(zhuǎn)移(Move Red)




/*
 * 左移
 * 小寫(xiě)字母為紅節(jié)點(diǎn)，大寫(xiě)字母為黑節(jié)點(diǎn)
 *      P                    B
 *     / \                  / \ 
 *    A   Q     ----->     p   q 
 *       /                / 
 *      b                a  
 */
Node* MoveRedLeft(Node* node){
    FlipColor(node); // 父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成4結(jié)點(diǎn)
    if(IsRed(node->right->left)){ // 從右子樹(shù)借紅結(jié)點(diǎn)，父結(jié)點(diǎn)和左結(jié)點(diǎn)轉(zhuǎn)化成3結(jié)點(diǎn)
        node->right = RightRotate(node->right);
        node = LeftRotate(node);
    } 
    return node;
}

/*
 * 右移
 * 小寫(xiě)字母為紅節(jié)點(diǎn)，大寫(xiě)字母為黑節(jié)點(diǎn)
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    a   q 
 *    /                        \ 
 *   a                          c  
 *
 */
Node* MoveRedRight(Node* node){
    FlipColor(node); // 父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成4結(jié)點(diǎn)
    if(IsRed(node->left->left)) node = RightRotate(node);// 從左子樹(shù)借紅結(jié)點(diǎn)，父結(jié)點(diǎn)和右結(jié)點(diǎn)轉(zhuǎn)化成3結(jié)點(diǎn)
    return node;
}

紅節(jié)點(diǎn)轉(zhuǎn)移實(shí)質(zhì)上形成一個(gè)5節(jié)點(diǎn)。

2-3樹(shù)的平衡操作來(lái)對(duì)紅黑樹(shù)進(jìn)行平衡操作

插入

一切為了平衡，樹(shù)根到葉子節(jié)點(diǎn)的路徑上黑邊的個(gè)數(shù)(黑節(jié)點(diǎn)個(gè)數(shù))決定平衡。
從上到下查找位置，插入節(jié)點(diǎn)為紅葉子節(jié)點(diǎn)，然后從下到上回溯平衡。

  • 往一個(gè)2-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn)
    1. 按照BST遍歷，新插入的節(jié)點(diǎn)標(biāo)記為紅色。為什么新插入節(jié)點(diǎn)是紅色？為了保證插入后樹(shù)是平衡的(每條分支黑邊個(gè)數(shù)不發(fā)生改變)。
    2. 如果新插入的節(jié)點(diǎn)在父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則需要進(jìn)行左旋操作
往一個(gè)2-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn).png
  • 往一個(gè)3-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn)
    1. 插入的節(jié)點(diǎn)比現(xiàn)有的兩個(gè)節(jié)點(diǎn)都大，新插入的節(jié)點(diǎn)連接到右邊子樹(shù)上，顏色反轉(zhuǎn)。
    2. 插入的節(jié)點(diǎn)比現(xiàn)有的兩個(gè)節(jié)點(diǎn)都小，新插入的節(jié)點(diǎn)連接到最左側(cè)，中間節(jié)點(diǎn)右旋，顏色反轉(zhuǎn)。
    3. 插入的節(jié)點(diǎn)的值位于兩個(gè)節(jié)點(diǎn)之間，新節(jié)點(diǎn)插入到左側(cè)節(jié)點(diǎn)的右子節(jié)點(diǎn)。先以中間節(jié)點(diǎn)左旋至情況2，再中間節(jié)點(diǎn)右旋，顏色反轉(zhuǎn)。
往一個(gè)3-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn)
No. 值key的范圍 操作
1 a<b<key 顏色反轉(zhuǎn)
2 key<a<b b右旋(變成情況1)，然后顏色反轉(zhuǎn)
3 a<key<b a左旋(變成情況2)，b右旋(變成情況1)，然后顏色反轉(zhuǎn)
添加操作總結(jié)

3-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn)，可能會(huì)導(dǎo)致父節(jié)點(diǎn)不滿足紅黑樹(shù)的特點(diǎn)(完美平衡)，可以從下往上回溯更新節(jié)點(diǎn)的顏色(與AVL判斷平衡因子更新樹(shù)高相似)，直到平衡。

3-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn)的連鎖反應(yīng)實(shí)例1
3-node節(jié)點(diǎn)底部插入新的節(jié)點(diǎn)的連鎖反應(yīng)實(shí)例2

步驟：

  1. 執(zhí)行標(biāo)準(zhǔn)的二叉查找樹(shù)插入操作，新插入的節(jié)點(diǎn)元素用紅色標(biāo)識(shí)。
  2. 如果需要對(duì)4-node節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作
  3. 如果需要，調(diào)用FlipColor方法將紅色節(jié)點(diǎn)提升
  4. 如果需要，左旋操作使紅色節(jié)點(diǎn)左傾。
  5. 在有些情況下，需要遞歸調(diào)用Case1 Case2，來(lái)進(jìn)行遞歸操作。

平衡操作：

  1. 如果節(jié)點(diǎn)的右子節(jié)點(diǎn)為紅色，且左子節(jié)點(diǎn)位黑色，則進(jìn)行左旋操作
  2. 如果節(jié)點(diǎn)的左子節(jié)點(diǎn)為紅色，并且左子節(jié)點(diǎn)的左子節(jié)點(diǎn)也為紅色，則進(jìn)行右旋操作
  3. 如果節(jié)點(diǎn)的左右子節(jié)點(diǎn)均為紅色，則執(zhí)行FlipColor操作，提升中間結(jié)點(diǎn)。
// 只有標(biāo)志為紅色的節(jié)點(diǎn)才是紅節(jié)點(diǎn)(空節(jié)點(diǎn)也是黑節(jié)點(diǎn))
bool IsRed(const Node* root){
    return NULL != root && RED == root->color; 
}
// 平衡
Node* Balance(Node* root){
    Node *res = root;
    if (IsRed(root->right) and !IsRed(root->left)) // 如果節(jié)點(diǎn)的右子節(jié)點(diǎn)為紅色，且左子節(jié)點(diǎn)位黑色，則進(jìn)行左旋操作
        res = LeftRotate(root);
    if (IsRed(root->left) and IsRed(root->left->left)) // 如果節(jié)點(diǎn)的左子節(jié)點(diǎn)為紅色，并且左子節(jié)點(diǎn)的左子節(jié)點(diǎn)也為紅色，則進(jìn)行右旋操作
        res = RightRotate(root);
    if (IsRed(root->left) and IsRed(root->right)) // 如果節(jié)點(diǎn)的左右子節(jié)點(diǎn)均為紅色，則執(zhí)行FlipColor操作，提升中間結(jié)點(diǎn)。
        res = FlipColor(root);
    return res;
}
Node* InsertNode(Node*& node, int key){
    if(NULL == node) node = new Node(key,RED);
    if (key < node->key) node->left = InsertNode(node->left, key);
    else if (key > node->key) node->right = InsertNode(node->right,key);
    node = Balance(node); // 平衡
    return node;
}
// 插入
Node* Insert(Node*& node, int key){
    node = InsertNode(node,key);
    node->color = BLACK;// 根結(jié)點(diǎn)必須為黑結(jié)點(diǎn)
}

紅黑樹(shù)能夠保證符號(hào)表的所有操作即使在最壞的情況下都能保證對(duì)數(shù)的時(shí)間復(fù)雜度，也就是樹(shù)的高度。


升序插入構(gòu)建紅黑樹(shù)

降序插入構(gòu)建紅黑樹(shù)

隨機(jī)插入構(gòu)建紅黑樹(shù)

最壞情況
紅黑樹(shù)中除了最左側(cè)路徑全部是由3-node節(jié)點(diǎn)組成，即紅黑相間的路徑長(zhǎng)度是全黑路徑長(zhǎng)度的2倍。紅黑樹(shù)的高度不超過(guò)2lgN

最壞情況

2-3 nodes樹(shù)與RB樹(shù)關(guān)系

  1. 2-3 nodes樹(shù)中的4-node分裂成3個(gè)2-node，并讓中間節(jié)點(diǎn)上移；等價(jià)于紅黑樹(shù)中的左右旋轉(zhuǎn)；
  2. 2-3 nodes樹(shù)中間節(jié)點(diǎn)上移與父節(jié)點(diǎn)融合過(guò)程；等價(jià)于紅黑樹(shù)中的反色操作。

查找

與BST一致。

// 查找
Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}

刪除

刪除需要保證刪除節(jié)點(diǎn)是非2-node的葉子節(jié)點(diǎn)，即必須是3-node和4-node。所以查找過(guò)程需要把過(guò)程中的2-node轉(zhuǎn)化成3-node和4-node，刪除后，在把3-node和4-node還原。

/*
 * 左移
 * 小寫(xiě)字母為紅節(jié)點(diǎn)，大寫(xiě)字母為黑節(jié)點(diǎn)
 *      P                    B
 *     / \                  / \ 
 *    A   Q     ----->     p   q 
 *       /                / 
 *      b                a  
 */
Node* MoveRedLeft(Node* node){
    FlipColor(node); // 父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成4結(jié)點(diǎn)
    if(IsRed(node->right->left)){ // 從右子樹(shù)借紅結(jié)點(diǎn)，父結(jié)點(diǎn)和左結(jié)點(diǎn)轉(zhuǎn)化成3結(jié)點(diǎn)
        node->right = RightRotate(node->right);
        node = LeftRotate(node);
    } 
    return node;
}

/*
 * 右移
 * 小寫(xiě)字母為紅節(jié)點(diǎn)，大寫(xiě)字母為黑節(jié)點(diǎn)
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    a   q 
 *    /                        \ 
 *   a                          c  
 *
 */
Node* MoveRedRight(Node* node){
    FlipColor(node); // 父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成4結(jié)點(diǎn)
    if(IsRed(node->left->left)) node = RightRotate(node);// 從左子樹(shù)借紅結(jié)點(diǎn)，父結(jié)點(diǎn)和右結(jié)點(diǎn)轉(zhuǎn)化成3結(jié)點(diǎn)
    return node;
}

// 為了保證完美平衡，刪除的葉子節(jié)點(diǎn)必須是3-node或者4-node
Node* RemoveNode(Node*& node, int key) {
    Node* res = NULL;
    if(NULL == node) return NULL;
    if (key < node->key) { // 左子樹(shù)
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        node->left = RemoveNode(node->left, key);
    } else if(key > node->key) {
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        node->right = RemoveNode(node->right,key);
    } else if(key == node->key) {
        if(IsLeaf(node) && IsRed(node)) {
            delete node;
            return NULL;
        }
// #define DELETE_MIN
#ifdef DELETE_MIN
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        if(key == node->key) { // 借不到的情況
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = RemoveNode(node->right,p->key);
        } else {
            node->right = RemoveNode(node->right,key);
        }
#else
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        if(key == node->key) { // 借不到的情況
            Node* p = Maximum(node->left);
            node->key = p->key;
            node->left = RemoveNode(node->left,p->key);
        } else {
            node->left = RemoveNode(node->left, key);
        }
#endif
    }
    return Balance(node); // 平衡
}
// 刪除
Node* Remove(Node*& node,int key){
    if(!IsRed(node->right) && !IsRed(node->left)) // 根節(jié)點(diǎn)左右子樹(shù)不為黑節(jié)點(diǎn)
        node->color = RED; // 根節(jié)點(diǎn)暫時(shí)變?yōu)榧t節(jié)點(diǎn)
    node = RemoveNode(node,key);
    if(NULL != node) node->color = BLACK;
    return node;
}

小結(jié)

  • 插入操作
No. 操作 目的 改變項(xiàng) 保持項(xiàng) 執(zhí)行條件
1 左旋/右旋 調(diào)節(jié)平衡,使之符合紅黑樹(shù)規(guī)定 節(jié)點(diǎn)的位置和顏色 始終保持BST特點(diǎn) 紅節(jié)點(diǎn)不滿足紅黑樹(shù)規(guī)定
2 顏色反轉(zhuǎn) 調(diào)節(jié)平衡,使之符合紅黑樹(shù)規(guī)定(等價(jià)于2-3樹(shù)4節(jié)點(diǎn)差分) 改變節(jié)點(diǎn)的顏色 始終保持BST特點(diǎn) 紅節(jié)點(diǎn)不滿足紅黑樹(shù)規(guī)定
  • 刪除操作
No. 操作 目的 改變項(xiàng) 保持項(xiàng) 執(zhí)行條件
1 左旋/右旋 旋轉(zhuǎn)紅節(jié)點(diǎn)到要?jiǎng)h除的分支，便于后續(xù)刪除 節(jié)點(diǎn)的位置和顏色 始終保持BST特點(diǎn) 刪除右子樹(shù)節(jié)點(diǎn)，左子樹(shù)的根節(jié)點(diǎn)為紅節(jié)點(diǎn)時(shí)。
2 顏色反轉(zhuǎn) 增加可使用的紅節(jié)點(diǎn)(等價(jià)于2-3樹(shù)節(jié)點(diǎn)4節(jié)點(diǎn)組合) 改變節(jié)點(diǎn)的顏色 始終保持BST特點(diǎn) 左右子節(jié)點(diǎn)為黑節(jié)點(diǎn)時(shí)
3 紅節(jié)點(diǎn)移動(dòng) 移動(dòng)紅節(jié)點(diǎn)到要?jiǎng)h除的分支，便于后續(xù)刪除 節(jié)點(diǎn)的位置和顏色 始終保持BST特點(diǎn) 向下查找刪除節(jié)點(diǎn)，當(dāng)前子樹(shù)連續(xù)兩個(gè)黑節(jié)點(diǎn)時(shí)。

完整代碼

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

// 節(jié)點(diǎn)顏色
enum NodeColor{
    RED,  ///< 紅節(jié)點(diǎn)
    BLACK ///< 黑節(jié)點(diǎn)
};

// 節(jié)點(diǎn)
struct Node{
    int key;        ///< 鍵
    Node *left;     ///< 左子節(jié)點(diǎn)
    Node *right;    ///< 右子節(jié)點(diǎn)
    NodeColor color;///< 節(jié)點(diǎn)顏色
    Node(int key,NodeColor color) 
    :key(key),left(NULL),right(NULL),color(color){}
};

// 最大鍵
Node* Maximum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->right) node = node->right;
    return node;
}

// 最小鍵
Node* Minimum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->left) node = node->left;
    return node;
}

/*
 * 右旋
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    A   Q 
 *    / \                /   / \ 
 *   A   B              X'  B   C  
 *
 */
Node* RightRotate(Node* root){
    Node* pivot = root->left;  // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->left = pivot->right; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->right = root;       // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn)
}

/*
 * 左旋
 *      P                    Q
 *     / \                  / \ 
 *    A   Q     ----->     P   C 
 *       / \              / \   \ 
 *      B   C            A   B   X'  
 */
Node* LeftRotate(Node* root){
    Node* pivot = root->right; // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->right = pivot->left; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->left = root;        // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)

    pivot->color = root->color;
    root->color = RED;
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn) 
}

// 顏色翻轉(zhuǎn)：兩個(gè)子節(jié)點(diǎn)由紅色變?yōu)楹谏腹?jié)點(diǎn)由黑色變成紅色
// 兩個(gè)子節(jié)點(diǎn)由紅色變?yōu)楹谏?，父?jié)點(diǎn)由黑色變成紅色
// 兩個(gè)子節(jié)點(diǎn)由黑色變?yōu)榧t色，父節(jié)點(diǎn)由紅色變成黑色
Node* FlipColor(Node* node){
    assert(NULL != node);
    cout<<"FlipColor"<<endl;
    if(RED == node->color){
        node->left->color = RED;
        node->right->color = RED;
        node->color = BLACK;
    }else{
        node->left->color = BLACK;
        node->right->color = BLACK;
        node->color = RED;
    }
    return node;
}

// 只有標(biāo)志為紅色的節(jié)點(diǎn)才是紅節(jié)點(diǎn)(空節(jié)點(diǎn)也是黑節(jié)點(diǎn))
bool IsRed(const Node* root){
    return NULL != root && RED == root->color; 
}

// 平衡
Node* Balance(Node* root){
    Node *res = root;
    if (IsRed(root->right) and !IsRed(root->left)) // 如果節(jié)點(diǎn)的右子節(jié)點(diǎn)為紅色，且左子節(jié)點(diǎn)位黑色，則進(jìn)行左旋操作
        res = LeftRotate(root);
    if (IsRed(root->left) and IsRed(root->left->left)) // 如果節(jié)點(diǎn)的左子節(jié)點(diǎn)為紅色，并且左子節(jié)點(diǎn)的左子節(jié)點(diǎn)也為紅色，則進(jìn)行右旋操作
        res = RightRotate(root);
    if (IsRed(root->left) and IsRed(root->right)) // 如果節(jié)點(diǎn)的左右子節(jié)點(diǎn)均為紅色，則執(zhí)行FlipColor操作，提升中間結(jié)點(diǎn)。
        res = FlipColor(root);
    return res;
}

// 三個(gè)核心操作

Node* InsertNode(Node*& node, int key){
    if(NULL == node) node = new Node(key,RED);
    if (key < node->key) node->left = InsertNode(node->left, key);
    else if (key > node->key) node->right = InsertNode(node->right,key);
    node = Balance(node); // 平衡
    return node;
}
// 插入
Node* Insert(Node*& node, int key){
    node = InsertNode(node,key);
    node->color = BLACK;// 根結(jié)點(diǎn)必須為黑結(jié)點(diǎn)
}

// 查找
Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}

/*
 * 左移
 * 小寫(xiě)字母為紅節(jié)點(diǎn)，大寫(xiě)字母為黑節(jié)點(diǎn)
 *      P                    B
 *     / \                  / \ 
 *    A   Q     ----->     p   q 
 *       /                / 
 *      b                a  
 */
Node* MoveRedLeft(Node* node){
    FlipColor(node); // 父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成4結(jié)點(diǎn)
    if(IsRed(node->right->left)){ // 從右子樹(shù)借紅結(jié)點(diǎn)，父結(jié)點(diǎn)和左結(jié)點(diǎn)轉(zhuǎn)化成3結(jié)點(diǎn)
        node->right = RightRotate(node->right);
        node = LeftRotate(node);
    } 
    return node;
}

/*
 * 右移
 * 小寫(xiě)字母為紅節(jié)點(diǎn)，大寫(xiě)字母為黑節(jié)點(diǎn)
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    a   q 
 *    /                        \ 
 *   a                          c  
 *
 */
Node* MoveRedRight(Node* node){
    FlipColor(node); // 父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成4結(jié)點(diǎn)
    if(IsRed(node->left->left)) node = RightRotate(node);// 從左子樹(shù)借紅結(jié)點(diǎn)，父結(jié)點(diǎn)和右結(jié)點(diǎn)轉(zhuǎn)化成3結(jié)點(diǎn)
    return node;
}

// 為了保證完美平衡，刪除的葉子節(jié)點(diǎn)必須是3-node或者4-node
Node* RemoveNode(Node*& node, int key) {
    Node* res = NULL;
    if(NULL == node) return NULL;
    if (key < node->key) { // 左子樹(shù)
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        node->left = RemoveNode(node->left, key);
    } else if(key > node->key) {
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        node->right = RemoveNode(node->right,key);
    } else if(key == node->key) {
        if(IsLeaf(node) && IsRed(node)) {
            delete node;
            return NULL;
        }
// #define DELETE_MIN
#ifdef DELETE_MIN
        if(IsRed(node->left)) node = RightRotate(node);
        if(!IsRed(node->right) && !IsRed(node->right->left)) node = MoveRedRight(node);
        if(key == node->key) { // 借不到的情況
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = RemoveNode(node->right,p->key);
        } else {
            node->right = RemoveNode(node->right,key);
        }
#else
        if(!IsRed(node->left) && !IsRed(node->left->left)) node = MoveRedLeft(node);
        if(key == node->key) { // 借不到的情況
            Node* p = Maximum(node->left);
            node->key = p->key;
            node->left = RemoveNode(node->left,p->key);
        } else {
            node->left = RemoveNode(node->left, key);
        }
#endif
    }
    return Balance(node); // 平衡
}
// 刪除
Node* Remove(Node*& node,int key){
    if(!IsRed(node->right) && !IsRed(node->left)) // 根節(jié)點(diǎn)左右子樹(shù)不為黑節(jié)點(diǎn)
        node->color = RED; // 根節(jié)點(diǎn)暫時(shí)變?yōu)榧t節(jié)點(diǎn)
    node = RemoveNode(node,key);
    if(NULL != node) node->color = BLACK;
    return node;
}
/////////////////////////////////////////////////////////////
ostream& operator<<(ostream& os,const Node root) {
    queue<const Node*> q;
    q.push(&root);
    while(!q.empty()){
        const Node* curr = q.front();
        q.pop();
        if (NULL != curr){
            os << curr->key<< '[' << (curr->color==RED?'R':'B') <<']';
            q.push(curr->left);
            q.push(curr->right);
        } else {
            os << '#';
        }
    }
    return os;        
}
void TestInsert(Node*& root){
    Insert(root,1);
    Insert(root,2);
    Insert(root,3);
    Insert(root,4);
    Insert(root,5);
    cout << *root << endl;
}
void TestSearch(Node* root,int key){
    cout <<"Search " << key << ":" << Search(root,key) << endl;
}
void TestRemove(Node*& root,int key){
    root = Remove(root, key);
    cout <<"Remove " << key << ":" ;
    if(NULL != root) cout << *root << endl;
    else cout << "#" << endl;
}
void TestMax(Node* root){
    Node* maxNode = Maximum(root);
    cout << "Max:"<< maxNode->key <<":"<< maxNode <<endl;
}
void TestMin(Node* root){
    Node* minNode = Minimum(root);
    cout << "Min:"<< minNode->key <<":"<< minNode <<endl;
}

int main(){
    Node* root = NULL;
    TestInsert(root);
    TestSearch(root,1);
    TestSearch(root,2);
    TestSearch(root,3);
    TestSearch(root,4);
    TestSearch(root,5);
    TestSearch(root,6);
    TestSearch(root,7);
    TestSearch(root,8);
    TestMax(root);
    TestMin(root);

    TestRemove(root, 2);
    TestRemove(root, 5);
    TestRemove(root, 4);
    TestRemove(root, 3);
    TestRemove(root, 1);
    // TestRemove(root,1);
    // TestRemove(root,2);
    // TestRemove(root,3);
    // TestRemove(root,4);
    // TestRemove(root,5);
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容