RBtree刪除怎么實現

這篇文章主要講解了“RBtree刪除怎么實現”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“RBtree刪除怎么實現”吧！

下面先放出紅黑樹刪除函數的代碼：

//紅黑樹刪除函數
///類似于二叉樹刪除函數,不過在刪除完成以后需要調用調整函數恢復性質
///總的過程也是按z的左右兒子情況進行分類.
///1.z只有左兒子/右兒子
///2.z有左右兒子,z的后繼結點是z的右兒子
///3.z有左右兒子,z的后繼結點不是z的右兒子
void RBDelete(RBTree &z)
{ ///在下面的過程中y總是指向樹中會被刪除的結點或是會被替代的結點
    ///x總是指向要替代z或y的結點

    RBTree x=NULL;
    RBTree y=z;
    int ycolor=y->color; ///記錄y原來的顏色
    if(z->left==NULL) ///只有右兒子
    {
        x=z->right;
        RBTransplant(z, z->right);// z->right 替換 z
    }
    else if(z->right==NULL) ///只有左兒子
    {
        x=z->left;
        RBTransplant(z, z->left);
    }
    else  ///左右兒子都有
    {
        y=RBTreeMinMuM(z->right); ///查找z的后繼
        ycolor=y->color;
        x=y->right; ///因為后面y會被染成z原來的顏色,所以違反性質的就是y的右兒子
        if(y->p==z) ///y是z的孩子結點
        {
            x->p=y;///這種情況下,y為x的父結點

            RBTransplant(z,y); ///y取代z
            y->left=z->left; ///z的左孩子改變指向
            y->left->p=y;
            y->color=z->color; ///更改y的顏色,這樣的話從y以上紅黑樹的性質都不會違反
        }
        else ///y不是z的孩子結點的情況
        {
            RBTransplant(z, y); ///y取代z
            y->left=z->left; ///z的左孩子改變指向
            y->left->p=y;
            y->color=z->color; ///更改y的顏色,這樣的話從y以上紅黑樹的性質都不會違反
            y->right=z->right;
            y->right->p=y;
            RBTransplant(y, y->right);
        }
    }
    delete z;//
    ///如果y原來的顏色是黑色,那么就意味著有一個黑色結點被覆蓋了,
    ///紅黑樹的性質可能會被破壞(性質4或5),需要調整
    if(ycolor==BLACK)
    {
        RBDeleteFixUp(x);
    }
}

我們設要刪除的結點為z，在下面的過程中y總是指向樹中會被刪除的結點或是會被替代的結點而x總是指向要替代z或y的結點；從代碼上看，紅黑樹的刪除操作與二叉樹搜索樹一樣都是分三種情況進行的：

1).z只有左兒子/右兒子 
2).z有左右兒子,z的后繼結點是z的右兒子 
3).z有左右兒子,z的后繼的結點不是z的右兒子 
那么現在我們就來分析這三種情況下刪除z需要怎樣操作，以及刪除z后紅黑樹的那些性質會被違反，我們如何進行調整以恢復性質。

情況1：z只有左兒子/右兒子 
這種情況下刪除操作是很簡單的，我們只需要用z的左孩子或右孩子替代z就行了；然后y表示z，x表示z的左孩子或右孩子，ycolor表示z的顏色。 
(1).如果z的顏色為紅；那么這種替代以后紅黑樹不會有任何性質被違反，所以就不需要進行調整。 
(2).如果z的顏色為黑；那么就意味著有一個黑色結點被覆蓋了，這時如果替代z的x是黑色，那么就意味著黑高減少，性質5被破壞了，這時我們可以在x上再人為的”增添”一重黑色,此時x變成雙重黑色的結點，但是性質5恢復了；如果x是紅色，那么如果z的父結點是紅色的，那么性質4和性質5都就會被破壞，這時我們就可以將x染成紅色，這樣性質4，性質5都可以恢復了。

情況2：z有左右兒子，并且其右兒子就是其后繼結點 
我們知道一個結點的后繼就是將所有結點按關鍵字從小到大的排序后，排在其后面的那一個結點。z的右兒子就是z的后繼，說明z的右兒子的左子樹為空。此時y表示z的右兒子，而x表示y的右兒子。刪除過程應該是用 y 替代 z, 然后 x 替代 y，并且將y染成z原來的顏色，ycolor表示y原來的顏色。現在因為y替代z以后被染成z原來的顏色，所以至z以上紅黑樹的所有性質都不會變，唯一有可能會影響紅黑樹性質的地方在x替代y這一點。所以其實情況有返回到情況1了，下面按y的顏色進行分類討論： 
(1).y的顏色為紅；那么無論x的顏色為紅還是為黑，x替換y以后都不會影響任何性質。 
(2).y的顏色為黑；這時與上面的情況1是相似的，如果x為黑，則性質5會被違反，我們通過將其染成雙重黑色解決。如果x為紅，則性質4,5都會被違反，但是我們可以通過將x染成黑色恢復。

情況3：z有左右兒子，并且z的后繼不是其右兒子 
其實這種情況和情況2是基本一樣的，唯一不同的點在于y的位置會變。在情況2中y是z的右兒子，而在這里我們需要用一個查找后繼的函數查找到y，然后x仍然表示y的右兒子，ycolor表示y的顏色。同樣的x取代y，然后y取代z并被染成z原來的顏色。所以我們還是只需要關注x取代y的過程。接下來按y的顏色討論，其實與上面情況2是一模一樣的： 
(1).如果y的顏色為紅色；那么無論x為紅還是為黑，替換都不會影響任何性質，無需調整。 
(2).y的顏色為黑；如果x為黑，則性質5會被違反，我們通過將其染成雙重黑色解決。如果x為紅，則性質4,5都會被違反，但是我們可以通過將x染成黑色恢復。

上面的所有情況討論完了以后，我們就發現如果ycolor為紅，則刪除以后不需要任何的調整。否則如果ycolor為黑，紅黑樹的性質就會被違反，需要進入調整函數中調整恢復性質。并且進入調整函數時，如果x為紅，那么我們簡單的將其染成黑色就可以恢復性質了；如果x為黑，那么進入調整函數是我們就將其看成帶有雙重黑色的情況，調整函數中需要消除那重額外的黑色。對于x為雙重黑色的情況，還有一點需要注意：如果此時x為根結點，我們可以簡單的去掉一重黑色就行了(其實就是不需要做任何操作)，這時黑高是不會受影響的。所以我們下面集中精力來討論如何調整雙重黑色的情況。

(1).w的顏色為紅 
     此時x的父結點一定是黑色的，我們可以通過將w染成黑色，x的父結點染成紅色，然后對x的父結點進行左旋變成下面w為黑的情況(旋轉以后要重新指定w)。變化為(2)的問題。

(2).w的顏色為黑 
     此時又需要按照w的左右兒子的顏色進行分類討論 
1).w的左右兒子都為黑色：此時我們可以將w染成紅色，x移動為x的父結點，將x在樹中上移一層,如果x->p是根結點或x->p原來是紅色則結束循環,否         則轉成情況(1). 
2).w的右兒子為黑(左孩子為紅)：此時我們可以通過染色和選擇轉成w的右孩子為紅的情況(具體的操作見代碼) 變化為4 的情況 繼續執行
3).w的右兒子為紅：這種情況下，我們是可以通過選擇和染色去掉x的雙重黑色，結束循環的(具體操作見代碼) 4變化以后 結束循環

至此我們就將調整函數中所有的情況討論完了，下面給出調整函數的代碼：

///紅黑樹刪除調整函數
///這個函數主要要解決的問題是x被染成紅黑色,或是雙重黑色的問題
///對于第一種情況只要簡單的去掉x的紅色就行了。
///對于第二種情況我們分情況討論，將雙重黑色的結點在樹中上升
///直到轉成情況1,或是上升為根結點
void RBDeleteFixUp(RBTree &x)
{
    while(x !=rt &&x->color == BLACK)
    {
        if(x == x->p->left)///按x是其父結點的左/右孩子分情況討論
        {///下面的過程要按其兄弟結點的顏色進行分類討論
            RBTree w=x->p->right; ///其兄弟結點
            
            ///Case 1
            if(w->color==RED)///如果兄弟結點是紅色
            {///此時父結點一定是黑色；在保證黑高的情況下
                ///我們通過染色和旋轉轉成下面兄弟結點為黑色的情況
                
                w->color=BLACK;
                x->p->color=RED;
                LeftRotate(x->p);
                w=x->p->right;
            }
            
            ///Case 2
            if(w->left->color==BLACK&&w->right->color==BLACK)
            {///通過染色將x上移一層
                w->color=RED;
                x=x->p; ///將x在樹中上移一層,如果x->p是根結點或x->p原來是紅色則結束循環,否則轉成情況1
            }
            else ///情況3,4
            {
                ///Case 3
                if(w->right->color==BLACK)
                {///染色和右旋成情況4
                    
                    w->color=RED;
                    w->left->color=BLACK;
                    RightRotate(w);
                    w=x->p->right;
                }
                ///Case 4
                ///情況4可以直接結束遞歸
                w->color=w->p->color;
                w->p->color=BLACK;
                w->right->color=BLACK; ///需要將w的右兒子染成黑色以保證黑高
                LeftRotate(x->p);
                break;
            }
        }
        else ///處理x是父結點的右兒子的情況
        {
            RBTree w=x->p->left;
            if(w->color==RED)///Case 1
            {
                w->p->color=RED;
                w->color=BLACK;
                RightRotate(x->p);
                w=x->p->left;
            }
            else if(w->left->color==BLACK&&w->right->color==BLACK)
            {///Case 2
                w->color=RED;
                x=x->p;
            }
            else
            {
                if(w->left->color==BLACK)///Case 3
                {
                    w->right->color=BLACK;
                    w->color=RED;
                    LeftRotate(w);
                    w=x->p->left;
                }
                w->color=x->p->color;///Case 4
                x->p->color=BLACK;
                w->left->color=BLACK;
                RightRotate(x->p);
                break
            }
        }
    }
    //解決紅黑問題
    x->color=BLACK;
}

下面給出一份帶注釋和 測試 數據的完整紅黑樹代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define RED 1
#define BLACK 0
///紅黑樹結點定義,與普通的二叉樹搜索樹相比多了一個顏色域
typedef struct node
{
    int key,color; ///定義1為紅,0為黑
    node *p,*left,*right;
    node()
    {
        color=BLACK; ///默認結點顏色為黑
        p = NULL;
        left = NULL;
        right = NULL;
    }
}*RBTree;

RBTree Nul;///表示空的哨兵結點
RBTree  root; ///表示根結點

///左旋:對具有任意具有右孩子的結點可以進行
///傳入要選擇的結點指針的引用
///旋轉以后x的右孩子y取代了x,而x成為y的左孩子,y的左孩子成為x的右孩子
///下面的代碼就是完成這三個部分
void LeftRotate(RBTree x)
{
    RBTree y=x->right; ///y表示x的右孩子
    x->right=y->left; ///第一步:將x的右孩子設為y的左孩子
    if(y->left!=Nul)
        y->left->p=x;

    y->p=x->p;  ///更改y的父結點為x的父結點
    if(x->p==Nul)    ///第二步:y替代x,需要分情況討論
        root=y; ///x原來是根結點,則設y為根結點
    else if(x==x->p->left)
        x->p->left=y;   ///更改y為x父結點的左孩子
    else
        x->p->right=y; ///更改y為x父結點的右孩子

    y->left=x; ///第三步:將x設為y的左孩子
    x->p=y;
}

///右旋:對任何具有左孩子的結點可以進行
///傳入要右旋的結點指針的引用
///旋轉以后結點x被左孩子y替換,x成為y的右兒子,y的右孩子成為x的左孩子
void RightRotate(RBTree x)
{
    RBTree y=x->left; ///y表示x的左孩子
    x->left=y->right; ///第一步:x的左孩子更改為y的右孩子
    if(y->right!=Nul)
        y->right->p=x;

    y->p=x->p;  ///更改y的父結點為x的父結點
    if(x->p==Nul) ///第二步:y替代x,需要分情況討論
        root=y;  ///x原來為根結點,指定y為新根結點
    else if(x==x->p->left)
        x->p->left=y;  ///更改x父結點的左孩子為y
    else
        x->p->right=y; ///更改x父結點的右孩子為y

    y->right=x; ///第三步:更改y的右結點為x
    x->p=y;
}

///紅黑樹插入調整函數
///我們將插入結點染成紅色,可能違反了性質4,所以要進行調整
///調整的過程其實就是根據不同的情況進行分類討論,不斷轉換的過程
///最后轉成可以通過染色和旋轉恢復性質的情況
void RBInsertFixUp(RBTree z)
{
    ///在下面的代碼中z結點總是違反性質4的那個結點
    while(z->p->color==RED) ///x是紅色,它的父結點也是紅色就說明性質4被違反,要持續調整
    {
        ///下面的過程按x->p是其祖父結點的左孩子還是右兒子進行分類討論
        if(z->p==z->p->p->left) ///父結點是其祖父結點的左孩子
        {
            RBTree y=z->p->p->right;  ///表示z的叔結點
            ///下面按y的顏色進行分類討論
            if(y->color==RED)
            {///如果y是紅色并z的祖父結點一定是黑色的,這時我們通過下面的染色過程
                ///在保證黑高不變的情況下(性質5),將z在樹中上移兩層,z=z->p->p
                z->p->color=BLACK;
                y->color=BLACK;
                z->p->p->color=RED;
                z=z->p->p;///如果上移到根節點或某個父結點不為紅的結點就可以結束循環了
            }
            else   ///叔結點為黑色
            { ///此時要根據z是其父結點的左孩子還是右孩子進行分類討論
                ///如果z是左孩子則可以直接可以通過染色和右旋來恢復性質
                ///如果z是右孩子則可以先左旋來轉成右孩子的情況
                if(z==z->p->right)
                {
                    z=z->p;
                    LeftRotate(z); ///直接左旋
                }
                ///重新染色,再右旋就可以恢復性質
                z->p->color=BLACK;
                z->p->p->color=RED;
                RightRotate(z->p->p);
            }
        }
        else///父結點是祖父結點的右孩子
        {
            RBTree y=z->p->p->left;  ///叔結點
            if(y->color==RED)
            {
                z->p->color=BLACK;
                y->color=BLACK;
                z->p->p->color=RED;
                z=z->p->p;
            }
            else
            {///右兒子的時候可以直接左旋,重新調色恢復性質
                ///左兒子可以先右旋成右兒子再處理
                if(z==z->p->left)
                {
                    z=z->p;
                    RightRotate(z);
                }
                z->p->color=BLACK;
                z->p->p->color=RED;
                LeftRotate(z->p->p);
            }
        }
    }
    ///將根節點染成黑色，是必要的步驟；處理兩種情況
    ///1.第一次插入根結點被染成紅色的情況
    ///2.和在上面的循環中根節點可能被染成紅色的情況
    root->color=BLACK;
}

///紅黑樹的插入
///RB插入函數與普通的BST的插入函數只是稍微有點不同
///我們將原來的null換成了Nul結點,然后對新加入的結點,染成紅色
///然后調用RBInserootFixUp函數進行調整,使得紅黑樹的性質不被破壞
void RBInsert(int key)
{
    RBTree z=new node;
    z->color=RED;
    z->key=key;
    z->p=z->left=z->right=Nul;
    RBTree y=Nul;
    RBTree x=root;
    while(x!=Nul) ///按照二叉搜索樹的性質尋找z的插入點
    {
        y=x;
        if(z->key<x->key)
            x=x->left;
        else
            x=x->right;
    }
    z->p=y;
    if(y==Nul)///插入的是根節點
        root=z;
    else if(z->key<y->key)
        y->left=z;
    else
        y->right=z;
    RBInsertFixUp(z); ///插入紅色結點可能違反了紅黑樹的某些性質,調用調整函數進行調整
}

///紅黑樹替換函數,v替換u,與BST的類似
///只負責更改父結點的指向,左右兒子需要自己更改
void RBTransplant(RBTree u,RBTree v)
{
    if(u->p==Nul)
        root=v;
    else if(u==u->p->left)
        u->p->left=v;
    else
        u->p->right=v;
    v->p=u->p;
}

///紅黑樹后繼查找函數
///按二叉搜索樹的性質一直往左走
RBTree RBTreeMinMuM(RBTree x)
{
    if(x->left==Nul)
        return x;
    return RBTreeMinMuM(x->left);
}

///紅黑樹刪除調整函數
///這個函數主要要解決的問題是x被染成紅黑色,或是雙重黑色的問題
///對于第一種情況只要簡單的去掉x的紅色就行了。
///對于第二種情況我們分情況討論，將雙重黑色的結點在樹中上升
///直到轉成情況1,或是上升為根結點
void RBDeleteFixUp(RBTree x)
{
    while(x!=root&&x->color==BLACK)
    {
        if(x==x->p->left)///按x是其父結點的左/右孩子分情況討論
        {///下面的過程要按其兄弟結點的顏色進行分類討論
            RBTree w=x->p->right; ///其兄弟結點
            ///Case 1
            if(w->color==RED)///如果兄弟結點是紅色
            {///此時父結點一定是黑色；在保證黑高的情況下
                ///我們通過染色和旋轉轉成下面兄弟結點為黑色的情況
                w->color=BLACK;
                x->p->color=RED;
                LeftRotate(x->p);
                w=x->p->right;
            }
            ///Case 2
            if(w->left->color==BLACK&&w->right->color==BLACK)
            {///通過染色將x上移一層
                w->color=RED;
                x=x->p; ///將x在樹中上移一層,如果x->p是根結點或x->p原來是紅色則結束循環,否則轉成情況1
            }
            else ///情況3,4
            {
                ///Case 3
                if(w->right->color==BLACK)
                {///染色和右旋成情況4
                    w->color=RED;
                    w->left->color=BLACK;
                    RightRotate(w);
                    w=x->p->right;
                }
                ///Case 4
                ///情況4可以直接結束遞歸
                w->color=w->p->color;
                w->p->color=BLACK;
                w->right->color=BLACK; ///需要將w的右兒子染成黑色以保證黑高
                LeftRotate(x->p);
                break;
            }
        }
        else ///處理x是父結點的右兒子的情況
        {
            RBTree w=x->p->left;
            if(w->color==RED)
            {
                w->p->color=RED;
                w->color=BLACK;
                RightRotate(x->p);
                w=x->p->left;
            }
            else if(w->left->color==BLACK&&w->right->color==BLACK)
            {
                w->color=RED;
                x=x->p;
            }
            else
            {
                if(w->left->color==BLACK)
                {
                    w->right->color=BLACK;
                    w->color=RED;
                    LeftRotate(w);
                    w=x->p->left;
                }
                w->color=x->p->color;
                x->p->color=BLACK;
                w->left->color=BLACK;
                RightRotate(x->p);
                break;
            }
        }
    }
    x->color=BLACK;
}

//紅黑樹刪除函數
///類似于二叉樹刪除函數,不過在刪除完成以后需要調用調整函數恢復性質
///總的過程也是按z的左右兒子情況進行分類.
///1.z只有左兒子/右兒子
///2.z有左右兒子,z的后繼結點是z的右兒子
///3.z有左右兒子,z的后繼結點不是z的右兒子
void RBDelete(RBTree &z)
{ ///在下面的過程中y總是指向樹中會被刪除的結點或是會被替代的結點
    ///x總是指向要替代z或y的結點

    RBTree x=Nul;
    RBTree y=z;
    int ycolor=y->color; ///記錄y原來的顏色
    if(z->left==Nul) ///只有右兒子
    {
        x=z->right;
        RBTransplant(z, z->right);// z->right 替換 z
    }
    else if(z->right==Nul) ///只有左兒子
    {
        x=z->left;
        RBTransplant(z, z->left);
    }
    else  ///左右兒子都有
    {
        y=RBTreeMinMuM(z->right); ///查找z的后繼
        ycolor=y->color;
        x=y->right; ///因為后面y會被染成z原來的顏色,所以違反性質的就是y的右兒子
        if(y->p==z) ///y是z的孩子結點
        {
            x->p=y;///這種情況下,y為x的父結點

            RBTransplant(z,y); ///y取代z
            y->left=z->left; ///z的左孩子改變指向
            y->left->p=y;
            y->color=z->color; ///更改y的顏色,這樣的話從y以上紅黑樹的性質都不會違反
        }
        else ///y不是z的孩子結點的情況
        {
            RBTransplant(z, y); ///y取代z
            y->left=z->left; ///z的左孩子改變指向
            y->left->p=y;
            y->color=z->color; ///更改y的顏色,這樣的話從y以上紅黑樹的性質都不會違反
            y->right=z->right;
            y->right->p=y;
            RBTransplant(y, y->right);
        }
    }
    //delete z;//
    ///如果y原來的顏色是黑色,那么就意味著有一個黑色結點被覆蓋了,
    ///紅黑樹的性質可能會被破壞(性質4或5),需要調整
    if(ycolor==BLACK)
    {
        RBDeleteFixUp(x);
    }
}

///紅黑樹的中序遍歷
void RBInoderSearch(RBTree x)
{
    if(x==Nul)
        return ;
    RBInoderSearch(x->left);
    printf("%d ",x->key);
    RBInoderSearch(x->right);
}

///通過關鍵字搜索對應結點
RBTree searchByKey(RBTree x,int k)
{
    if(x->key==k)
        return  x;
    if(k<x->key)
        return searchByKey(x->left,k);
    else
        return searchByKey(x->right,k);
    return NULL;
}

int main()
{
    int a[10]={1,134,21,235,318,12,34,3,99,198};
    Nul=new node;
    root=Nul;
    for(int i=0;i<10;i++)
    {
        RBInsert(a[i]);
        cout<<"after insert "<<a[i]<<": ";
        RBInoderSearch(root);
        cout<<endl;
    }
    cout<<endl;
    RBInoderSearch(root);
    cout<<endl<<endl;
    for(int i=0;i<10;i++)
    {
        RBTree x=searchByKey(root,a[i]);
        RBDelete(x);
        cout<<"after delete "<<a[i]<<": "<<endl;
        RBInoderSearch(root);
        cout<<endl;
    }
    return 0;
}

感謝各位的閱讀，以上就是“RBtree刪除怎么實現”的內容了，經過本文的學習后，相信大家對RBtree刪除怎么實現這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！