第C++超詳細(xì)分析紅黑樹目錄紅黑樹紅黑樹的概念紅黑樹的性質(zhì)紅黑樹結(jié)點(diǎn)的定義紅黑樹的插入操作情況一情況二情況三紅黑樹的驗(yàn)證用紅黑樹封裝map、set紅黑樹的迭代器封裝map封裝set

紅黑樹

紅黑樹的概念

紅黑樹的概念紅黑樹，是一種二叉搜索樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的。

紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的時(shí)間復(fù)雜度都是O()，紅黑樹不追求絕對(duì)平衡，其只需保證最長(zhǎng)路徑不超過(guò)最短路徑的2倍，相對(duì)而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，而且紅黑樹實(shí)現(xiàn)比較簡(jiǎn)單，所以實(shí)際運(yùn)用中紅黑樹更多。

紅黑樹的性質(zhì)

每個(gè)結(jié)點(diǎn)不是紅色就是黑色根節(jié)點(diǎn)是黑色的如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的對(duì)于每個(gè)結(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)每個(gè)葉子結(jié)點(diǎn)都是黑色的（此處的葉子節(jié)點(diǎn)指的是空結(jié)點(diǎn)，如上圖路徑數(shù)為11條）

紅黑樹結(jié)點(diǎn)的定義

enumColor{

BLACK,

templateclassT

structRBTreeNode

RBTreeNodeT*_left;

RBTreeNodeT*_right;

RBTreeNodeT*_parent;

Color_col;

T_data;

RBTreeNode(constTdata)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_col（RED)

，_data(data)

紅黑樹的插入操作

約定：cur為當(dāng)前節(jié)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)

情況一

情況一：cur為紅，p為紅，g為黑，u存在且為紅注意：此處看到的樹，可能是一棵完整的樹，也可能是一棵子樹解決方式：將p，u改為黑，g改為紅，然后把g當(dāng)成cur，繼續(xù)向上調(diào)整

如果g是根節(jié)點(diǎn)，調(diào)整完成后，需要將g改為黑色

如果g是子樹，g一定有雙親，且g的雙親如果是紅色，需要繼續(xù)向上調(diào)整。

情況二

情況二：cur為紅，p為紅，g為黑，u不存在/u為黑

解決方法：p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋；p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋。

p變黑，g變紅。

1.如果u節(jié)點(diǎn)不存在，則cur一定是新插入節(jié)點(diǎn)，因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn)，則cur和p一定有一個(gè)節(jié)點(diǎn)的顏色是黑色，就不滿足性質(zhì)4：每條路徑黑色節(jié)點(diǎn)個(gè)數(shù)相同。

2.如果u節(jié)點(diǎn)存在，則其一定是黑色的，cur一定不是新增節(jié)點(diǎn)，那么cur節(jié)點(diǎn)原來(lái)的顏色一定是黑色的，是作為子樹的祖父，由第一種情況變化過(guò)來(lái)的

情況三

情況三：cur為紅，p為紅，g為黑，u不存在/u為黑（折線型）

p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋轉(zhuǎn)；

p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋轉(zhuǎn)。

即轉(zhuǎn)換為了情況二。再對(duì)g做對(duì)于旋轉(zhuǎn)。即進(jìn)行雙旋轉(zhuǎn)。

//T-Kset

//T-pairconstK,Vmap

templateclassK,classT,classKeyOfT

classRBTree

typedefRBTreeNodeTNode;

public:

typedefRBTreeIteratorT,T,T*iterator;

typedefRBTreeIteratorT,constT,constT*const_iterator;

iteratorbegin();

iteratorend();

RBTree()

:_root(nullptr)

//拷貝構(gòu)造和賦值重載

//析構(gòu)

Node*Find(constKkey);

pairiterator,boolInsert(constTdata)

if(_root==nullptr)

_root=newNode(data);

_root-_col=BLACK;

returnmake_pair(iterator(_root),true);

Node*parent=nullptr;

Node*cur=_root;

KeyOfTkot;

while(cur)

if(kot(cur-_data)kot(data))

parent=cur;

cur=cur-_right;

elseif(kot(cur-_data)kot(data))

parent=cur;

cur=cur-_left;

else

returnmake_pair(iterator(cur),false);

//新增節(jié)點(diǎn)，顏色是紅色，可能破壞規(guī)則3，產(chǎn)生連續(xù)紅色節(jié)點(diǎn)

cur=newNode(data);

Node*newnode=cur;

cur-_col=RED;

if(kot(parent-_data)kot(data))

parent-_right=cur;

cur-_parent=parent;

else

parent-_left=cur;

cur-_parent=parent;

//控制近似平衡

while(parentparent-_col==RED)

Node*grandfather=parent-_parent;

if(parent==grandfather-_left)

Node*uncle=grandfather-_right;

//情況一：uncle存在且為紅，進(jìn)行變色處理，并繼續(xù)往上更新處理

if(uncleuncle-_col==RED)

parent-_col=uncle-_col=BLACK;

grandfather-_col=RED;

cur=grandfather;

parent=cur-_parent;

}//情況二+三：uncle不存在，或者存在且為黑，需要旋轉(zhuǎn)+變色處理

else

//情況二：?jiǎn)涡?變色

if(cur==parent-_left)

RotateR(grandfather);

parent-_col=BLACK;

grandfather-_col=RED;

else//情況三：雙旋+變色

RotateL(parent);

RotateR(grandfather);

cur-_col=BLACK;

grandfather-_col=RED;

break;

else//(parent==grandfather-_right)

Node*uncle=grandfather-_left;

if(uncleuncle-_col==RED)

parent-_col=uncle-_col=BLACK;

grandfather-_col=RED;

cur=grandfather;

parent=cur-_parent;

else

if(parent-_right==cur)

RotateL(grandfather);

parent-_col=BLACK;

grandfather-_col=RED;

else

RotateR(parent);

RotateL(grandfather);

cur-_col=BLACK;

grandfather-_col=RED;

break;

_root-_col=BLACK;

returnmake_pair(iterator(newnode),true);

voidRotateR(Node*parent);

voidRotateL(Node*parent);

private:

Node*_root;

紅黑樹的驗(yàn)證

紅黑樹的檢測(cè)分為兩步：

檢測(cè)其是否滿足二叉搜索樹(中序遍歷是否為有序序列)檢測(cè)其是否滿足紅黑樹的性質(zhì)

此處用未改造過(guò)的紅黑樹

templateclassK,classV

structRBTreeNode

RBTreeNodeK,V*_left;

RBTreeNodeK,V*_right;

RBTreeNodeK,V*_parent;

Colour_col;

pairK,V_kv;

RBTreeNode(constpairK,Vkv)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_col(RED)

,_kv(kv)

templateclassK,classV

classRBTree

typedefRBTreeNodeK,VNode;

public:

RBTree()

:_root(nullptr)

boolInsert(constpairK,Vkv);

voidRotateR(Node*parent);

voidRotateL(Node*parent);

void_InOrder(Node*root)

if(root==nullptr)

return;

_InOrder(root-_left);

coutroot-_kv.first"";

_InOrder(root-_right);

voidInOrder()

_InOrder(_root);

coutendl;

boolCheckRED_RED(Node*cur)

if(cur==nullptr)

returntrue;

if(cur-_col==REDcur-_parent-_col==RED)

cout"違反規(guī)則三，存在連續(xù)的紅色節(jié)點(diǎn)"endl;

returnfalse;

returnCheckRED_RED(cur-_left)

CheckRED_RED(cur-_right);

//檢查每條路徑黑色節(jié)點(diǎn)的數(shù)量

boolCheckBlackNum(Node*cur,intblackNum,intbenchmark){

if(cur==nullptr){

if(blackNum!=benchmark){

cout"違反規(guī)則四：黑色節(jié)點(diǎn)的數(shù)量不相等"endl;

returnfalse;}

returntrue;

if(cur-_col==BLACK)

++blackNum;

returnCheckBlackNum(cur-_left,blackNum,benchmark)

CheckBlackNum(cur-_right,blackNum,benchmark);

boolIsBalance()

if(_root==nullptr)

returntrue;

if(_root-_col==RED)

cout"根節(jié)點(diǎn)是紅色，違反規(guī)則二"endl;

returnfalse;

//算出最左路徑的黑色節(jié)點(diǎn)的數(shù)量作為基準(zhǔn)值

intbenchmark=0;

Node*cur=_root;

while(cur)

if(cur-_col==BLACK)

++benchmark;

cur=cur-_left;

intblackNum=0;

returnCheckRED_RED(_root)CheckBlackNum(_root,blackNum,benchmark);

private:

Node*_root;

voidTestRBTree1()

constintn=1000000;

vectorint

a.reserve(n);

srand(time(0));

for(size_ti=0;i++i)

a.push_back(rand());

RBTreeint,int

for(autoe:a)

t1.Insert(make_pair(e,e));

coutt1.IsBalance()endl;

//t1.InOrder();

用紅黑樹封裝map、set

紅黑樹的迭代器

begin()與end()

begin()可以放在紅黑樹中最小節(jié)點(diǎn)(即最左側(cè)節(jié)點(diǎn))的位置

end()放在最大節(jié)點(diǎn)(最右側(cè)節(jié)點(diǎn))的下一個(gè)位置

typedefRBTreeIteratorT,T,T*iterator;

typedefRBTreeIteratorT,constT,constT*const_iterator;

iteratorbegin()

Node*left=_root;

while(leftleft-_left)

left=left-_left;

//returnleft

returniterator(left);

iteratorend()

returniterator(nullptr);

操作符重載

templateclassT,classRef,classPtr

structRBTreeIterator

typedefRBTreeNodeTNode;

typedefRBTreeIteratorT,Ref,PtrSelf;

Node*_node;

RBTreeIterator(Node*node=nullptr)

:_node(node)

Refoperator*()

return_node-_data;

Ptroperator-()

return_node-_data;

Selfoperator--()

//跟++基本是反過(guò)來(lái)

return*this;

Selfoperator++()

if(_node-_right)

//右子樹中序第一個(gè)節(jié)點(diǎn)，也就是右子樹的最左節(jié)點(diǎn)

Node*subLeft=_node-_right;

while(subLeft-_left)

subLeft=subLeft-_left;

_node=subLeft;

else

//當(dāng)前子樹已經(jīng)訪問(wèn)完了，要去找祖先訪問(wèn)，沿著到根節(jié)點(diǎn)的路徑往上走，

//找孩子是父親左的那個(gè)父親節(jié)點(diǎn)

Node*cur=_node;

Node*parent=cur-_parent;

while(parentparent-_right==cur)

cur=parent;

parent=parent-_parent;

_node=parent;

return*this;

booloperator!=(constSelfs)const

return_node!=s._node;

booloperator==(constSelfs)const

return_node==s._node;

封裝map

#pragmaonce

#include"RBTree.h"

namespaceMyMap

templateclassK,classV

classmap

structMapKeyOfT

constKoperator()(constpairconstK,Vkv)

returnkv.first;

public:

typedeftypenameRBTreeK,pairconstK,V,MapKeyOfT::iteratoriterator;

iteratorbegin()

return_t.begin();

iteratorend()

return_t.end();

pairiterator,boolinsert(constpairconstK,Vkv)

return_t.Insert(kv);

Voperator[](constKkey)

pairiterator,boolret=_t.Insert(make_pair(key,V()));

returnret.first-second;

private:

RBTreeK,pairconstK,V,MapKeyOfT

voidtest_map()

mapstring,stringdict;

dict.insert(make_pair("sort","排序"));

dict.insert(make_pair("string","字符串"));

dict.insert(make_pair("debug","找蟲子"));

dict.insert(make_pair("set","集合"));

mapstring,string::iteratorit=dict.