柚子快報(bào)邀請(qǐng)碼778899分享：c++ 【數(shù)據(jù)結(jié)構(gòu)】紅黑樹

http://yzkb.51969.com/

文章目錄

1, 紅黑樹的概念2. 紅黑樹的性質(zhì)3. 紅黑樹節(jié)點(diǎn)的定義4. 紅黑樹的結(jié)構(gòu)5. 紅黑樹的插入操作6. 紅黑樹的驗(yàn)證7. 紅黑樹與 AVL 樹的比較8. 紅黑樹的應(yīng)用

1, 紅黑樹的概念

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

2. 紅黑樹的性質(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)）。

思考：為什么滿足上面的性質(zhì)，紅黑樹就能保證：其最長(zhǎng)路徑中節(jié)點(diǎn)個(gè)數(shù)不會(huì)超過最短路徑節(jié)點(diǎn)個(gè)數(shù)的兩倍？

3. 紅黑樹節(jié)點(diǎn)的定義

// 節(jié)點(diǎn)的顏色

enum Color { RED, BLACK };

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

template

struct RBTreeNode

{

RBTreeNode(const ValueType& data = ValueType()，Color color = RED)

: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)

, _data(data), _color(color)

{}

RBTreeNode* _pLeft; // 節(jié)點(diǎn)的左孩子

RBTreeNode* _pRight; // 節(jié)點(diǎn)的右孩子

RBTreeNode* _pParent; // 節(jié)點(diǎn)的雙親(紅黑樹需要旋轉(zhuǎn)，為了實(shí)現(xiàn)簡(jiǎn)單給出該字段)

ValueType _data; // 節(jié)點(diǎn)的值域

Color _color; // 節(jié)點(diǎn)的顏色

};

思考：在節(jié)點(diǎn)的定義中，為什么要將節(jié)點(diǎn)的默認(rèn)顏色給成紅色的？

4. 紅黑樹的結(jié)構(gòu)

為了后續(xù)實(shí)現(xiàn)關(guān)聯(lián)式容器簡(jiǎn)單，紅黑樹的實(shí)現(xiàn)中增加一個(gè)頭節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)必須為黑色，為了與根節(jié)點(diǎn)進(jìn)行區(qū)分，將頭節(jié)點(diǎn)給成黑色，并且讓頭節(jié)點(diǎn)的 pParent 域指向紅黑樹的根節(jié)點(diǎn)，pLeft 域指向紅黑樹中最小的節(jié)點(diǎn)，pRight 域指向紅黑樹中最大的節(jié)點(diǎn)，如下：

5. 紅黑樹的插入操作

紅黑樹是在二叉搜索樹的基礎(chǔ)上加上其平衡限制條件，因此紅黑樹的插入可分為兩步：

按照二叉搜索樹的樹規(guī)則插入新節(jié)點(diǎn)： template

class RBTree

{

//……

bool Insert(const ValueType& data)

{

PNode& pRoot = GetRoot();

if (nullptr == pRoot)

{

pRoot = new Node(data, BLACK);

// 根的雙親為頭節(jié)點(diǎn)

pRoot->_pParent = _pHead;

_pHead->_pParent = pRoot;

}

else

{

// 1. 按照二叉搜索的樹方式插入新節(jié)點(diǎn)

// 2. 檢測(cè)新節(jié)點(diǎn)插入后，紅黑樹的性質(zhì)是否造到破壞，

// 若滿足直接退出，否則對(duì)紅黑樹進(jìn)行旋轉(zhuǎn)著色處理

}

// 根節(jié)點(diǎn)的顏色可能被修改，將其改回黑色

pRoot->_color = BLACK;

_pHead->_pLeft = LeftMost();

_pHead->_pRight = RightMost();

return true;

}

private:

PNode& GetRoot() { return _pHead->_pParent; }

// 獲取紅黑樹中最小節(jié)點(diǎn)，即最左側(cè)節(jié)點(diǎn)

PNode LeftMost();

// 獲取紅黑樹中最大節(jié)點(diǎn)，即最右側(cè)節(jié)點(diǎn)

PNode RightMost();

private:

PNode _pHead;

};

檢測(cè)新節(jié)點(diǎn)插入后，紅黑樹的性質(zhì)是否遭到破壞： 因?yàn)樾鹿?jié)點(diǎn)的默認(rèn)顏色是紅色，因此：如果其雙親節(jié)點(diǎn)的顏色是黑色，沒有違反紅黑樹任何性質(zhì)，則不需要調(diào)整；但當(dāng)新插入節(jié)點(diǎn)的雙親節(jié)點(diǎn)顏色為紅色時(shí)，就違反了性質(zhì)三：不能有連在一起的紅色節(jié)點(diǎn)，此時(shí)需要對(duì)紅黑樹分情況來討論： 約定：cur 為當(dāng)前節(jié)點(diǎn)，p 為父節(jié)點(diǎn)，g 為祖父節(jié)點(diǎn)，u 為叔叔節(jié)點(diǎn)。

情況一：cur 為紅，p 為紅，g 為黑，u 存在且為紅 cur 和 p 均為紅，違反了性質(zhì)三，此處能否將 p 直接改為黑？ 解決方式：將 p，u 改為黑，g 改為紅，然后把 g 當(dāng)成 cur，繼續(xù)向上調(diào)整。 情況二：cur 為紅，p 為紅，g 為黑，u 不存在 / u 存在且為黑 p 為 g 的左孩子，cur 為 p 的左孩子，則進(jìn)行右單旋轉(zhuǎn)；相反， p 為 g 的右孩子，cur 為 p 的右孩子，則進(jìn)行左單旋轉(zhuǎn)； p、g 變色 – p 變黑，g 變紅。 情況三：cur 為紅，p 為紅，g 為黑，u 不存在 / u 存在且為黑 p 為 g 的左孩子，cur 為 p 的右孩子，則針對(duì) p 做左單旋轉(zhuǎn)；相反， p 為 g 的右孩子，cur 為 p 的左孩子，則針對(duì) p 做右單旋轉(zhuǎn)； 則轉(zhuǎn)換成了情況 2。 針對(duì)每種情況進(jìn)行相應(yīng)的處理即可。 bool Insert(const ValueType& data)

{

// ...

// 新節(jié)點(diǎn)插入后，如果其雙親節(jié)點(diǎn)的顏色為空色，則違反性質(zhì)3：不能有連在一起的紅色結(jié)點(diǎn)

while (pParent && RED == pParent->_color)

{

// 注意：grandFather一定存在

// 因?yàn)閜Parent存在，且不是黑色節(jié)點(diǎn)，則pParent一定不是根，則其一定有雙親

PNode grandFather = pParent->_pParent;

// 先討論左側(cè)情況

if (pParent == grandFather->_pLeft)

{

PNode unclue = grandFather->_pRight;

// 情況三：叔叔節(jié)點(diǎn)存在，且為紅

if (unclue && RED == unclue->_color)

{

pParent->_color = BLACK;

unclue->_color = BLACK;

grandFather->_color = RED;

pCur = grandFather;

pParent = pCur->_pParent;

}

else

{

// 情況五：叔叔節(jié)點(diǎn)不存在，或者叔叔節(jié)點(diǎn)存在且為黑

if (pCur == pParent->_pRight)

{

_RotateLeft(pParent);

swap(pParent, pCur);

}

// 情況五最后轉(zhuǎn)化成情況四

grandFather->_color = RED;

pParent->_color = BLACK;

_RotateRight(grandFather);

}

}

else

{

// 右側(cè)請(qǐng)大家自己動(dòng)手完成

}

}

// ...

}

6. 紅黑樹的驗(yàn)證

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

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

bool IsValidRBTree()

{

PNode pRoot = GetRoot();

// 空樹也是紅黑樹

if (nullptr == pRoot)

return true;

// 檢測(cè)根節(jié)點(diǎn)是否滿足情況

if (BLACK != pRoot->_color)

{

cout << "違反紅黑樹性質(zhì)二：根節(jié)點(diǎn)必須為黑色" << endl;

return false;

}

// 獲取任意一條路徑中黑色節(jié)點(diǎn)的個(gè)數(shù)

size_t blackCount = 0;

PNode pCur = pRoot;

while (pCur)

{

if (BLACK == pCur->_color)

blackCount++;

pCur = pCur->_pLeft;

}

// 檢測(cè)是否滿足紅黑樹的性質(zhì)，k用來記錄路徑中黑色節(jié)點(diǎn)的個(gè)數(shù)

size_t k = 0;

return _IsValidRBTree(pRoot, k, blackCount);

}

bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)

{

//走到null之后，判斷k和black是否相等

if (nullptr == pRoot)

{

if (k != blackCount)

{

cout << "違反性質(zhì)四：每條路徑中黑色節(jié)點(diǎn)的個(gè)數(shù)必須相同" << endl;

return false;

}

return true;

}

// 統(tǒng)計(jì)黑色節(jié)點(diǎn)的個(gè)數(shù)

if (BLACK == pRoot->_color)

k++;

// 檢測(cè)當(dāng)前節(jié)點(diǎn)與其雙親是否都為紅色

PNode pParent = pRoot->_pParent;

if (pParent && RED == pParent->_color && RED == pRoot->_color)

{

cout << "違反性質(zhì)三：沒有連在一起的紅色節(jié)點(diǎn)" << endl;

return false;

}

return _IsValidRBTree(pRoot->_pLeft, k, blackCount)

&& _IsValidRBTree(pRoot->_pRight, k, blackCount);

}

7. 紅黑樹與 AVL 樹的比較

紅黑樹和 AVL 樹都是高效的平衡二叉樹，增刪改查的時(shí)間復(fù)雜度都是 O(

l

o

g

2

N

log_2 N

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

8. 紅黑樹的應(yīng)用

C++ STL 庫 – map / set、multi_map / multi_set；Java 庫；Linux 內(nèi)核；其他一些庫；…

END

柚子快報(bào)邀請(qǐng)碼778899分享：c++ 【數(shù)據(jù)結(jié)構(gòu)】紅黑樹

http://yzkb.51969.com/

參考閱讀