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