【C++修炼之路】21.红黑树封装map和set

每一个不曾起舞的日子都是对生命的辜负

前言

上一节中，说到了红黑树的实现，并且已经知道map和set的底层共用了同一套红黑树的结构。但这样就会出现一个问题，map的数据域和set不一样，比较大小的方式自然也就不一样。因此上一篇中的红黑树还需要做出一些改变才能用来实现map和set。

一.改良红黑树的数据域结构

对于如何设计针对map、set的红黑树结构，看源码的实现无疑是最好的方式：

对于源码的实现，我们知道set是<k,k>的键值对，但是在使用时却只显示一个k，map是<k,value>的键值对，通过观察源码发现，map的节点结构为rb_tree<key_type, value_type>，但发现其设计方式很特殊，value_type是pair<const Key, T>的重命名，也就是说，map节点结构的key_type并不作为数据域，value_type单一类型就充当了数据域，而key_type实际上可以充当查找的作用。因此，下面改良红黑树就采用这种方式：一个类型T作为结点的全部数据域。

1.1 改良后的结点

enum Color//颜色采用枚举，但STL库采用的是特殊的bool值，后续会看
{RED,//0BLACK//1
};template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};

与之前的双参数<class K, class V>相比，改良之后的T作为了全部的数据域，即T也可以代表pair类型。

1.2 改良后的类

在前言中提到，比较方式也是一个头疼的问题，这个时候就可以自己封装一个比较方式，即以仿函数的形式进行比较。

由于只有比较方式进行了改变，因此除了insert其他的都没有变化，所以下面只展示insert

enum Color//颜色采用枚举，但STL库采用的是特殊的bool值，后续会看
{RED,//0BLACK//1
};template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<const K, V>, MapKeyOfT> _t;
template<class K, class T, class KeyOfT>//新增的KeyOfT就是仿函数
class RBTree
{typedef RBTreeNode<T> Node;
public:bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点为黑色return true;}KeyOfT kot;//仿函数Node* parent = nullptr;Node* cur = _root;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 false;}}cur = new Node(data);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;//看叔叔颜色//情况1：uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况2或3：不用考虑叔叔的问题，即叔叔为空还是为黑{if (cur == parent->_left)//情况2{//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况3{//     g//   p//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//与上述代码的左右反过来了而已，步骤一样但左右相反。{Node* uncle = grandfather->_left;//情况1if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况2和3{//  g//     p//        cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//  g//     p//   cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}}_root->_col = BLACK;return true;}
private:Node* _root = nullptr;
};

二. 封装的set和map

以仿函数封装就可以完成比较。

2.1 set.h

#pragma once
#include"RBTree.h"namespace cfy
{template<class K>class set{struct SetKeyOfT//仿函数{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};void test_set(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };set<int> s;for (auto e : a){s.insert(e);}}
}

2.2 map.h

#pragma once
#include"RBTree.h"
namespace cfy
{template<class K, class V>class map{struct MapKeyOfT//仿函数{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:bool insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void test_map(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };map<int, int> m;for (auto e : a){m.insert(make_pair(e, e));}}
}

三. 迭代器

需要将有关迭代器的功能都封装起来，这在之前的vector、list模拟实现时已经了解过。对于map和set的迭代器，重要的函数重载就是++和–了。为了map和set能够共用这一套迭代器，因此将其封装在RBTree里。

3.1 迭代器封装

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

但由于我们上一届中设计的RBTree没有头结点这个结构，因此我们也就不与STL的实现方式完全一样，end()就直接设置为nullptr。

//迭代器
template<class T>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T> Self;//迭代器类进行typedefNode* _node;__RBTreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}//迭代器++//迭代器--//上面两个都拿出来在下面bool operator!=(const Self& s){return _node != s._node;}};

一. 对于++，有这么两种选择：

• 如果右树不为空，则找到右树的最左节点。
• 如果右树为空，则找到孩子是父亲的左孩子的那个祖先。

Self& operator++()//迭代器返回的还是迭代器
{if (_node->_right)//1.右不为空，找到右子树的最左节点{Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else//2.右为空，则找祖先：孩子是父亲的左的那个祖先{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}

二. 对于–，有这么两种选择：（事实上思路就是与++相反）

• 如果左树不为空，则找到左树的最右结点（也就是最大结点)。
• 如果左树为空，则找到孩子是父亲的右孩子的那个祖先。

Self& operator--()
{if (_node->_left){Node* max = _node->_left;while (max->_right)//max一定存在，因此不需要写出max条件{max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}

3.2 const迭代器

如果是const迭代器，那可以在迭代器类中多加上两个模板参数：T&, T*偏特化，当然实际上是Ref，Ptr的全特化；由于set不能修改，因此set的普通迭代器和const迭代器都应该是const类型，但map的value可以修改，因此我们就需要在RBTree中把普通迭代器和const迭代器均实现出来。此外，对于map来讲，需要实现operator[]的重载，因此我们插入函数返回的值也应该从bool变成pair类型，这样才便于在operator[]重载中进行操作。由于代码繁琐，且需要处理一些细节问题，因此代码的注释将会就那些进行解释，看下面代码就可以了。

四.完整代码实现

提示：需要注意细节问题，如普通迭代器可以赋值给const迭代器的原理。

4.1 RBTree.h

#pragma onceenum Color//颜色采用枚举，但STL库采用的是特殊的bool值，后续会看
{RED,//0BLACK//1
};template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};//迭代器
// class< T, T&, T*>
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器类进行typedef//如果Ref和Ptr都是非const，则下面与上面没区别，但如果是const，则下面仍是非const，因此可以const迭代器可以赋值给非const就是因为下面的这个，就是一个构造typedef __RBTreeIterator<T, T&, T*> iterator;//满足普通迭代器可以赋值给const迭代器Node* _node;__RBTreeIterator(Node* node):_node(node){}// 普通迭代器的时候，他是拷贝构造// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator& s)//加上这个，就满足普通迭代器赋值给const迭代器:_node(s._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++()//迭代器返回的还是迭代器{if (_node->_right)//1.右不为空，找到右子树的最左节点{Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else//2.右为空，则找祖先：孩子是父亲的左的那个祖先{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* max = _node->_left;while (max->_right)//max一定存在，因此不需要写出max条件{max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}};// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<const K, V>, MapKeyOfT> _t;
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(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* left = _root;while (left && left->_left){left = left->_left;}return const_iterator(left);}const_iterator end() const{return const_iterator(nullptr);}pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点为黑色return make_pair(iterator(_root), true);}KeyOfT kot;//仿函数Node* parent = nullptr;Node* cur = _root;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);}}cur = new Node(data);Node* newnode = cur;//加上这个是为了pair返回值时return的时候需要返回，因为cue会变，因此记录一下这个结点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;//看叔叔颜色//情况1：uncle存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况2或3：不用考虑叔叔的问题，即叔叔为空还是为黑{if (cur == parent->_left)//情况2{//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况3{//     g//   p//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//与上述代码的左右反过来了而已，步骤一样但左右相反。{Node* uncle = grandfather->_left;//情况1if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//情况2和3{//  g//     p//        cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//  g//     p//   cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}//旋转代码和AVL一样，只是去掉了平衡因子void RotateL(Node* parent)//左单旋{//1.记录subR, subRLNode* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)//subRL不为空则需要连接到parent{subRL->_parent = parent;}Node* ppNode = parent->_parent;//记录保存subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr)//说明根节点变化{_root = subR;_root->_parent = nullptr;}else//如果是局部子树{//判断ppNode之前是左连接还是右连接if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void Inorder(){_Inorder(_root);}bool IsBalance()//检查是否为红黑树结构{if (_root == nullptr){return true;}if (_root->_col != BLACK){return false;}int ref = 0;Node* left = _root;while (left){if (left->_col == BLACK){++ref;}left = left->_left;}//遍历这棵树，就好了，检查是否存在连续的红结点。//检查父亲，因为孩子不一定有，但是一定有父亲return Check(_root, 0, ref);}private:bool Check(Node* root, int blackNum, int ref){if (root == nullptr){if (blackNum != ref){cout << "违反规则：一条路径上的黑色节点数量不同" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则，出现连续红色结点" << endl;}if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, ref)&& Check(root->_right, blackNum, ref);}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}Node* _root = nullptr;
};

4.2 set.h

#pragma once
#include"RBTree.h"namespace cfy
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://加上typename是由于没有实例化的模板不能进行typedef。由于不能修改，因此均用consttypedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();//_t.begin()是普通迭代器，iterator是const,因此需要修改}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){//直接return会造成const与非const的类型不匹配//因为set的iterator默认就是const，但return的并不是const//因此需要如下修正：pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};void test_set(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };set<int> s;for (auto e : a){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){//*it += 10;//set这里不能被修改，因此const迭代器统一cout << *it << " ";++it;}cout << endl;for (auto& e : s){cout << e << " ";}cout << endl;}
}

4.3 map.h

#pragma once
#include"RBTree.h"
namespace cfy
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public://加上typename是由于没有实例化的模板不能进行typedef。typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{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 = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void test_map(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };map<int, int> m;for (auto e : a){m.insert(make_pair(e, e));}map<int, int>::iterator it = m.begin();while (it != m.end()){//it->first++; 经过const就不能修改了it->second++;//允许被修改cout << it->first << ":" << it->second << endl;++it;}cout << endl;//map统计水果操作的次数string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "西瓜","苹果", "苹果","西瓜","苹果",  "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (const auto& kv : countMap)//注意加引用，不给就是拷贝构造，代价大{cout << kv.first << ":" << kv.second << endl;}}
}

4.4 Test.cpp

#include<iostream>
#include<map>
#include<set>
using namespace std;
#include"RBTree.h"
#include"Map.h"
#include"Set.h"
int main()
{cfy::test_set();cfy::test_map();return 0;
}