【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;
}