C++超詳細(xì)分析紅黑樹(shù)
紅黑樹(shù)
紅黑樹(shù)的概念
紅黑樹(shù)的概念 紅黑樹(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)出倆倍,因而是接近平衡的。
紅黑樹(shù)和AVL樹(shù)都是高效的平衡二叉樹(shù),增刪改查的時(shí)間復(fù)雜度都是O(),紅黑樹(shù)不追求絕對(duì)平衡,其只需保證最長(zhǎng)路徑不超過(guò)最短路徑的2倍,相對(duì)而言,降低了插入和旋轉(zhuǎn)的次數(shù),所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹(shù)更優(yōu),而且紅黑樹(shù)實(shí)現(xiàn)比較簡(jiǎn)單,所以實(shí)際運(yùn)用中紅黑樹(shù)更多。
紅黑樹(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)
- 每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處的葉子節(jié)點(diǎn)指的是空結(jié)點(diǎn),如上圖路徑數(shù)為11條)
紅黑樹(shù)結(jié)點(diǎn)的定義
enum Color { BLACK, RED }; template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Color _col; T _data; RBTreeNode(const T& data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) ,_data(data) {} };
紅黑樹(shù)的插入操作
約定:cur為當(dāng)前節(jié)點(diǎn),p為父節(jié)點(diǎn),g為祖父節(jié)點(diǎn),u為叔叔節(jié)點(diǎn)
情況一
- 情況一:cur為紅,p為紅,g為黑,u存在且為紅注意:此處看到的樹(shù),可能是一棵完整的樹(shù),也可能是一棵子樹(shù)
- 解決方式:將p,u改為黑,g改為紅,然后把g當(dāng)成cur,繼續(xù)向上調(diào)整
如果g是根節(jié)點(diǎn),調(diào)整完成后,需要將g改為黑色
如果g是子樹(shù),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)的顏色是黑色,就不滿(mǎn)足性質(zhì)4:每條路徑黑色節(jié)點(diǎn)個(gè)數(shù)相同。
2.如果u節(jié)點(diǎn)存在,則其一定是黑色的,cur一定不是新增節(jié)點(diǎn),那么cur節(jié)點(diǎn)原來(lái)的顏色一定是黑色的,是作為子樹(shù)的祖父,由第一種情況變化過(guò)來(lái)的
情況三
情況三:cur為紅,p為紅,g為黑,u不存在/u為黑(折線(xiàn)型)
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->K set // T->pair<const K, V> map template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef RBTreeIterator<T, T&, T*> iterator; typedef RBTreeIterator<T, const T&, const T*> const_iterator; iterator begin(); iterator end(); RBTree() :_root(nullptr) {} // 拷貝構(gòu)造和賦值重載 // 析構(gòu) Node* Find(const K& key); pair<iterator, bool> Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } Node* parent = nullptr; Node* cur = _root; KeyOfT kot; while (cur) { if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else { return make_pair(iterator(cur), false); } } // 新增節(jié)點(diǎn),顏色是紅色,可能破壞規(guī)則3,產(chǎn)生連續(xù)紅色節(jié)點(diǎn) cur = new Node(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 (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; // 情況一:uncle存在且為紅,進(jìn)行變色處理,并繼續(xù)往上更新處理 if (uncle && uncle->_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 (uncle && uncle->_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; return make_pair(iterator(newnode), true); } void RotateR(Node* parent); void RotateL(Node* parent); private: Node* _root; };
紅黑樹(shù)的驗(yàn)證
紅黑樹(shù)的檢測(cè)分為兩步:
- 檢測(cè)其是否滿(mǎn)足二叉搜索樹(shù)(中序遍歷是否為有序序列)
- 檢測(cè)其是否滿(mǎn)足紅黑樹(shù)的性質(zhì)
此處用未改造過(guò)的紅黑樹(shù)
template<class K, class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; pair<K, V> _kv; RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) , _kv(kv) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: RBTree() :_root(nullptr) {} bool Insert(const pair<K, V>& kv); void RotateR(Node* parent); void RotateL(Node* parent); void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } void InOrder() { _InOrder(_root); cout<<endl; } bool CheckRED_RED(Node* cur) { if (cur == nullptr) { return true; } if (cur->_col == RED && cur->_parent->_col == RED) { cout << "違反規(guī)則三,存在連續(xù)的紅色節(jié)點(diǎn)" << endl; return false; } return CheckRED_RED(cur->_left) && CheckRED_RED(cur->_right); } // 檢查每條路徑黑色節(jié)點(diǎn)的數(shù)量 bool CheckBlackNum(Node* cur, int blackNum, int benchmark) { if (cur == nullptr) { if (blackNum != benchmark){ cout << "違反規(guī)則四:黑色節(jié)點(diǎn)的數(shù)量不相等" << endl; return false;} return true; } if (cur->_col == BLACK) ++blackNum; return CheckBlackNum(cur->_left, blackNum, benchmark) && CheckBlackNum(cur->_right, blackNum, benchmark); } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) { cout << "根節(jié)點(diǎn)是紅色,違反規(guī)則二" << endl; return false; } // 算出最左路徑的黑色節(jié)點(diǎn)的數(shù)量作為基準(zhǔn)值 int benchmark = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++benchmark; } cur = cur->_left; } int blackNum = 0; return CheckRED_RED(_root) && CheckBlackNum(_root, blackNum, benchmark); } private: Node* _root; }; void TestRBTree1() { const int n = 1000000; vector<int> a; a.reserve(n); srand(time(0)); for (size_t i = 0; i < n; ++i) { a.push_back(rand()); } RBTree<int, int> t1; for (auto e : a) { t1.Insert(make_pair(e, e)); } cout << t1.IsBalance() << endl; //t1.InOrder(); }
用紅黑樹(shù)封裝map、set
紅黑樹(shù)的迭代器
begin()與end()
begin()可以放在紅黑樹(shù)中最小節(jié)點(diǎn)(即最左側(cè)節(jié)點(diǎn))的位置
end()放在最大節(jié)點(diǎn)(最右側(cè)節(jié)點(diǎn))的下一個(gè)位置
typedef RBTreeIterator<T, T&, T*> iterator; typedef RBTreeIterator<T, const T&, const T*> const_iterator; iterator begin() { Node* left = _root; while (left && left->_left) { left = left->_left; } //return left return iterator(left); } iterator end() { return iterator(nullptr); }
操作符重載
template<class T, class Ref, class Ptr> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node; RBTreeIterator(Node* node = nullptr) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator--() { // 跟++基本是反過(guò)來(lái) return *this; } Self& operator++() { if (_node->_right) { // 右子樹(shù)中序第一個(gè)節(jié)點(diǎn),也就是右子樹(shù)的最左節(jié)點(diǎn) Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else { // 當(dāng)前子樹(shù)已經(jīng)訪(fǎng)問(wèn)完了,要去找祖先訪(fǎng)問(wèn),沿著到根節(jié)點(diǎn)的路徑往上走, // 找孩子是父親左的那個(gè)父親節(jié)點(diǎn) Node* cur = _node; Node* parent = cur->_parent; while (parent && parent->_right == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } };
封裝map
#pragma once #include "RBTree.h" namespace MyMap { template < class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } pair<iterator, bool> insert(const pair<const K, V>& kv) { return _t.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); return ret.first->second; } private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; void test_map() { map<string, string> dict; dict.insert(make_pair("sort", "排序")); dict.insert(make_pair("string", "字符串")); dict.insert(make_pair("debug", "找蟲(chóng)子")); dict.insert(make_pair("set", "集合")); map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; } }
封裝set
#pragma once #include "RBTree.h" namespace MySet { template < class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } private: RBTree<K, K, SetKeyOfT> _t; }; void test_set() { set<int> s; s.insert(1); s.insert(3); s.insert(7); s.insert(2); s.insert(12); s.insert(22); s.insert(2); s.insert(23); s.insert(-2); s.insert(-9); s.insert(30); set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; for (auto e : s) { cout << e << " "; } cout << endl; } }
到此這篇關(guān)于C++超詳細(xì)分析紅黑樹(shù)的文章就介紹到這了,更多相關(guān)C++ 紅黑樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++詳細(xì)實(shí)現(xiàn)紅黑樹(shù)流程詳解
- C++實(shí)現(xiàn)紅黑樹(shù)應(yīng)用實(shí)例代碼
- C++?STL容器詳解之紅黑樹(shù)部分模擬實(shí)現(xiàn)
- C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)的實(shí)現(xiàn)
- C++數(shù)據(jù)結(jié)構(gòu)紅黑樹(shù)全面分析
- C++?RBTree紅黑樹(shù)的性質(zhì)與實(shí)現(xiàn)
- C++使用一棵紅黑樹(shù)同時(shí)封裝出map和set實(shí)例代碼
- C++紅黑樹(shù)應(yīng)用之手搓set和map
- C++實(shí)現(xiàn)紅黑樹(shù)核心插入實(shí)例代碼
相關(guān)文章
C語(yǔ)言中隨機(jī)數(shù)rand()函數(shù)詳解
大家好,本篇文章主要講的是C語(yǔ)言中隨機(jī)數(shù)rand()函數(shù)詳解,感興趣的同學(xué)感快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下2022-02-02VC++中HTControl控件類(lèi)之CHTRichEdit富文本編輯控件實(shí)例
這篇文章主要介紹了VC++中HTControl控件類(lèi)之CHTRichEdit富文本編輯控件,是一個(gè)比較實(shí)用的功能,需要的朋友可以參考下2014-08-08C語(yǔ)言計(jì)算代碼執(zhí)行所耗CPU時(shí)鐘周期
本文給大家介紹的是使用C語(yǔ)言來(lái)計(jì)算代碼執(zhí)行所耗CPU時(shí)鐘周期的代碼,非常的簡(jiǎn)單實(shí)用,不過(guò)要依托于sync,有需要的小伙伴自己參考下吧。2015-03-03C++:構(gòu)造函數(shù),析構(gòu)函數(shù)詳解
今天小編就為大家分享一篇關(guān)于C++構(gòu)造函數(shù)和析構(gòu)函數(shù)的文章,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2021-09-09C++中類(lèi)的構(gòu)造函數(shù)初始值列表解讀
這篇文章主要介紹了C++中類(lèi)的構(gòu)造函數(shù)初始值列表,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-11-11C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán)
這篇文章主要為大家詳細(xì)介紹了C++基于棧的深搜算法實(shí)現(xiàn)馬踏棋盤(pán),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-02-02C語(yǔ)言實(shí)現(xiàn)數(shù)字連連看
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)數(shù)字連連看游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-09-09用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷游戲
這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-07-07