【C++進階】第8課—紅黑樹封裝map和set

文章目錄

1. map和set的源碼及框架分析
2. 模擬實現map和set
- 2.1 實現可以復用紅黑樹的框架，支持insert操作
- 2.2 實現迭代器iterator
- - 2.2.1 實現迭代器++
  - 2.2.2 實現迭代器 - -
  - 2.2.3 解決key不能修改的問題
  - 2.2.4 重載operator[ ]
3. 完整代碼
- 3.1 ==紅黑樹頭文件RBTree.h==
- 3.2 ==mymap頭文件==
- 3.3 ==myset頭文件==
- 3.4 ==測試文件test.cpp==

??學過紅黑樹后，現在我們來學習如何使用紅黑樹來封裝mymap和myset

1. map和set的源碼及框架分析

SGI-STL30版本源代碼，map和set的源代碼在map/set/stl_map.h/stl_set.h/stl_tree.h等幾個頭文件中

在這里插入圖片描述

2. 模擬實現map和set

2.1 實現可以復用紅黑樹的框架，支持insert操作

當然，之前我們實現的紅黑樹是以map的key/value實現的，要實現泛型，就需要改變一些參數，例如節點數據應該給模版參數T，插入數據時應該是T& data
對比源碼調整一下，key參數就用K，value參數就用V，紅黑樹中的數據類型，我們使用T
其次因為RBTree實現了泛型不知道T參數到底是K，還是pair<K, V>，那么insert內部進行插入邏輯比較時，就沒辦法進行比較，因為pair的默認支持的是key和value一起參與比較，我們需要的是任何時候只比較key，所以我們在map和set層分別實現一個MapKeyOfT和SetKeyOfT的仿函數傳給RBTree的KeyOfT，然后RBTree中通過KeyOfT仿函數取出T類型對象中的key，再進行比較，具體細節參考如下代碼實現

在這里插入圖片描述

2.2 實現迭代器iterator

迭代器實現時，其核心邏輯就是++/- -時該如何實現
迭代器++的核心邏輯就是不看全局，只看局部，只考慮當前中序局部要訪問的下一個結點

實現迭代器的思路
1. 實現紅黑樹，封裝迭代器，使用紅黑樹封裝map和set
2. 實現迭代器++/- -
3. 搭建iterator和const_iterator框架
4. 解決key不支持修改的問題
5. 重載方括號operator[ ]

2.2.1 實現迭代器++

第一種情況：it所指向的節點，它的右子樹不為空，++it步驟

在這里插入圖片描述

第2種情況: it所指向的節點，它的右子樹為空時，++it步驟

在這里插入圖片描述

如果it節點是它父節點的左孩子節點

在這里插入圖片描述

代碼實現邏輯

在這里插入圖片描述

2.2.2 實現迭代器 - -

迭代器- -時思路和++時大同小異，這里直接上代碼講解

在這里插入圖片描述

搭建iterator和const_iterator框架

在這里插入圖片描述

2.2.3 解決key不能修改的問題

在這里插入圖片描述

2.2.4 重載operator[ ]

在這里插入圖片描述

3. 完整代碼

3.1 紅黑樹頭文件RBTree.h

#pragma once
#include <iostream>
using namespace std;//枚舉常量
enum Colour
{RED,BLACK
};//紅黑樹節點
template <class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};//迭代器
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;//默認構造RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}//重載運算符++Self& operator++(){//如果it節點的右子樹存在if (_node->_right){//++it ---> 找右子樹的最左節點_node = _node->_right;while (_node->_left){_node = _node->_left;}}//如果it節點的右子樹不存在else{//向上更新Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}//重載運算符--    右-根-左Self& operator--(){//在 _node == end() 處--if (_node == nullptr){//找根節點右子樹最右節點Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}//如果不是在end()--else if (_node->_left){// 左?樹不為空，中序左?樹最后?個Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{// 孩?是?親右的那個祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//重載解引用操作符*Ref operator*(){return _node->_data;}//重載解引用操作符->Ptr operator->(){return &_node->_data;}//重載操作符!=bool operator!=(const Self& s) const{return _node != s._node;}//重載操作符==bool operator==(const Self& s) const{return _node == s._node;}
};//紅黑樹
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;RBTree() = default;//迭代器使用Iterator begin(){Node* MinLeft = _root;while (MinLeft && MinLeft->_left){MinLeft = MinLeft->_left;}return Iterator(MinLeft, _root);}Iterator end(){return Iterator(nullptr, _root);}Const_Iterator begin() const{Node* MinLeft = _root;while (MinLeft && MinLeft->_left){MinLeft = MinLeft->_left;}return Const_Iterator(MinLeft, _root);}Const_Iterator end() const{return Const_Iterator(nullptr, _root);}//插入節點pair<Iterator,bool> insert(const T& data){//如果是空樹if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return { Iterator{_root,_root},true };}//如果是非空樹 KeyOfT kot;Node* parent = nullptr;Node* cur = _root;//尋找插入位置while (cur){//插入值比cur節點值大if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}//插入值比cur節點值小else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}elsereturn { Iterator(cur,_root),false };}//插入節點cur = new Node(data);cur->_col = RED;Node* newnode = cur;//如果插入值大于parent值if (kot(data) > kot(parent->_data))parent->_right = cur;//如果插入值小于parent值else if (kot(data) < kot(parent->_data))parent->_left = cur;//存儲cur節點的父節點cur->_parent = parent;//定義cur節點的p、u、g節點 ---> 更新while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//如果parent為grandfather的左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;//第一種情況:父親、叔叔都為紅，爺爺為黑if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//繼續向上處理cur = grandfather;parent = cur->_parent;}//第2、3種情況else{//第2種情況 ---> uncle節點不存在或者為黑色//      g//   p     u//c 右單旋if (cur == parent->_left){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//第3種情況 ---> uncle節點不存在或者為黑色//      g//   p     u//      c  左單旋 + 右單旋else{RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}//如果parent為grandfather的右孩子else{Node* uncle = grandfather->_left;//第一種情況:父親、叔叔都為紅，爺爺為黑if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//繼續向上處理cur = grandfather;parent = cur->_parent;}//第2、3種情況else{//第2種情況 ---> uncle節點不存在或者為黑色//      g//   u     p//左單旋       cif (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//第3種情況 ---> uncle節點不存在或者為黑色//      g//   u     p//      c  右單旋 + 左單旋else{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}//直接賦予根節點黑色_root->_col = BLACK;return { Iterator{newnode,_root},true };}//左單旋void RotateL(Node* parent){//定義兩個節點指針Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;if (subRL)subRL->_parent = parent;Node* parent_Parent = parent->_parent;parent->_parent = subR;//如果parent為根節點if (parent_Parent == nullptr){_root = subR;subR->_parent = nullptr;}//如果parent不是根節點else{//如果旋轉之前parent所在的整個子樹為根節點的左子樹if (parent_Parent->_left == parent)parent_Parent->_left = subR;elseparent_Parent->_right = subR;subR->_parent = parent_Parent;}}//右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;Node* parent_Parent = parent->_parent;parent->_parent = subL;//如果parent為根節點if (parent == _root){_root = subL;subL->_parent = nullptr;}//如果parent不是根節點else{if (parent_Parent->_left == parent)parent_Parent->_left = subL;elseparent_Parent->_right = subL;subL->_parent = parent_Parent;}}//中序遍歷輸出數據void Inorder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;KeyOfT kot;_Inorder(root->_left);cout << kot(root->_data) << " ";_Inorder(root->_right);}//紅黑樹節點個數size_t Size(){return _Size(_root);}size_t _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}//查找Iterator Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first)cur = cur->_right;else if (key < cur->_kv.first)cur = cur->_left;elsereturn Iterator(cur, _root);}return end();}//銷毀void Destroy(Node* _root){if (_root == nullptr)return;Destroy(_root->_left);Destroy(_root->_right);delete _root;}//析構~RBTree(){Destroy(_root);_root = nullptr;}//前序遍歷查找每條路徑黑色節點個數bool Check(Node* root, int Count_BlackNode, int retNum){if (root == nullptr){if (Count_BlackNode != retNum){cout << "存在黑色節點數量不等的路徑" << endl;return false;}return true;}KeyOfT kot;//root節點非空 ---> 檢查兩個孩子節點不方便，可能還有孩子不存在，直接檢查其父節點if (root->_col == RED && root->_parent->_col == RED){cout << kot(root->_data) << "存在連續的紅色節點" << endl;return false;}//如果節點為黑色if (root->_col == BLACK){++Count_BlackNode;}return Check(root->_left, Count_BlackNode, retNum) && Check(root->_right, Count_BlackNode, retNum);}//檢查是否滿足平衡bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED){cout << "根節點為紅色！" << endl;return false;}//記錄一條路徑上黑色節點數量int retNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++retNum;}cur = cur->_left;}return Check(_root, 0, retNum);}private:Node* _root = nullptr;
};

3.2 mymap頭文件

#pragma once#include "RBTree_副本.h"namespace ZY
{//用于比較的仿函數template<class K,class V>class mymap{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Const_Iterator const_iterator;//插入pair<iterator, bool> insert(const pair<K, V>& kv){return _mymap.insert(kv);}//operator[]V& operator[](const K& key){pair<iterator, bool> ret = _mymap.insert({ key,V() });return ret.first->second;}//判斷樹平衡bool IsBalance(){return _mymap.IsBalance();}//返回節點個數size_t size(){return _mymap.Size();}//中序遍歷void Inoreder(){_mymap.Inorder();}iterator begin(){return _mymap.begin();}iterator end(){return _mymap.end();}const_iterator begin() const{return _mymap.begin();}const_iterator end() const{return _mymap.end();}private:RBTree<K, pair<const K, V>, MapKeyOfT> _mymap;};
}

3.3 myset頭文件

#pragma once#include "RBTree_副本.h"namespace ZY
{//用于比較的仿函數template<class K>class myset{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::Const_Iterator const_iterator;//插入pair<iterator, bool> insert(const K& key){return _myset.insert(key);}//判斷樹平衡bool IsBalance(){return _myset.IsBalance();}//返回節點個數size_t size(){return _myset.Size();}//中序遍歷void Inoreder(){_myset.Inorder();}iterator begin(){return _myset.begin();}iterator end(){return _myset.end();}const_iterator begin() const{return _myset.begin();}const_iterator end() const{return _myset.end();}private:RBTree<K, const K, SetKeyOfT> _myset;};
}

3.4 測試文件test.cpp

#include"mymap.h"
#include"myset.h"
#include<vector>void print_set(const ZY::myset<int>& s)
{for (auto e : s){cout << e << " ";}cout << endl;
}void print_map(const ZY::mymap<string,string>& mp)
{for (auto e : mp){cout << e.first << " " << e.second << " ";}cout << endl;
}//插入測試
void myset_test1()
{ZY::myset<int> st;//常規測試//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//for (auto& e : a)//{//	st.insert(e);//}//帶有雙旋的測試用例int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto& e : arr){st.insert(e);}if (st.IsBalance())cout << "該二叉樹是紅黑樹!" << endl;elsecout << "該二叉樹不是紅黑樹!" << endl;cout << "節點個數:" << st.size() << endl;//st.Inoreder();//測試迭代器ZY::myset<int>::iterator it = st.begin();while (it != st.end()){//*it += 1;cout << *it << " ";++it;}cout << endl;print_set(st);
}void mymap_test1()
{ZY::mymap<string, string> mp;mp.insert({ "left","左邊" });mp.insert({ "right","右邊" });mp.insert({ "sort","排序" });mp.insert({ "string","字符串" });//mp.Inoreder();//mp.size();if (mp.IsBalance())cout << "該二叉樹是紅黑樹!" << endl;elsecout << "該二叉樹不是紅黑樹!" << endl;cout << "節點個數:" << mp.size() << endl;ZY::mymap<string, string>::iterator it = mp.begin();while (it != mp.end()){cout << it->first << ":" << it->second <<" ";++it;}cout << endl;//auto it1 = mp.end();//while (it1 != mp.begin())//{//	--it1;//	cout << it1->first << ":" << it1->second << " ";//}//cout << endl;mp["哈哈哈"];mp["left"] = "耶耶耶";print_map(mp);
}void test()
{const int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(i + rand());}size_t begin2 = clock();ZY::myset<int> t;for (size_t i = 0; i < v.size(); ++i){t.insert(v[i]);}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << "Size:" << t.size() << endl;if (t.IsBalance())cout << "該二叉樹是紅黑樹!" << endl;elsecout << "該二叉樹不是紅黑樹!" << endl;}int main()
{//myset_test1();mymap_test1();//test();return 0;
}