第C++詳細實現紅黑樹流程詳解目錄紅黑樹的概念紅黑樹的性質紅黑樹的定義與樹結構插入新增結點插入后維護紅黑樹性質的主邏輯旋轉驗證紅黑樹與AVl樹的比較紅黑樹的應用

紅黑樹的概念

紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的

概念總結：

紅黑樹是二叉搜索樹的升級，結點里面存放的成員col標記當前結點的顏色，它的最長路徑最多是最短路徑的二倍，紅黑樹通過各個結點著色方式的限制接近平衡二叉樹，但是不同于AVL的是AVL是一顆高度平衡的二叉樹，紅黑樹只是接近平衡

紅黑樹的性質

每個結點不是紅色就是黑色根節點是黑色的如果一個節點是紅色的，則它的兩個孩子結點是黑色的對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑色結點每個葉子結點都是黑色的(此處的葉子結點指的是空結點)

紅黑樹性質總結：

1、紅黑樹結點的顏色只能是紅色或者黑色

2、紅黑樹根節點必須是黑色

3、紅黑樹并沒有連續的紅色結點

4、紅黑樹中從根到葉子的每一條路徑都包含相同的黑色結點

5、葉子是黑色，表示空的位置

最長路徑和最短路徑概念：

最短路徑：從根結點到葉子結點每一條路徑的結點顏色都是黑色的不包含紅色

最長路徑：紅黑交替，黑色結點和紅色結點的個數相等

思考：為什么滿足上面的性質，紅黑樹就能保證：其最長路徑中節點個數不會超過最短路徑節點個數的兩倍？

假設結點個數為N，那么最短路徑就是logN，最長路徑就是2*logN，所有并不存在最長路徑超過最短路徑2倍的情況

紅黑樹的定義與樹結構

//枚舉紅黑顏色

enumcolour

RED,

BLACK,

//定義紅黑樹結點結構

templateclassK,classV

structRBTreeNode

//構造

RBTreeNode(constpairK,Vkv={0,0})

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_kv(kv)

,_col(BLACK)

//定義三叉鏈

RBTreeNodeK,V*_left;//左孩子

RBTreeNodeK,V*_right;//右孩子

RBTreeNodeK,V*_parent;//父親

pairK,V_kv;//pair對象

//節點的顏色

colour_col;//定義枚舉變量

//定義紅黑樹

templateclassK,classV

classRBTree

typedefRBTreeNodeK,VNode;

public:

//構造

RBTree()

:_root(nullptr)

private:

Node*_root;//定義樹的根節點

插入

插入過程類似搜索樹的插入，重要的是維護紅黑樹的性質

pairNode*,boolInsert(constpairK,Vkv)

if(!_root)//空樹處理

_root=newNode(kv);

_root-_col=BLACK;

return{_root,true};

//二叉搜索樹的插入邏輯

Node*cur=_root,*parent=nullptr;

while(cur)

if(cur-_kv.firstkv.first)//插入結點比當前結點大

parent=cur;

cur=cur-_right;

elseif(cur-_kv.firstkv.first)//插入結點比當前結點小

parent=cur;

cur=cur-_left;

else

return{cur,false};//插入失敗

cur=newNode(kv);

cur-_col=RED;//新增結點顏色默認設置為RED

//判斷插入結點是否在parent的左邊或者右邊

if(parent-_kv.firstkv.first)//左邊

parent-_left=cur;

cur-_parent=parent;

else//右邊

parent-_right=cur;

cur-_parent=parent;

/*紅黑樹性質處理：

如果這棵樹一開始是符合紅黑樹的性質，但在新增結點之后，

導致失去了紅黑樹的性質，這里需要控制結點的顏色和限制

每條路徑上黑色結點的個數，以上情況都要處理

while(parentparent-_col==RED)//父親存在且父親為紅色

Node*grandfather=parent-_parent;//祖父

//父親出現在祖父的左邊需要考慮的情況

if(parent==grandfather-left)

//1、uncle存在，uncle為紅色

如果parent和uncle都存在并且都為紅色這是情況一，

需要將parent和uncle的顏色變成紅色，祖父顏色變成黑色

更新cur、parent、grandfather、uncle繼續向上調整

//2、uncle不存在

/*這里考慮兩種旋轉情況，直線單旋轉，折線雙旋

cur出現在parent的左邊,右單旋轉

經過右單旋后，parent去做樹的根,祖父做為右子樹

//調節結點顏色

parent-_col=BLACK;

grandfather-_col=RED;

cur出現在parent的右邊，左右雙旋

經過雙旋后，cur作為樹的根，grandfather為右子樹

調節結點顏色

cur-_col=BLACK;

grandfather-_col=RED;

else//父親出現在祖父的右邊

Node*uncle=grandfather-_left;//叔叔在左子樹

情況一：叔叔存在，且叔叔和父親都是紅色，那么就需要將父親

和叔叔結點的顏色變成黑色，再將祖父的顏色變成紅色，

繼續向上調整，更新孩子、父親、祖父、叔叔的位置

情況二：叔叔不存在

1、新增結點出現在父親的右邊，直線情況，左單旋處理

旋轉完后parent去做父親的根，grandfather做父親

的左子樹

//調節顏色，根為黑，左右孩子為紅

2、新增結點出現在父親的左邊，會出現折現的情況，

引發雙旋，旋轉完后，cur變成根，

parent和grandfaher去做cur的左右孩子

//調節顏色,根結點為黑，左右孩子為紅

//如果父親不存在為了保證根結點是黑色的，這里一定得將根結點處理為黑色

_root-_col=BLACK;

}

新增結點插入后維護紅黑樹性質的主邏輯

//1、父親一定存在的情況，叔叔存在/不存在父親叔叔結點顏色為紅色

while(parentparent-_col==RED)//父親存在且父親為紅色

Node*grandfather=parent-_parent;//祖父

//如果父親和叔叔結點顏色都是紅色

if(parent==grandfather-_left)

Node*uncle=grandfather-_right;

if(uncleuncle-_col==RED)//對應情況：uncle存在且為紅

//處理：父親和叔叔變成黑色，祖父變成紅色，繼續向上調整

uncle-_col=parent-_col=BLACK;

grandfather-_col=RED;

//向上調整

cur=grandfather;//調整孩子

parent=cur-_parent;//調整父親

else//uncle不存在，uncle存在且為黑

//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉點進行右單旋轉，

//旋轉完后將祖父的顏色變成紅色，將父親的顏色變成黑色

if(parent-_left==cur)

RotateR(grandfather);

parent-_col=BLACK;

grandfather-_col=RED;

else//parent-_right==cur

//折線情況(cur在parent的右邊)：這里會引發雙旋

RotateL(parent);//以parent為旋轉點進行左單旋

RotateR(grandfather);//以grandfather為旋轉點進行右單旋轉

//旋轉完后cur會去做樹的根，那么設置為黑色，

//為了保證每條路徑的黑色結點個數相同，grandfather結點顏色設置為紅

cur-_col=BLACK;

grandfather-_col=RED;//黑色結點個數相同

else//父親在右子樹

Node*uncle=grandfather-_left;//叔叔在左子樹

if(uncleuncle-_col==RED)//情況一處理：叔叔存在，且叔叔的顏色是紅色的（包含了父親的顏色是紅色的情況）

//根據情況一處理即可：叔叔和父親變黑，

//祖父變紅(目的是為了每條路徑的黑色結點個數相同)，繼續向上

cur=grandfather;//孩子

parent=cur-_parent;//父親

else//叔叔不存在

if(cur==parent-_right)//新增結點在父親的右邊，直線情況左單旋處理

//左單旋轉，以grandfather為旋轉點，旋轉完后parent去做新的根，grandfather去做左子樹

RotateL(grandfather);

//調節顏色

grandfather-_col=RED;

parent-_col=BLACK;

else//新增結點在父親的左邊，折線情況，引發雙旋

//處理：以parenrt為旋轉點做右單旋，再以grandfather為旋轉點做左單旋

RotateR(parent);//右旋

RotateL(grandfather);//左旋

parent-_col=grandfather-_col=RED;

cur-_col=BLACK;

break;

_root-_col=BLACK;

}

拆解討論：

以下只列舉parent在grandfather左邊的情況，而parent在grandfather右邊的情況處理方式只是反過來的，讀者可以自行畫圖，這里僅留參考代碼

Node*uncle=grandfather-_right;

if(uncleuncle-_col==RED)//對應情況：uncle存在且為紅

//處理：父親和叔叔變成黑色，祖父變成紅色，繼續向上調整

uncle-_col=parent-_col=BLACK;

grandfather-_col=RED;

//向上調整

cur=grandfather;//調整孩子

parent=cur-_parent;//調整父親

}

else//uncle不存在，uncle存在且為黑

//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉點進行右單旋轉，

//旋轉完后將祖父的顏色變成紅色，將父親的顏色變成黑色

if(parent-_left==cur)

RotateR(grandfather);

parent-_col=BLACK;

grandfather-_col=RED;

else//parent-_right==cur

//雙旋轉

//折線情況(cur在parent的右邊)：這里會引發雙旋

RotateL(parent);//以parent為旋轉點進行左單旋

RotateR(grandfather);//以grandfather為旋轉點進行右單旋轉

//旋轉完后cur會去做樹的根，那么設置為黑色，

//為了保證每條路徑的黑色結點個數相同，grandfather結點顏色設置為紅

cur-_col=BLACK;

grandfather-_col=RED;

旋轉

voidRotateR(Node*parent)//右單旋

Node*subL=parent-_left;

Node*subLR=subL-_right;

parent-_left=subLR;

if(subLR)subLR-_parent=parent;//防止subLR為nullptr

subL-_right=parent;

Node*parent_parent=parent-_parent;//指針備份

parent-_parent=subL;

if(_root==parent)//如果parent就是樹的根

_root=subL;//subL取代parent

_root-_parent=nullptr;

else//如果parent并不是樹的根

if(parent_parent-_left==parent)parent-_left=subL;

elseparent_parent-_right=subL;

subL-_parent=parent_parent;//subL去做parent_parent的孩子

//左單旋

voidRotateL(Node*parent)

Node*subR=parent-_right;

Node*subRL=subR-_left;

parent-_right=subRL;

if(subRL)subRL-_parent=parent;

subR-_left=parent;

Node*parent_parent=parent-_parent;

parent-_parent=subR;

if(_root==parent)

_root=subR;

_root-_parent=nullptr;

else

if(parent_parent-_left==parent)parent_parent-_left=subR;

elseparent_parent-_right=subR;

subR-_parent=parent_parent;

}

驗證

/*

紅黑樹的幾點性質在于：

1、根結點必須是紅色的

2、不會出現連續的紅色結點

3、所有路徑的黑色結點個數是相同的

bool_CheckBlance(Node*root,intisBlackNum,intcount)

if(!root)

if(isBlackNum!=count)

printf("黑色結點個數不均等\n");

returnfalse;

returntrue;//遍歷完整棵樹，如果以上列舉的非法情況都不存在就返回true

//檢查是否出現連續的紅色結點

if(root-_col==REDroot-_parent-_col==RED)

printf("出現了連續的紅色結點\n");

returnfalse;

//走前序遍歷的過程中記錄每一條路徑黑色結點的個數

if(root-_col==BLACK)count++;