RBtree刪除怎么實現(xiàn)

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

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

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

    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原來的顏色,所以違反性質(zhì)的就是y的右兒子
        if(y->p==z) ///y是z的孩子結(jié)點
        {
            x->p=y;///這種情況下,y為x的父結(jié)點

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

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

1).z只有左兒子/右兒子 
2).z有左右兒子,z的后繼結(jié)點是z的右兒子 
3).z有左右兒子,z的后繼的結(jié)點不是z的右兒子 
那么現(xiàn)在我們就來分析這三種情況下刪除z需要怎樣操作，以及刪除z后紅黑樹的那些性質(zhì)會被違反，我們?nèi)绾芜M行調(diào)整以恢復性質(zhì)。

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

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

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

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

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

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

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

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

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

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

RBTree Nul;///表示空的哨兵結(jié)點
RBTree  root; ///表示根結(jié)點

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

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

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

///右旋:對任何具有左孩子的結(jié)點可以進行
///傳入要右旋的結(jié)點指針的引用
///旋轉(zhuǎn)以后結(jié)點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的父結(jié)點為x的父結(jié)點
    if(x->p==Nul) ///第二步:y替代x,需要分情況討論
        root=y;  ///x原來為根結(jié)點,指定y為新根結(jié)點
    else if(x==x->p->left)
        x->p->left=y;  ///更改x父結(jié)點的左孩子為y
    else
        x->p->right=y; ///更改x父結(jié)點的右孩子為y

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

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

///紅黑樹的插入
///RB插入函數(shù)與普通的BST的插入函數(shù)只是稍微有點不同
///我們將原來的null換成了Nul結(jié)點,然后對新加入的結(jié)點,染成紅色
///然后調(diào)用RBInserootFixUp函數(shù)進行調(diào)整,使得紅黑樹的性質(zhì)不被破壞
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) ///按照二叉搜索樹的性質(zhì)尋找z的插入點
    {
        y=x;
        if(z->key<x->key)
            x=x->left;
        else
            x=x->right;
    }
    z->p=y;
    if(y==Nul)///插入的是根節(jié)點
        root=z;
    else if(z->key<y->key)
        y->left=z;
    else
        y->right=z;
    RBInsertFixUp(z); ///插入紅色結(jié)點可能違反了紅黑樹的某些性質(zhì),調(diào)用調(diào)整函數(shù)進行調(diào)整
}

///紅黑樹替換函數(shù),v替換u,與BST的類似
///只負責更改父結(jié)點的指向,左右兒子需要自己更改
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;
}

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

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

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

    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原來的顏色,所以違反性質(zhì)的就是y的右兒子
        if(y->p==z) ///y是z的孩子結(jié)點
        {
            x->p=y;///這種情況下,y為x的父結(jié)點

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

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

///通過關(guān)鍵字搜索對應結(jié)點
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刪除怎么實現(xiàn)”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對RBtree刪除怎么實現(xiàn)這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！