1.關聯式容器之前接觸的STL中的部分容器比如vectorlistdequeforward_list(C11)等這些統稱為序列式容器因為其底層為線性序列的數據結構里面存儲的是元素本身。關聯式容器也是用來存儲數據的與序列式容器不同的是其里面存儲的是keyvalue結構的鍵值對在數據檢索時比序列式容器效率更高。2.鍵值對用來表示具有一一對應關系的一種結構該結構中一般只包含兩個成員變量key和valuekey代表鍵值value表示與key對應的信息。3.樹形結構的關聯式容器STL總共實現了兩種不同的關聯式容器樹形結構與哈希結構。樹形結構的關聯式容器主要有四種mapsetmultimapmultiset。這四種容器的共同點是使用平衡搜索樹(即紅黑樹)作為其底層結果容器中的元素是一個有序的列。3.1 setset 中只存放 value 值且每個 value 必須唯一。set 中元素不能修改(元素是const)只可以插入刪除。插入元素時只需要插入 value不需要構造鍵值對。set 中元素不可以重復可以使用它進行去重按小于來比較遍歷即可得到有序序列。3.2 mapmap 是關聯式容器它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。在元素訪問時與operator[]類似的操作at()(該函數不常用)函數都是通過key找到與key對應的value然后返回其引用不同的是當key不存在時operator[]用默認value與key構造鍵值對然后插入返回該默認valueat()函數直接拋異常。3.3 multiset multiset是按照特定順序的容器其中元素可以重復的。在 multiset 中元素的value也會識別它(因為 multiset 中本身存儲的就是value, value組成的鍵值對因此 value 本身就是 keykey 就是 value類型為 T)multiset 元素的值不能在容器中修改(因為元素總是 const)可以插入刪除。set 與 multiset 的接口相同不作展示唯一區別就是可存儲重復元素。3.4 multimap同上 multimap 和 map 的唯一不同是map 中 key 值唯一multimap 中 key 是可以重復的。4.底層結構map/multimap/set/multiset 其底層結構都是二叉搜索樹實現的但是二叉搜索樹有其缺陷假如往樹中插入的元素有序便會退化為單支樹時間復雜度便會退化為O(N)因此對其進行了平衡處理即二叉平衡樹(AVL)。4.1 AVL樹一棵AVL樹或者是空樹或者是左右都是AVL樹、左右子樹高度差(簡稱平衡因子)的絕對值不超過1(-1/0/1)的二叉搜索樹。AVL樹的旋轉1新結點插入較高左子樹的左側——左左右單旋2新結點插入較高右子樹的右側——右右左單旋3新結點插入較高左子樹右側——左右先左單旋在右單旋(先旋轉再考慮平衡因子更新)4新結點插入較高右子樹左側——右左先右單旋再左單旋AVL樹實現#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說明parent所在子樹高度不變不會影響祖先 //4.更新后parent平衡因子 -1 or 1說明parent所在子樹高度變化會影響祖先需繼續沿著到root的路徑往上更新 //5.更新后parent平衡因子 -2 or 2說明parent所在子樹高度變化且不平衡對parent所在子樹進行旋轉讓它平衡 //更新平衡因子 while (parent)//更新到根節點結束 { if (cur parent-_pleft) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break;//結束 } else if (parent-_bf -1 || parent-_bf 1) { //繼續往上更新 cur parent; parent parent-_parent; } else if (parent-_bf -2 || parent-_bf 2) { //子樹不平衡了需要旋轉 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); //右左雙旋本質是 孫子結點左子樹給祖父結點做右子樹右子樹給父節點做左子樹自己變為根節點 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); //左右雙旋是 孫子節點左子樹給父節點做右子樹右子樹給祖父節點做左子樹自己變成根節點 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紅黑樹是一種二叉搜索樹但每個結點上增加一個存儲位表示結點的顏色可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制紅黑樹確保沒有一條路徑會比其他路徑長出兩倍因為是接近平衡的。紅黑樹的性質1每個結點不是黑色就是紅色2根結點是黑色3如果一個結點是紅色的則它兩個孩子都是黑色的4對于每個結點從該結點到其所有后代葉結點的簡單路徑均包含相同數目的黑色結點5每個葉子結點都是黑色的(此處葉子節點指的空結點)紅黑樹的插入操作1按照二叉搜素樹規則插入新結點2檢測新結點插入后紅黑樹的性質是否遭到破壞因為新結點的默認顏色是紅色因此如果其雙親結點的顏色是黑色沒有違反紅黑樹任何性質則不需要調整但當新插入結點的雙親結點顏色為紅色時就違反了性質三不能有連續紅色結點需分情況討論。(cur 為當前結點p為父結點g為祖父結點u為叔叔結點)1cur 為紅p 為紅g 為黑u 存在且為紅解決方式將p、u 改為黑g 改為紅然后把 g 當成 cur繼續向上調整。2cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的左孩子則進行右單旋轉相反p 為 g 的右孩子cur 為 p 的右孩子則進行左單旋最后 p、g 變色——p 變黑g 變紅。3cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的右孩子則針對 p 做左單旋轉相反p 為g 的右孩子cur 為 p 的左孩子則針對 p 做右單旋轉最后則轉換成了情況2(雙旋)。紅黑樹模擬實現 STL 中的 map 與 set(暫略) map 和 set 使用及模擬實現
1.關聯式容器之前接觸的STL中的部分容器比如vectorlistdequeforward_list(C11)等這些統稱為序列式容器因為其底層為線性序列的數據結構里面存儲的是元素本身。關聯式容器也是用來存儲數據的與序列式容器不同的是其里面存儲的是keyvalue結構的鍵值對在數據檢索時比序列式容器效率更高。2.鍵值對用來表示具有一一對應關系的一種結構該結構中一般只包含兩個成員變量key和valuekey代表鍵值value表示與key對應的信息。3.樹形結構的關聯式容器STL總共實現了兩種不同的關聯式容器樹形結構與哈希結構。樹形結構的關聯式容器主要有四種mapsetmultimapmultiset。這四種容器的共同點是使用平衡搜索樹(即紅黑樹)作為其底層結果容器中的元素是一個有序的列。3.1 setset 中只存放 value 值且每個 value 必須唯一。set 中元素不能修改(元素是const)只可以插入刪除。插入元素時只需要插入 value不需要構造鍵值對。set 中元素不可以重復可以使用它進行去重按小于來比較遍歷即可得到有序序列。3.2 mapmap 是關聯式容器它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。在元素訪問時與operator[]類似的操作at()(該函數不常用)函數都是通過key找到與key對應的value然后返回其引用不同的是當key不存在時operator[]用默認value與key構造鍵值對然后插入返回該默認valueat()函數直接拋異常。3.3 multiset multiset是按照特定順序的容器其中元素可以重復的。在 multiset 中元素的value也會識別它(因為 multiset 中本身存儲的就是value, value組成的鍵值對因此 value 本身就是 keykey 就是 value類型為 T)multiset 元素的值不能在容器中修改(因為元素總是 const)可以插入刪除。set 與 multiset 的接口相同不作展示唯一區別就是可存儲重復元素。3.4 multimap同上 multimap 和 map 的唯一不同是map 中 key 值唯一multimap 中 key 是可以重復的。4.底層結構map/multimap/set/multiset 其底層結構都是二叉搜索樹實現的但是二叉搜索樹有其缺陷假如往樹中插入的元素有序便會退化為單支樹時間復雜度便會退化為O(N)因此對其進行了平衡處理即二叉平衡樹(AVL)。4.1 AVL樹一棵AVL樹或者是空樹或者是左右都是AVL樹、左右子樹高度差(簡稱平衡因子)的絕對值不超過1(-1/0/1)的二叉搜索樹。AVL樹的旋轉1新結點插入較高左子樹的左側——左左右單旋2新結點插入較高右子樹的右側——右右左單旋3新結點插入較高左子樹右側——左右先左單旋在右單旋(先旋轉再考慮平衡因子更新)4新結點插入較高右子樹左側——右左先右單旋再左單旋AVL樹實現#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說明parent所在子樹高度不變不會影響祖先 //4.更新后parent平衡因子 -1 or 1說明parent所在子樹高度變化會影響祖先需繼續沿著到root的路徑往上更新 //5.更新后parent平衡因子 -2 or 2說明parent所在子樹高度變化且不平衡對parent所在子樹進行旋轉讓它平衡 //更新平衡因子 while (parent)//更新到根節點結束 { if (cur parent-_pleft) { parent-_bf--; } else { parent-_bf; } if (parent-_bf 0) { break;//結束 } else if (parent-_bf -1 || parent-_bf 1) { //繼續往上更新 cur parent; parent parent-_parent; } else if (parent-_bf -2 || parent-_bf 2) { //子樹不平衡了需要旋轉 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); //右左雙旋本質是 孫子結點左子樹給祖父結點做右子樹右子樹給父節點做左子樹自己變為根節點 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); //左右雙旋是 孫子節點左子樹給父節點做右子樹右子樹給祖父節點做左子樹自己變成根節點 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紅黑樹是一種二叉搜索樹但每個結點上增加一個存儲位表示結點的顏色可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制紅黑樹確保沒有一條路徑會比其他路徑長出兩倍因為是接近平衡的。紅黑樹的性質1每個結點不是黑色就是紅色2根結點是黑色3如果一個結點是紅色的則它兩個孩子都是黑色的4對于每個結點從該結點到其所有后代葉結點的簡單路徑均包含相同數目的黑色結點5每個葉子結點都是黑色的(此處葉子節點指的空結點)紅黑樹的插入操作1按照二叉搜素樹規則插入新結點2檢測新結點插入后紅黑樹的性質是否遭到破壞因為新結點的默認顏色是紅色因此如果其雙親結點的顏色是黑色沒有違反紅黑樹任何性質則不需要調整但當新插入結點的雙親結點顏色為紅色時就違反了性質三不能有連續紅色結點需分情況討論。(cur 為當前結點p為父結點g為祖父結點u為叔叔結點)1cur 為紅p 為紅g 為黑u 存在且為紅解決方式將p、u 改為黑g 改為紅然后把 g 當成 cur繼續向上調整。2cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的左孩子則進行右單旋轉相反p 為 g 的右孩子cur 為 p 的右孩子則進行左單旋最后 p、g 變色——p 變黑g 變紅。3cur 為紅p 為紅g 為黑u 不存在/u存在且為黑解決方式p 為 g 的左孩子cur 為 p 的右孩子則針對 p 做左單旋轉相反p 為g 的右孩子cur 為 p 的左孩子則針對 p 做右單旋轉最后則轉換成了情況2(雙旋)。紅黑樹模擬實現 STL 中的 map 與 set(暫略)