C++紅黑樹的底層實現(xiàn)機(jī)制詳解
前言
紅黑樹與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ì)是否造到破壞,如果破壞進(jìn)行相應(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)整:
因為不可能有兩個紅色連在一起,所以我們需要進(jìn)行調(diào)整;而且父節(jié)點是紅色的話那么父節(jié)點肯定不是根節(jié)點且其父節(jié)點的顏色也只能是黑色,如下圖所示:
這時,我們就需要根據(jù)叔叔節(jié)點來進(jìn)行調(diào)整節(jié)點:
如果uncle節(jié)點是紅色:
我們就可以將unlcle和parent節(jié)點都變?yōu)楹谏琯randparent節(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ì),我們需要進(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)后,紅黑樹就滿足了性質(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é)點來進(jìn)一步判斷即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ù)量,所以當(dāng)root為空時我們就可以將計算該條路徑上的黑色節(jié)點數(shù)量blackNum與參考值refNum進(jìn)行比較,如果相等返回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.中序遍歷
與二叉搜索樹一樣,可以使用遞歸進(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é)語
因為紅黑樹也是二叉搜索樹,其他的類似查找節(jié)點,析構(gòu)函數(shù)和構(gòu)造函數(shù)都與二叉搜索樹類似,對于刪除節(jié)點,可按照二叉搜索樹的方式將節(jié)點刪除,然后再進(jìn)行調(diào)整,大家有興趣可以自己查找了解一下
以上就是C++紅黑樹的底層實現(xiàn)機(jī)制詳解的詳細(xì)內(nèi)容,更多關(guān)于C++紅黑樹底層實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C語言數(shù)據(jù)的存儲超詳細(xì)講解下篇浮點型在內(nèi)存中的存取
使用編程語言進(jìn)行編程時,需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著,當(dāng)您創(chuàng)建一個變量時,就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息,操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型,來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2022-04-04C語言中設(shè)置進(jìn)程優(yōu)先順序的方法
這篇文章主要介紹了C語言中設(shè)置進(jìn)程優(yōu)先順序的方法,包括setpriority()函數(shù)和getpriority()函數(shù)以及nice()函數(shù),需要的朋友可以參考下2015-08-08C++使用文件實現(xiàn)學(xué)生信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++使用文件實現(xiàn)學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-01-01C語言實現(xiàn)簡單學(xué)生信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)簡單學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-07-07使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu)
這篇文章主要介紹了使用C語言使用C語言構(gòu)建基本的二叉樹數(shù)據(jù)結(jié)構(gòu),包括根據(jù)前序序列和中序序列構(gòu)建二叉樹的方法,需要的朋友可以參考下2015-08-08