C++紅黑樹的底層實現(xiàn)機制詳解
前言
紅黑樹與AVL樹一樣，也是一種自平衡的二叉搜索樹，它在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black，通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近 平衡的。
1.紅黑樹結(jié)構(gòu)
紅黑樹的性質(zhì)：
- 每個結(jié)點不是紅色就是黑色
- 根節(jié)點是黑色的
- 如果一個節(jié)點是紅色的，則它的兩個孩子結(jié)點是黑色的
- 對于每個結(jié)點，從該結(jié)點到其所有后代葉結(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點
所以紅黑樹的節(jié)點必須包含一個值類存儲該節(jié)點的顏色，我們可以利用枚舉來實現(xiàn)：
//枚舉顏色
enum Colour
{
RED,
BLACK
};
//節(jié)點類
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv; //存放數(shù)據(jù)
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col; //保存顏色
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
,_col(RED)
{}
};
//紅黑樹類
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
// 在紅黑樹中插入值為data的節(jié)點，插入成功返回true，否則返回false
bool Insert(const pair<K, V>& data);
// 檢測紅黑樹是否為有效的紅黑樹
bool IsValidRBTRee();
//中序遍歷
void InOrder()
{
_InOrder(_pHead);
}
private:
void _InOrder(Node* root);
bool Check(Node* root, int blackNum, const int refNum);
// 左單旋
void RotateL(Node* parent);
// 右單旋
void RotateR(Node* parent);
private:
Node* _pHead = nullptr;
};
2.紅黑樹的插入
紅黑樹是在二叉搜索樹的基礎(chǔ)上加上其平衡限制條件，因此紅黑樹的插入可分為兩步：
- 按照二叉搜索的樹規(guī)則插入新節(jié)點
- 檢測新節(jié)點插入后，紅黑樹的性質(zhì)是否造到破壞，如果破壞進行相應(yīng)的修改操作
在插入新節(jié)點時，我們先確定一下新節(jié)點的顏色，如果是黑色，那么在插入后該條子路徑上就會多一個黑色節(jié)點，根據(jù)紅黑樹的性質(zhì)需要在其他路徑上都增加一個新節(jié)點才可以，比較麻煩，所以我們將新節(jié)點的顏色設(shè)為紅色，這樣如果其父親是黑色就剛剛好插入成功，如果父親是紅色我們就再來修改；所以我們將新節(jié)點的顏色設(shè)置為紅色：
//節(jié)點類
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv; //存放數(shù)據(jù)
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col; //保存顏色
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
,_col(RED) //直接在構(gòu)造時設(shè)置即可
{}
};
先正常插入節(jié)點：
//1.先找到插入位置
//如果是空樹
if (_pHead == nullptr)
{
Node* newnode = new Node(data);
newnode->_col = BLACK;
_pHead = newnode;
return true;
}
//如果不是空樹
Node* cur = _pHead;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > data.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < data.first)
{
parent = cur;
cur = cur->_right;
}
else
return false;//沒找到返回false
}
//2.找到，插入節(jié)點
Node* newnode = new Node(data);
//判斷插入父節(jié)點左側(cè)還是右側(cè)
if (parent->_kv.first > data.first)
parent->_left = newnode;
else
parent->_right = newnode;
//更新newnode父節(jié)點
newnode->_parent = parent;
如果父節(jié)點是黑色，那么直接插入節(jié)點即可：
if (parent->_col == BLACK)
{
//父節(jié)點是黑色,插入成功
return true;
}
如果父節(jié)點是紅色，那么我們需要調(diào)整：
因為不可能有兩個紅色連在一起，所以我們需要進行調(diào)整；而且父節(jié)點是紅色的話那么父節(jié)點肯定不是根節(jié)點且其父節(jié)點的顏色也只能是黑色，如下圖所示：
這時，我們就需要根據(jù)叔叔節(jié)點來進行調(diào)整節(jié)點：
如果uncle節(jié)點是紅色：
我們就可以將unlcle和parent節(jié)點都變?yōu)楹谏?，grandparent節(jié)點變?yōu)榧t色：
這樣這兩條路徑的黑色節(jié)點依然是一個，沒有變，但是grandparent節(jié)點變?yōu)榧t色，如果它的父節(jié)點是黑色那么調(diào)整成功，但是如果其父節(jié)點是紅色，紅黑樹的性質(zhì)就不滿足，所以我們需要繼續(xù)向上調(diào)整。
如果uncle節(jié)點是黑色：
這時我們發(fā)現(xiàn)uncle節(jié)點的路徑上多了一個黑色節(jié)點，說明cur節(jié)點不可能是新增節(jié)點，這種情況是由上面uncle節(jié)點是紅色情況調(diào)整之后還需要繼續(xù)向上調(diào)整得來的(cur是上面情況的grandparent，grandparent的父節(jié)點也是紅色)，單純的變色已經(jīng)不能維持紅黑樹的性質(zhì)，我們需要進行旋轉(zhuǎn)：
情況一：如果parent為grandparent的左孩子，cur為parent的左孩子，則進行右單旋轉(zhuǎn)：
再將grandparent的顏色改為紅色，parent改為黑色。
情況二：如果parent為grandparent的右孩子，cur為parent的右孩子，則進行左單旋轉(zhuǎn)：
再將grandparent的顏色改為紅色，parent改為黑色。
情況三：如果parent為grandparent的左孩子，cur為parent的右孩子，則先進行左單旋轉(zhuǎn)換成情況一，再進行右單旋：
再像情況一進行右單旋：
再將grandparent的顏色改為紅色，cur改為黑色。
情況四：如果parent為grandparent的右孩子，cur為parent的左孩子，則先進行右單旋轉(zhuǎn)換成情況二，再進行左單旋：
再像情況二進行左單旋：
再將grandparent的顏色改為紅色，cur改為黑色。
進行旋轉(zhuǎn)后，紅黑樹就滿足了性質(zhì)，插入成功。
如果uncle不存在：
這種情況和uncle存在且為黑是一樣的，所以可以并入上面一起考慮。
完整代碼如下：
bool Insert(const pair<K, V>& data)
{
//1.先找到插入位置
//如果是空樹
if (_pHead == nullptr)
{
Node* newnode = new Node(data);
newnode->_col = BLACK;
_pHead = newnode;
return true;
}
//如果不是空樹
Node* cur = _pHead;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > data.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < data.first)
{
parent = cur;
cur = cur->_right;
}
else
return false;//沒找到返回false
}
//2.找到，插入節(jié)點
Node* newnode = new Node(data);
//判斷插入父節(jié)點左側(cè)還是右側(cè)
if (parent->_kv.first > data.first)
parent->_left = newnode;
else
parent->_right = newnode;
//更新newnode父節(jié)點和顏色
newnode->_parent = parent;
if (parent->_col == BLACK)
{
//父節(jié)點是黑色,插入成功
return true;
}
if (parent->_col == RED)
{
//父節(jié)點是紅色
cur = newnode;
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;//parent是紅色，肯定不是根節(jié)點，所以grandparent不是空節(jié)點，而且是黑色
//找叔叔節(jié)點
Node* uncle = grandparent->_left;
if (parent == grandparent->_left)
uncle = grandparent->_right;
if (uncle&&uncle->_col == RED)
{
//如果uncle是紅色
//將unlcle和parent節(jié)點都變?yōu)楹谏?，grandparent節(jié)點變?yōu)榧t色
parent->_col = uncle->_col = BLACK;//即可保證所有路徑上黑色一樣多
grandparent->_col = RED;
//繼續(xù)往上更新
cur = grandparent;
parent = cur->_parent;
}
else if (uncle==nullptr||uncle->_col == BLACK)
{
//如果uncle不存在或者存在且為黑色
if (grandparent->_left == parent && parent->_left == cur)
{
//右單旋,再將grandparent改為紅色，parent改為黑色
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
else if (grandparent->_right == parent && parent->_right == cur)
{
//左單旋,再將grandparent改為紅色，parent改為黑色
RotateL(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
else if (grandparent->_right == parent && parent->_left == cur)
{
RotateR(parent);//先右單旋
RotateL(grandparent);//再左單旋
//再將grandparent的顏色改為紅色，cur改為黑色
grandparent->_col = RED;
cur->_col = BLACK;
}
else if (grandparent->_left == parent && parent->_right == cur)
{
RotateL(parent);//先左單旋
RotateR(grandparent);//后右單旋
//再將grandparent的顏色改為紅色，parent改為黑色
grandparent->_col = RED;
cur->_col = BLACK;
}
else
assert(false);
//插入成功，跳出循環(huán)
break;
}
}
}
_pHead->_col = BLACK;//最后不管怎樣，根節(jié)點都是黑色
return true;
}
因為涉及到多種情況，所以根節(jié)點的顏色可能會顧及不上，所以最后我們可以加一句_pHead->_col = BLACK;，這樣不管怎么樣，根節(jié)點都是黑色了。
左、右單旋函數(shù)與AVL樹的左、右單旋一樣：
// 左單旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
//將cur的左邊給parent的右邊，cur的左邊再指向parent
parent->_right = cur->_left;
cur->_left = parent;
//鏈接cur與parent的父節(jié)點
if (parent->_parent == nullptr)
{
//如果parent是根節(jié)點
cur->_parent = nullptr;
_pHead = cur;
}
else if (parent->_parent->_left == parent)
parent->_parent->_left = cur;
else
parent->_parent->_right = cur;
//更新父節(jié)點
cur->_parent = parent->_parent;
parent->_parent = cur;
if (parent->_right)//判斷parent的右邊是否存在
parent->_right->_parent = parent;
}
// 右單旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
//將cur的右邊給parent的左邊，cur的右邊再指向parent
parent->_left = cur->_right;
cur->_right = parent;
//鏈接cur與parent的父節(jié)點
if (parent->_parent == nullptr)
{
//如果parent是根節(jié)點
cur->_parent = nullptr;
_pHead = cur;
}
else if (parent->_parent->_left == parent)
parent->_parent->_left = cur;
else
parent->_parent->_right = cur;
//更新父節(jié)點
cur->_parent = parent->_parent;
parent->_parent = cur;
if (parent->_left)
parent->_left->_parent = parent;
}
紅黑樹的左、右單旋與AVL樹的區(qū)別在于不需要跟新平衡因子。
測試函數(shù)：
void RBTreeTest()
{
RBTree<int, int> t;
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
}
3.紅黑樹的驗證
紅黑樹的驗證和AVL樹一樣，分為兩個步驟：
檢測其是否滿足二叉搜索樹(中序遍歷是否為有序序列)檢測其是否滿足紅黑樹的性質(zhì)
對于第二點：
// 檢測紅黑樹是否為有效的紅黑樹
bool IsValidRBTRee()
{
if (_pHead == nullptr)
return true;
if (_pHead->_col == RED)
{
return false;
}
// 先求一條路徑上黑色節(jié)點數(shù)量作為參考值
int refNum = 0;
Node* cur = _pHead;
while (cur)
{
if (cur->_col == BLACK)
{
++refNum;
}
cur = cur->_left;
}
return Check(_pHead, 0, refNum);
}
首先如果一棵樹是空樹滿足紅黑樹的性質(zhì)，返回true；其次如果根節(jié)點為紅色則不滿足紅黑樹的性質(zhì)，返回false；然后再根據(jù)每條路徑上是否有相同的黑色節(jié)點已及是否存在連續(xù)的紅色節(jié)點來進一步判斷即Check()函數(shù)，但是我們需要先確定一條路上應(yīng)該有多少個黑色節(jié)點作為參考。
Check()函數(shù)如下：
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
//cout << blackNum << endl;
if (refNum != blackNum)
{
cout << "存在黑色節(jié)點的數(shù)量不相等的路徑" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在連續(xù)的紅色節(jié)點" << endl;
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);
}
因為Check()函數(shù)使用的是遞歸來計算每條路徑上黑色節(jié)點的數(shù)量，所以當root為空時我們就可以將計算該條路徑上的黑色節(jié)點數(shù)量blackNum與參考值refNum進行比較，如果相等返回true，不相等就返回fals；此外如果在計算黑色節(jié)點過程中存在連續(xù)的紅色節(jié)點也直接返回false即可。
測試函數(shù)：
void RBTreeTest()
{
RBTree<int, int> t;
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
cout << t.IsValidRBTRee() << endl;
}
4.中序遍歷
與二叉搜索樹一樣，可以使用遞歸進行中序遍歷，并且遍歷結(jié)果是有序的，代碼如下：
//中序遍歷
void InOrder()
{
_InOrder(_pHead);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
結(jié)果如下：
5.結(jié)語
因為紅黑樹也是二叉搜索樹，其他的類似查找節(jié)點，析構(gòu)函數(shù)和構(gòu)造函數(shù)都與二叉搜索樹類似，對于刪除節(jié)點，可按照二叉搜索樹的方式將節(jié)點刪除，然后再進行調(diào)整，大家有興趣可以自己查找了解一下
以上就是C++紅黑樹的底層實現(xiàn)機制詳解的詳細內(nèi)容，更多關(guān)于C++紅黑樹底層實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語言數(shù)據(jù)的存儲超詳細講解下篇浮點型在內(nèi)存中的存取
使用編程語言進行編程時，需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著，當您創(chuàng)建一個變量時，就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息，操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2022-04-04
這篇文章主要介紹了C語言中設(shè)置進程優(yōu)先順序的方法,包括setpriority()函數(shù)和getpriority()函數(shù)以及nice()函數(shù),需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細介紹了C++實現(xiàn)連連看消除算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了C語言異常處理機制案例講解,本文講解了異常處理機制所用的函數(shù)和具體的代碼實現(xiàn)等,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要給大家介紹了關(guān)于C++11模板元編程-std::enable_if的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10
這篇文章主要為大家詳細介紹了C++使用文件實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
對C++ 了解的人都應(yīng)該知道虛函數(shù)（Virtual Function）是通過一張?zhí)摵瘮?shù)表（Virtual Table）和一個指向虛函數(shù)表的指針（vptr）來實現(xiàn)的2013-09-09
這篇文章主要介紹了C++計算中國農(nóng)歷的深入淺析，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-05-05
使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu)
這篇文章主要介紹了使用C語言使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu),包括根據(jù)前序序列和中序序列構(gòu)建二叉樹的方法,需要的朋友可以參考下2015-08-08