Linux教程網 >> Linux編程 >> Linux編程 >> 紅黑樹的旋轉、查找和刪除（附源代碼）

紅黑樹的旋轉、查找和刪除（附源代碼）

日期：2017/3/1 9:06:06 编辑：Linux編程

Red Black Tree

Basic

紅黑樹的節點聲明，其中Parent指針是指向某一節點的父節點的指針：

typedef struct TreeNode *PtrRBTNode;
typedef struct TreeNode RBTNode;
struct TreeNode{
    ElementType Key;
    ColorType Color;
    PtrRBTNode Left;
    PtrRBTNode Right;
    PtrRBTNode Parent;
};

紅黑樹的總體聲明，該聲明中包含了指向紅黑樹根節點的指針和指向用作sentinel的dummy node的指針：

typedef struct Tree *PtrRBT;
struct Tree{
    PtrRBTNode Root;
    PtrRBTNode NullNode;
};

一些其他的相關函數：

PtrRBT RBInit(PtrRBT T){
    T = (PtrRBT)malloc(sizeof(struct Tree));
    T->Root = NULL;
    T->NullNode = (PtrRBTNode)malloc(sizeof(RBTNode));
    T->NullNode->Key = -1;
    T->NullNode->Color = Black;
    T->NullNode->Left = T->NullNode->Right = T->NullNode->Parent = NULL;
    
    return T;
}

PtrRBTNode RBCreateNode(PtrRBT T, ElementType Val){
    PtrRBTNode NewNode = (PtrRBTNode)malloc(sizeof(RBTNode));
    
    NewNode->Key = Val;
    NewNode->Color = Red;
    NewNode->Left = NewNode->Right = T->NullNode;
    
    return NewNode;
}

PtrRBTNode RBSearch(PtrRBT T, ElementType Val){
    PtrRBTNode TempNode = T->Root;
    
    if(NULL == TempNode){
        return NULL;
    }
    while(T->NullNode != TempNode){
        if(TempNode->Key > Val){
            TempNode = TempNode->Left;
        }
        else if(TempNode->Key < Val){
            TempNode = TempNode->Right;
        }
        else{
            return TempNode;
        }
    }
    
    return NULL;
}

PtrRBTNode RBFindSuccessor(PtrRBT T, PtrRBTNode Root){
    while(T->NullNode != Root->Left){
        Root = Root->Left;
    }
    
    return Root;
}

Rotate

紅黑樹的旋轉操作和AVL樹的旋轉操作差不多，但是還是有幾個需要特別注意的地方。

首先，應當注意紅黑樹的每個節點都有Parent指針，在旋轉操作時不能遺漏對於Parent指針的操作。

第二，對於某一節點中Parent指針的操作需要訪問該節點，這時就應當注意該節點是否為NULL節點。例如下圖中的C節點就可能為NULL節點，如果不是NULL節點，在旋轉時要將C的Parent指針指向B。當然在處理NULL節點時，我們可以利用一個dummy node來作為一個sentinel，所有的葉節點的Left和Right指針都指向這個sentinel，而根節點的Parent指針也指向sentinel，sentinel的Color為Black，其余成員值為任意。

第三，在旋轉時應該注意根節點。當旋轉的Pivot節點就是根節點時，應當注意更改struct Tree結構中的Root指針，將其指向新的根節點。當旋轉的Pivot節點不是根節點時，應當注意更改Pivot的父節點的Left或Right指針，這裡就需要加以分類討論（到底新的根節點，如上圖中的D節點，是其父節點的左子樹還是右子樹），可以利用Pivot->Parent來訪問Pivot的父節點。

Source Code

PtrRBT RBLeftRotate(PtrRBT T, PtrRBTNode Pivot){
    PtrRBTNode TempNode = Pivot->Right;
    
    Pivot->Right = TempNode->Left;
    if(T->NullNode != TempNode->Left){
        TempNode->Left->Parent = Pivot;
    }
    TempNode->Left = Pivot;
    TempNode->Parent = Pivot->Parent;
    if(T->Root == Pivot){
        T->Root = TempNode;
    }
    else{
        if(Pivot == Pivot->Parent->Left){
            Pivot->Parent->Left = TempNode;
        }
        else{
            Pivot->Parent->Right = TempNode;
        }
    }
    Pivot->Parent = TempNode;
    
    return T;
}

PtrRBT RBRightRotate(PtrRBT T, PtrRBTNode Pivot){
    PtrRBTNode TempNode = Pivot->Left;
    
    Pivot->Left = TempNode->Right;
    if(T->NullNode != TempNode->Right){
        TempNode->Right->Parent = Pivot;
    }
    TempNode->Right = Pivot;
    TempNode->Parent = Pivot->Parent;
    if(T->Root == Pivot){
        T->Root = TempNode;
    }
    else{
        if(Pivot == Pivot->Parent->Left){
            Pivot->Parent->Left = TempNode;
        }
        else{
            Pivot->Parent->Right = TempNode;
        }
    }
    Pivot->Parent = TempNode;
    
    return T;
}

Insert

紅黑樹的插入操作和BST也差不多，同樣在插入以後需要像AVL樹那樣向上調整，但是紅黑樹因為每個節點都存在parent指針，所以向上調整可以通過迭代來實現，而不需要像AVL樹那樣要用遞歸回溯。紅黑樹向上調整的過程實際上就是不斷將新插入的紅節點向上移動，直至它的父節點為黑為止，這樣就存在三種情況（之所以不存在其他情況，完全是由於紅黑樹的性質決定的）。並且紅黑樹的根節點和根節點的父節點的Color一定是Black，所以這個向上調整的過程就一定會停止，也就是最終一定能跳出循環，在跳出循環之後需要將根節點的Color賦值為Black。

以下三種情況均針對待調整節點在其祖父節點的左子樹中時進行分析，若在右子樹中時，做對稱操作即可。

Case One

這種情況中,待調整節點是C節點，C節點的父節點B和父節點B的Sibling節點E的Color均為Red（需要注意的是這裡C、D、E的左右子樹可能為空，可能不為空，且A節點也可能不是根節點）。遇到這種情況時，將C節點的父節點B和父節點B的Sibling節點E的Color賦值為Black，並將C節點的祖父節點A賦值為Red，同時將待調整節點變為節點A。因為起初父節點的Color為Red，所以根據性質，C的祖父節點A的Color一定為Black，這樣同時調整B和E為Black，可以使沿B和E至葉節點的路徑上的Black節點數相同，且消除了B、C均為Red的情況，但是這樣一來沿A至葉節點的路徑上的Black節點數就增加了一個，因此將A賦值為Red，使得沿A至葉節點的路徑上的Black節點數保持和調整前的數量一致，然而我們無法排除A的父節點的Color也是Red的情況，所以將待調整節點變為節點A，在下一次循環中繼續調整。

Case Two

這種情況中，待調整節點是D節點，D節點的父節點B的Color是Red，但是父節點B的Sibling節點E的Color是Black，且D節點是其父節點B的右子節點。此時僅需要以B節點為Pivot做左旋即可，並將待調整節點變為B。在具體實現時還需要注意將記錄父節點的變量FNode變為D節點，並進入Case Three。之所以要這樣操作，是因為這裡的操作僅僅針對兩個Red節點，而對於Black節點的操作（例如C節點），起初沿B的左子節點、D的左（C節點）右子節點至葉節點的路徑的Black節點數都是相同的，所以旋轉操作中移動以C為根節點的子樹後，沿B的子節點和D的子節點至葉節點的路徑的Black節點數依然是相同的且保持不變。

Case Three

這種情況中，待調整節點是C節點，C節點的父節點B的Color是Red，但是父節點B的Sibling節點E的Color是Black，且C節點是其父節點B的左子節點。此時僅需要以C節點的祖父節點A作為Pivot做右旋即可，並將原先的父節點B的Color調整為Black，將原先的祖父節點A的Color調整為Red。之所以要這樣操作，是因為起初沿C節點的左右子節點、沿D節點和E節點至葉節點的路徑的Black節點數是相同的，所以在調整過後沿它們至葉節點的路徑上的Black節點數依然是相同的且保持不變，而這樣操作卻可以通過交換顏色將一個Red節點移動到祖先節點的右子樹中，消除了兩個Red節點相連的情況，當然旋轉後新的子樹的根節點B要賦值為Black，以保持從子樹的根節點（原先是A，現在是B）的路徑的Black節點數保持和原來一樣。這裡要是Pivot是整棵紅黑樹的根節點，則需更新Root節點的值。

Source Code

PtrRBT RBInsert(PtrRBT T, ElementType Val){
    PtrRBTNode TempNode = T->Root;
    PtrRBTNode NewNode = RBCreateNode(T, Val);
    
    if(NULL == TempNode){
        T->Root = NewNode;
        NewNode->Parent = T->NullNode;
    }
    else{
        while(T->NullNode != TempNode){
            if(Val < TempNode->Key){
                if(T->NullNode == TempNode->Left){
                    TempNode->Left = NewNode;
                    NewNode->Parent = TempNode;
                    break;
                }
                else{
                    TempNode = TempNode->Left;
                }
            }
            else{
                if(T->NullNode == TempNode->Right){
                    TempNode->Right = NewNode;
                    NewNode->Parent = TempNode;
                    break;
                }
                else{
                    TempNode = TempNode->Right;
                }
            }
        }
    }
    
    T = RBInsertFixUp(T, NewNode);
    
    return T;
}

PtrRBT RBInsertFixUp(PtrRBT T, PtrRBTNode CurrentNode){
    PtrRBTNode FNode, GNode, UNode;
    
    while(Red == CurrentNode->Parent->Color){
        FNode = CurrentNode->Parent;
        GNode = FNode->Parent;
        if(GNode->Left == FNode){
            UNode = GNode->Right;
            if(Red == FNode->Color&&Red == UNode->Color){
                FNode->Color = UNode->Color = Black;
                GNode->Color = Red;
                CurrentNode = GNode;
            }
            else{
                if(CurrentNode == FNode->Right){
                    T = RBLeftRotate(T, FNode);
                    CurrentNode = FNode;
                    FNode = CurrentNode->Parent;
                }
                FNode->Color = Black;
                GNode->Color = Red;
                T = RBRightRotate(T, GNode);
            }
        }
        else{
            UNode = GNode->Left;
            if(Red == FNode->Color&&Red == UNode->Color){
                FNode->Color = UNode->Color = Black;
                GNode->Color = Red;
                CurrentNode = GNode;
            }
            else{
                if(CurrentNode == FNode->Left){
                    T = RBRightRotate(T, FNode);
                    CurrentNode = FNode;
                    FNode = CurrentNode->Parent;
                }
                FNode->Color = Black;
                GNode->Color = Red;
                T = RBLeftRotate(T, GNode);
            }
        }
    }
    T->Root->Color = Black;
    
    return T;
}

Delete

紅黑樹的刪除和BST的刪除也是類似的，區別在於紅黑樹刪除後需要保持性質。這就同樣需要在刪除過後進行調整。而紅黑樹的刪除主要是對於單支黑節點（即一個黑節點只有左子樹或只有右子樹）的操作。

因為刪除紅色葉節點對於紅黑樹的性質沒有影響，刪除黑色葉節點因為存在著sentinel節點，所以可以歸入刪除黑色internal節點的情況。
而對於刪除internal節點，則分為左右子樹均非空的節點，單支黑節點，單支紅節點三種情況：

如果該internal節點左右子樹均非空，則像BST那樣在右子樹中找中綴後繼節點，用後繼節點的值來替換待刪除的internal節點的值，internal節點的其余成員值保持不變，就相當於刪除了該節點，同時繼續對後繼節點進行刪除操作，實際上就可以歸入刪除單支節點的情況；
如果該internal節點為單支紅節點，則不論其子節點是紅是黑，均不符合紅黑樹的性質，所以實際上並不存在此種情況；
如果該internal節點為單支黑節點，那麼像BST那樣將其子樹接上，就相當於是刪除了該節點。而這樣一來，因為刪除了一個黑節點，對於紅黑樹的第五個性質造成了破壞，這裡就需要對紅黑樹進行調整。

因此實際上在具體實現中我們僅在被刪除節點為黑節點時進行調整，所以在具體實現的PtrRBT RBDelete(PtrRBT T, ElementType Val)中，需要用一個臨時變量DeleteNode來記錄待刪除節點，並在刪除執行完之後判斷待刪除節點的顏色，以便確定是否需要調用PtrRBT RBDeleteFixUp(PtrRBT T, PtrRBTNode FixUpNode)函數進行調整：

if(Black == DeleteNode->Color){
    T = RBDeleteFixUp(T, FixUpNode);
}

而以上所說的調整則是需要根據被刪除的單支黑節點的子節點的Color來判斷的。如果其子節點是黑色的，則有四種不同的情況，在RBDeleteFixUp函數的具體實現中需要進入一個while循環來處理，如果其子節點是紅色的，則無需進入循環，直接執行循環後的FixUpNode->Color = Black;，就是將其子節點的Color變為黑色，相當於增加了一個黑節點來消除刪除一個黑節點對紅黑樹性質的影響。

對於四種不同情況，《算法導論》上介紹的很明白了，下面主要說明Case2、4的情況，並通過注釋來介紹Case1、3和具體實現：

當然需要特別注意的是，所謂的待調整節點其實就是沿待調整節點比沿待調整節點的Sibling節點至葉節點的Black節點數少1，所以在調整過程中我們只在待調整節點為黑且不為根節點時做調整，因為待調整節點為紅時僅需將其置為黑既能保持紅黑樹性質，而待調整節點為根節點時相當於這一次刪除最終使得整棵紅黑樹中根節點至葉節點的路徑的Black節點數均減少1，但仍然符合紅黑樹性質。

Case Two

此情況下，不論祖父節點B是何種顏色，均將父節點的Sibling節點D顏色置為Red，這樣可以使上圖情況2中沿A節點和D節點至葉節點的路徑具有相同的Black節點數，但是卻使得圖中沿B節點至葉節點的路徑的Black節點數減少1，這樣相當於B節點等價於一個待調整節點，因為待調整節點的一個特點就是沿待調整節點比沿待調整節點的Sibling節點至葉節點的Black節點數少1，因此將待調整節點變為B即可，並繼續循環，若B為紅則跳出循環後將其顏色置為黑，若B為黑則繼續循環判斷是Case1、2、3、4中的何種情況。

更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2017-01/139950p2.htm