現(xiàn))
1.關(guān)聯(lián)式容器之前接觸的STL中的部分容器比如vectorlistdequeforward_list(C11)等這些統(tǒng)稱為序列式容器因?yàn)槠涞讓訛榫€性序列的數(shù)據(jù)結(jié)構(gòu)里面存儲(chǔ)的是元素本身。關(guān)聯(lián)式容器也是用來(lái)存儲(chǔ)數(shù)據(jù)的與序列式容器不同的是其里面存儲(chǔ)的是keyvalue結(jié)構(gòu)的鍵值對(duì)在數(shù)據(jù)檢索時(shí)比序列式容器效率更高。2.鍵值對(duì)用來(lái)表示具有一一對(duì)應(yīng)關(guān)系的一種結(jié)構(gòu)該結(jié)構(gòu)中一般只包含兩個(gè)成員變量key和valuekey代表鍵值value表示與key對(duì)應(yīng)的信息。3.樹(shù)形結(jié)構(gòu)的關(guān)聯(lián)式容器STL總共實(shí)現(xiàn)了兩種不同的關(guān)聯(lián)式容器樹(shù)形結(jié)構(gòu)與哈希結(jié)構(gòu)。樹(shù)形結(jié)構(gòu)的關(guān)聯(lián)式容器主要有四種mapsetmultimapmultiset。這四種容器的共同點(diǎn)是使用平衡搜索樹(shù)(即紅黑樹(shù))作為其底層結(jié)果容器中的元素是一個(gè)有序的列。3.1 setset 中只存放 value 值且每個(gè) value 必須唯一。set 中元素不能修改(元素是const)只可以插入刪除。插入元素時(shí)只需要插入 value不需要構(gòu)造鍵值對(duì)。set 中元素不可以重復(fù)可以使用它進(jìn)行去重按小于來(lái)比較遍歷即可得到有序序列。3.2 mapmap 是關(guān)聯(lián)式容器它按照特定的次序(按照key來(lái)比較)存儲(chǔ)由鍵值key和值value組合而成的元素。在元素訪問(wèn)時(shí)與operator[]類似的操作at()(該函數(shù)不常用)函數(shù)都是通過(guò)key找到與key對(duì)應(yīng)的value然后返回其引用不同的是當(dāng)key不存在時(shí)operator[]用默認(rèn)value與key構(gòu)造鍵值對(duì)然后插入返回該默認(rèn)valueat()函數(shù)直接拋異常。3.3 multiset multiset是按照特定順序的容器其中元素可以重復(fù)的。在 multiset 中元素的value也會(huì)識(shí)別它(因?yàn)?multiset 中本身存儲(chǔ)的就是value, value組成的鍵值對(duì)因此 value 本身就是 keykey 就是 value類型為 T)multiset 元素的值不能在容器中修改(因?yàn)樵乜偸?const)可以插入刪除。set 與 multiset 的接口相同不作展示唯一區(qū)別就是可存儲(chǔ)重復(fù)元素。3.4 multimap同上 multimap 和 map 的唯一不同是map 中 key 值唯一multimap 中 key 是可以重復(fù)的。4.底層結(jié)構(gòu)map/multimap/set/multiset 其底層結(jié)構(gòu)都是二叉搜索樹(shù)實(shí)現(xiàn)的但是二叉搜索樹(shù)有其缺陷假如往樹(shù)中插入的元素有序便會(huì)退化為單支樹(shù)時(shí)間復(fù)雜度便會(huì)退化為O(N)因此對(duì)其進(jìn)行了平衡處理即二叉平衡樹(shù)(AVL)。4.1 AVL樹(shù)一棵AVL樹(shù)或者是空樹(shù)或者是左右都是AVL樹(shù)、左右子樹(shù)高度差(簡(jiǎn)稱平衡因子)的絕對(duì)值不超過(guò)1(-1/0/1)的二叉搜索樹(shù)。AVL樹(shù)的旋轉(zhuǎn)1新結(jié)點(diǎn)插入較高左子樹(shù)的左側(cè)——左左右單旋2新結(jié)點(diǎn)插入較高右子樹(shù)的右側(cè)——右右左單旋3新結(jié)點(diǎn)插入較高左子樹(shù)右側(cè)——左右先左單旋在右單旋(先旋轉(zhuǎn)再考慮平衡因子更新)4新結(jié)點(diǎn)插入較高右子樹(shù)左側(cè)——右左先右單旋再左單旋AVL樹(shù)實(shí)現(xiàn)#pragma once #include iostream #include assert.h using namespace std; templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _pleft; AVLTreeNodeK, V* _pright; AVLTreeNodeK, V* _parent; int _bf;//平衡因子 AVLTreeNode(const pairK, V kv) :_kv(kv) ,_pleft(nullptr) ,_pright(nullptr) ,_parent(nullptr) ,_bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* parent _root; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_pright; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_pleft; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_pleft cur; } else { parent-_pright cur; } cur-_parent parent; //控制平衡 //1.新增在左parent平衡因子減減 //2.新增在右parent平衡因子加加 //3.更新后parent平衡因子 0說(shuō)明parent所在子樹(shù)高度不變不會(huì)影響祖先 //4.更新后parent平衡因子 -1 or 1說(shuō)明parent所在子樹(shù)高度變化會(huì)影響祖先需繼續(xù)沿著到root的路徑往上更新 //5.更新后parent平衡因子 -2 or 2說(shuō)明parent所在子樹(shù)高度變化且不平衡對(duì)parent所在子樹(shù)進(jìn)行旋轉(zhuǎn)讓它平衡 //更新平衡因子 while (parent)//更新到根節(jié)點(diǎn)結(jié)束 { if (cur parent-_pleft) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break;//結(jié)束 } else if (parent-_bf -1 || parent-_bf 1) { //繼續(xù)往上更新 cur parent; parent parent-_parent; } else if (parent-_bf -2 || parent-_bf 2) { //子樹(shù)不平衡了需要旋轉(zhuǎn) if (parent-_bf 2 cur-_bf 1)//左單旋 { RotateL(parent); } else if (parent-_bf -2 cur-_bf -1) { RotateR(parent); } else if (parent-_bf 2 cur-_bf -1) { RotateRL(parent); } else if (parent-_bf -2 cur-_bf 1) { RotateLR(parent); } break; } else { assert(false); } } return true; } void RotateL(Node* parent) { Node* cur parent-_pright; Node* curleft cur-_pleft; Node* pparent parent-_parent; parent-_pright curleft; if (curleft) { curleft-_parent parent; } cur-_pleft parent; parent-_parent cur; if (parent _root) { _root cur; cur-_parent nullptr; } else { if (pparent-_pleft parent) { pparent-_pleft cur; } else { pparent-_pright cur; } cur-_parent pparent; } parent-_bf cur-_bf 0; } void RotateR(Node* parent) { Node* cur parent-_pleft; Node* curright cur-_pright; Node* pparent parent-_parent; parent-_pleft curright; if (curright) { curright-_parent parent; } cur-_pright parent; parent-_parent cur; if (parent _root) { cur-_parent nullptr; _root cur; } else { if (pparent-_pleft parent) { pparent-_pleft cur; } else { pparent-_pright cur; } cur-_parent pparent; } parent-_bf cur-_bf 0; } void RotateRL(Node* parent) { Node* cur parent-_pright; Node* curleft cur-_pleft; int bf curleft-_bf; RotateR(cur); RotateL(parent); //右左雙旋本質(zhì)是 孫子結(jié)點(diǎn)左子樹(shù)給祖父結(jié)點(diǎn)做右子樹(shù)右子樹(shù)給父節(jié)點(diǎn)做左子樹(shù)自己變?yōu)楦?jié)點(diǎn) if (bf 0) { parent-_bf 0; cur-_bf 0; curleft-_bf 0; } else if (bf -1) { parent-_bf 0; cur-_bf 1; curleft-_bf 0; } else if (bf 1) { parent-_bf -1; cur-_bf 0; curleft-_bf 0; } else { assert(false); } } void RotateLR(Node* parent) { Node* cur parent-_pleft; Node* curright cur-_pright; int bf curright-_bf; RotateL(cur); RotateR(parent); //左右雙旋是 孫子節(jié)點(diǎn)左子樹(shù)給父節(jié)點(diǎn)做右子樹(shù)右子樹(shù)給祖父節(jié)點(diǎn)做左子樹(shù)自己變成根節(jié)點(diǎn) if (bf 0) { parent-_bf 0; cur-_bf 0; curright-_bf 0; } else if (bf -1) { parent-_bf 1; cur-_bf 0; curright-_bf 0; } else if (bf 1) { parent-_bf 0; cur-_bf -1; curright-_bf 0; } } bool IsBalance() { return _IsBalance(_root); } bool _IsBalance(Node* root) { if (root nullptr) return true; int leftHight Height(root-_pleft); int rightHight Height(root-_pright); return abs(rightHight - leftHight) 2 _IsBalance(root-_pleft) _IsBalance(root-_pright); } int Height(Node* root) { if (root nullptr) { return 0; } int leftHight Height(root-_pleft); int rightHight Height(root-_pright); if (rightHight - leftHight ! root-_bf) { cout 平衡因子異常 root-_kv.first - root-_bf endl; return false; } return leftHight rightHight ? leftHight 1 : rightHight 1; } private: Node* _root nullptr; };4.2紅黑樹(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)出兩倍因?yàn)槭墙咏胶獾?。紅黑樹(shù)的性質(zhì)1每個(gè)結(jié)點(diǎn)不是黑色就是紅色2根結(jié)點(diǎn)是黑色3如果一個(gè)結(jié)點(diǎn)是紅色的則它兩個(gè)孩子都是黑色的4對(duì)于每個(gè)結(jié)點(diǎn)從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑均包含相同數(shù)目的黑色結(jié)點(diǎn)5每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處葉子節(jié)點(diǎn)指的空結(jié)點(diǎn))紅黑樹(shù)的插入操作1按照二叉搜素樹(shù)規(guī)則插入新結(jié)點(diǎn)2檢測(cè)新結(jié)點(diǎn)插入后紅黑樹(shù)的性質(zhì)是否遭到破壞因?yàn)樾陆Y(jié)點(diǎn)的默認(rèn)顏色是紅色因此如果其雙親結(jié)點(diǎn)的顏色是黑色沒(méi)有違反紅黑樹(shù)任何性質(zhì)則不需要調(diào)整但當(dāng)新插入結(jié)點(diǎn)的雙親結(jié)點(diǎn)顏色為紅色時(shí)就違反了性質(zhì)三不能有連續(xù)紅色結(jié)點(diǎn)需分情況討論。(cur 為當(dāng)前結(jié)點(diǎn)p為父結(jié)點(diǎn)g為祖父結(jié)點(diǎn)u為叔叔結(jié)點(diǎn))1cur 為紅p 為紅g 為黑u 存在且為紅解決方式將p、u 改為黑g 改為紅然后把 g 當(dāng)成 cur繼續(xù)向上調(diào)整。2cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的左孩子則進(jìn)行右單旋轉(zhuǎn)相反p 為 g 的右孩子cur 為 p 的右孩子則進(jìn)行左單旋最后 p、g 變色——p 變黑g 變紅。3cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的右孩子則針對(duì) p 做左單旋轉(zhuǎn)相反p 為g 的右孩子cur 為 p 的左孩子則針對(duì) p 做右單旋轉(zhuǎn)最后則轉(zhuǎn)換成了情況2(雙旋)。紅黑樹(shù)模擬實(shí)現(xiàn) STL 中的 map 與 set(暫略) map 和 set 使用及模擬實(shí)現(xiàn)
1.關(guān)聯(lián)式容器之前接觸的STL中的部分容器比如vectorlistdequeforward_list(C11)等這些統(tǒng)稱為序列式容器因?yàn)槠涞讓訛榫€性序列的數(shù)據(jù)結(jié)構(gòu)里面存儲(chǔ)的是元素本身。關(guān)聯(lián)式容器也是用來(lái)存儲(chǔ)數(shù)據(jù)的與序列式容器不同的是其里面存儲(chǔ)的是keyvalue結(jié)構(gòu)的鍵值對(duì)在數(shù)據(jù)檢索時(shí)比序列式容器效率更高。2.鍵值對(duì)用來(lái)表示具有一一對(duì)應(yīng)關(guān)系的一種結(jié)構(gòu)該結(jié)構(gòu)中一般只包含兩個(gè)成員變量key和valuekey代表鍵值value表示與key對(duì)應(yīng)的信息。3.樹(shù)形結(jié)構(gòu)的關(guān)聯(lián)式容器STL總共實(shí)現(xiàn)了兩種不同的關(guān)聯(lián)式容器樹(shù)形結(jié)構(gòu)與哈希結(jié)構(gòu)。樹(shù)形結(jié)構(gòu)的關(guān)聯(lián)式容器主要有四種mapsetmultimapmultiset。這四種容器的共同點(diǎn)是使用平衡搜索樹(shù)(即紅黑樹(shù))作為其底層結(jié)果容器中的元素是一個(gè)有序的列。3.1 setset 中只存放 value 值且每個(gè) value 必須唯一。set 中元素不能修改(元素是const)只可以插入刪除。插入元素時(shí)只需要插入 value不需要構(gòu)造鍵值對(duì)。set 中元素不可以重復(fù)可以使用它進(jìn)行去重按小于來(lái)比較遍歷即可得到有序序列。3.2 mapmap 是關(guān)聯(lián)式容器它按照特定的次序(按照key來(lái)比較)存儲(chǔ)由鍵值key和值value組合而成的元素。在元素訪問(wèn)時(shí)與operator[]類似的操作at()(該函數(shù)不常用)函數(shù)都是通過(guò)key找到與key對(duì)應(yīng)的value然后返回其引用不同的是當(dāng)key不存在時(shí)operator[]用默認(rèn)value與key構(gòu)造鍵值對(duì)然后插入返回該默認(rèn)valueat()函數(shù)直接拋異常。3.3 multiset multiset是按照特定順序的容器其中元素可以重復(fù)的。在 multiset 中元素的value也會(huì)識(shí)別它(因?yàn)?multiset 中本身存儲(chǔ)的就是value, value組成的鍵值對(duì)因此 value 本身就是 keykey 就是 value類型為 T)multiset 元素的值不能在容器中修改(因?yàn)樵乜偸?const)可以插入刪除。set 與 multiset 的接口相同不作展示唯一區(qū)別就是可存儲(chǔ)重復(fù)元素。3.4 multimap同上 multimap 和 map 的唯一不同是map 中 key 值唯一multimap 中 key 是可以重復(fù)的。4.底層結(jié)構(gòu)map/multimap/set/multiset 其底層結(jié)構(gòu)都是二叉搜索樹(shù)實(shí)現(xiàn)的但是二叉搜索樹(shù)有其缺陷假如往樹(shù)中插入的元素有序便會(huì)退化為單支樹(shù)時(shí)間復(fù)雜度便會(huì)退化為O(N)因此對(duì)其進(jìn)行了平衡處理即二叉平衡樹(shù)(AVL)。4.1 AVL樹(shù)一棵AVL樹(shù)或者是空樹(shù)或者是左右都是AVL樹(shù)、左右子樹(shù)高度差(簡(jiǎn)稱平衡因子)的絕對(duì)值不超過(guò)1(-1/0/1)的二叉搜索樹(shù)。AVL樹(shù)的旋轉(zhuǎn)1新結(jié)點(diǎn)插入較高左子樹(shù)的左側(cè)——左左右單旋2新結(jié)點(diǎn)插入較高右子樹(shù)的右側(cè)——右右左單旋3新結(jié)點(diǎn)插入較高左子樹(shù)右側(cè)——左右先左單旋在右單旋(先旋轉(zhuǎn)再考慮平衡因子更新)4新結(jié)點(diǎn)插入較高右子樹(shù)左側(cè)——右左先右單旋再左單旋AVL樹(shù)實(shí)現(xiàn)#pragma once #include iostream #include assert.h using namespace std; templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _pleft; AVLTreeNodeK, V* _pright; AVLTreeNodeK, V* _parent; int _bf;//平衡因子 AVLTreeNode(const pairK, V kv) :_kv(kv) ,_pleft(nullptr) ,_pright(nullptr) ,_parent(nullptr) ,_bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* parent _root; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_pright; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_pleft; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_pleft cur; } else { parent-_pright cur; } cur-_parent parent; //控制平衡 //1.新增在左parent平衡因子減減 //2.新增在右parent平衡因子加加 //3.更新后parent平衡因子 0說(shuō)明parent所在子樹(shù)高度不變不會(huì)影響祖先 //4.更新后parent平衡因子 -1 or 1說(shuō)明parent所在子樹(shù)高度變化會(huì)影響祖先需繼續(xù)沿著到root的路徑往上更新 //5.更新后parent平衡因子 -2 or 2說(shuō)明parent所在子樹(shù)高度變化且不平衡對(duì)parent所在子樹(shù)進(jìn)行旋轉(zhuǎn)讓它平衡 //更新平衡因子 while (parent)//更新到根節(jié)點(diǎn)結(jié)束 { if (cur parent-_pleft) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break;//結(jié)束 } else if (parent-_bf -1 || parent-_bf 1) { //繼續(xù)往上更新 cur parent; parent parent-_parent; } else if (parent-_bf -2 || parent-_bf 2) { //子樹(shù)不平衡了需要旋轉(zhuǎn) if (parent-_bf 2 cur-_bf 1)//左單旋 { RotateL(parent); } else if (parent-_bf -2 cur-_bf -1) { RotateR(parent); } else if (parent-_bf 2 cur-_bf -1) { RotateRL(parent); } else if (parent-_bf -2 cur-_bf 1) { RotateLR(parent); } break; } else { assert(false); } } return true; } void RotateL(Node* parent) { Node* cur parent-_pright; Node* curleft cur-_pleft; Node* pparent parent-_parent; parent-_pright curleft; if (curleft) { curleft-_parent parent; } cur-_pleft parent; parent-_parent cur; if (parent _root) { _root cur; cur-_parent nullptr; } else { if (pparent-_pleft parent) { pparent-_pleft cur; } else { pparent-_pright cur; } cur-_parent pparent; } parent-_bf cur-_bf 0; } void RotateR(Node* parent) { Node* cur parent-_pleft; Node* curright cur-_pright; Node* pparent parent-_parent; parent-_pleft curright; if (curright) { curright-_parent parent; } cur-_pright parent; parent-_parent cur; if (parent _root) { cur-_parent nullptr; _root cur; } else { if (pparent-_pleft parent) { pparent-_pleft cur; } else { pparent-_pright cur; } cur-_parent pparent; } parent-_bf cur-_bf 0; } void RotateRL(Node* parent) { Node* cur parent-_pright; Node* curleft cur-_pleft; int bf curleft-_bf; RotateR(cur); RotateL(parent); //右左雙旋本質(zhì)是 孫子結(jié)點(diǎn)左子樹(shù)給祖父結(jié)點(diǎn)做右子樹(shù)右子樹(shù)給父節(jié)點(diǎn)做左子樹(shù)自己變?yōu)楦?jié)點(diǎn) if (bf 0) { parent-_bf 0; cur-_bf 0; curleft-_bf 0; } else if (bf -1) { parent-_bf 0; cur-_bf 1; curleft-_bf 0; } else if (bf 1) { parent-_bf -1; cur-_bf 0; curleft-_bf 0; } else { assert(false); } } void RotateLR(Node* parent) { Node* cur parent-_pleft; Node* curright cur-_pright; int bf curright-_bf; RotateL(cur); RotateR(parent); //左右雙旋是 孫子節(jié)點(diǎn)左子樹(shù)給父節(jié)點(diǎn)做右子樹(shù)右子樹(shù)給祖父節(jié)點(diǎn)做左子樹(shù)自己變成根節(jié)點(diǎn) if (bf 0) { parent-_bf 0; cur-_bf 0; curright-_bf 0; } else if (bf -1) { parent-_bf 1; cur-_bf 0; curright-_bf 0; } else if (bf 1) { parent-_bf 0; cur-_bf -1; curright-_bf 0; } } bool IsBalance() { return _IsBalance(_root); } bool _IsBalance(Node* root) { if (root nullptr) return true; int leftHight Height(root-_pleft); int rightHight Height(root-_pright); return abs(rightHight - leftHight) 2 _IsBalance(root-_pleft) _IsBalance(root-_pright); } int Height(Node* root) { if (root nullptr) { return 0; } int leftHight Height(root-_pleft); int rightHight Height(root-_pright); if (rightHight - leftHight ! root-_bf) { cout 平衡因子異常 root-_kv.first - root-_bf endl; return false; } return leftHight rightHight ? leftHight 1 : rightHight 1; } private: Node* _root nullptr; };4.2紅黑樹(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)出兩倍因?yàn)槭墙咏胶獾?。紅黑樹(shù)的性質(zhì)1每個(gè)結(jié)點(diǎn)不是黑色就是紅色2根結(jié)點(diǎn)是黑色3如果一個(gè)結(jié)點(diǎn)是紅色的則它兩個(gè)孩子都是黑色的4對(duì)于每個(gè)結(jié)點(diǎn)從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑均包含相同數(shù)目的黑色結(jié)點(diǎn)5每個(gè)葉子結(jié)點(diǎn)都是黑色的(此處葉子節(jié)點(diǎn)指的空結(jié)點(diǎn))紅黑樹(shù)的插入操作1按照二叉搜素樹(shù)規(guī)則插入新結(jié)點(diǎn)2檢測(cè)新結(jié)點(diǎn)插入后紅黑樹(shù)的性質(zhì)是否遭到破壞因?yàn)樾陆Y(jié)點(diǎn)的默認(rèn)顏色是紅色因此如果其雙親結(jié)點(diǎn)的顏色是黑色沒(méi)有違反紅黑樹(shù)任何性質(zhì)則不需要調(diào)整但當(dāng)新插入結(jié)點(diǎn)的雙親結(jié)點(diǎn)顏色為紅色時(shí)就違反了性質(zhì)三不能有連續(xù)紅色結(jié)點(diǎn)需分情況討論。(cur 為當(dāng)前結(jié)點(diǎn)p為父結(jié)點(diǎn)g為祖父結(jié)點(diǎn)u為叔叔結(jié)點(diǎn))1cur 為紅p 為紅g 為黑u 存在且為紅解決方式將p、u 改為黑g 改為紅然后把 g 當(dāng)成 cur繼續(xù)向上調(diào)整。2cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的左孩子則進(jìn)行右單旋轉(zhuǎn)相反p 為 g 的右孩子cur 為 p 的右孩子則進(jìn)行左單旋最后 p、g 變色——p 變黑g 變紅。3cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的右孩子則針對(duì) p 做左單旋轉(zhuǎn)相反p 為g 的右孩子cur 為 p 的左孩子則針對(duì) p 做右單旋轉(zhuǎn)最后則轉(zhuǎn)換成了情況2(雙旋)。紅黑樹(shù)模擬實(shí)現(xiàn) STL 中的 map 與 set(暫略)