C++：使用红黑树封装map和set

目录

一. 如何使用一颗红黑树同时实现map和set

二. 红黑树的节点插入操作

三. 红黑树迭代器的实现

3.1 begin()和end()

3.2 operator++和operator--

3.3 红黑树迭代器实现完整版代码

四. map和set的封装

附录：用红黑树封装map和set完整版代码

1. RBTree.h文件

2. map.h文件

3. set.h文件

---

一. 如何使用一颗红黑树同时实现map和set

我们知道，map和set的底层都是通过红黑树来实现的，它们的不同在于：map存储的是一键值对，键值对的第一个数据用于搜索树的比较，第二个数据用于与之配对，而set则只有一个数据。需要采用模板（泛型编程）的方法来定义红黑树节点，并在map和set中给定红黑树类模板不同的模板参数类型，

图1.1 红黑树节点、红黑树类模板与map和set类模板之间的关系

观察图1.1，我们可以总结出RBTreeNode、RBTree、map和set类模板之间的如下规则：

• 红黑树节点只有一个模板参数，set有一个模板参数，其本身就是节点的数据类型，map有两个模板参数，分别为创建键值对的first和second数据类型。
• 在map中，RBTreeNode中的模板参数类型为pair键值对，由于map中要取出键值对的first比较创建搜索树，而直接用>或<对pair比较不符合要求，因此定义仿函数KeyOfV来获取用于比较的数据。

二. 红黑树的节点插入操作

用于对map和set封装的红黑树的查找操作与普通红黑树一致，唯一的不同在于需要创建KeyOfV类的对象，并使用仿函数进行比较。如果希望与库中的insert更加贴合，则应返还键值对pair<iterator, bool>类型数据。

具体的红黑树的插入实现流程，可参考博文：C++数据结构：手撕红黑树_【Shine】光芒的博客-CSDN博客

代码2.1：（红黑树节点插入）

	std::pair<iterator, bool> insert(const T& date){//插入第一个节点if (_root == nullptr){_root = new Node(date);_root->_col = BLACK;   //根节点为黑色return std::make_pair(_root, true);}KeyOfT kov;   //用于筛选比较数据的类对象//寻找节点插入的位置Node* parent = nullptr;   Node* cur = _root;while (cur){//如果cur节点的key值大于插入键值对的key，向左子树查找if (kov(cur->_date) > kov(date)){parent = cur;cur = cur->_left;}else if(kov(cur->_date) < kov(date))  //如果cur节点的key值小于插入键值对的key，向左子树查找{parent = cur;cur = cur->_right;}else  //相等表明节点已存在，插入失败{return std::make_pair(cur, false);}}//判断新节点是parent的左节点还是右节点，链接//默认新插入的节点为红色cur = new Node(date);Node* newNode = cur;cur->_col = RED;cur->_parent = parent;if (kov(parent->_date) > kov(date)){parent->_left = cur;}else{parent->_right = cur;}//如果parent节点不为空且为红色，那么红黑树的结构在插入节点后被破坏，需要调整while (parent && parent->_col == RED){Node* grandParent = parent->_parent;   //祖父节点assert(grandParent);assert(grandParent->_col == BLACK);   //断言检查，如果祖父节点为空或为黑色，那么红黑树结构在节点插入之前就存在问题if (parent == grandParent->_left)  //插入在祖父节点的左子树{Node* uncle = grandParent->_right;//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}	else  //情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑{if (parent->_left == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//    g//  p   u//cRotateR(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行左右双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g//  p   u//   u RotateLR(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}else  //parent == grandParent->_right{Node* uncle = grandParent->_left;  //叔叔节点//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}else{//情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑if (parent->_right == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//   g// u   p//       cRotateL(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行右左双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g// u     p//     cRotateRL(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}}_root->_col = BLACK;   //根节点为黑色return std::make_pair(newNode, true);}

三. 红黑树迭代器的实现

我们要额外封装一个类struct  __RBTree_iterator_来实现红黑树迭代器，这个类有三个模板参数T、Ref、Ptr，这样做的目的是定义一份迭代器类模板就可以实现普通迭代器和const迭代器。

• typedef __RBTree_iterator_<T, T&, T*> iterator;   //红黑树迭代器

3.1 begin()和end()

STL标准规定迭代器区间begin()和end()为左闭右开区间，而对红黑树遍历获取的数据为升序序列，因此，begin()应该为左下角位置处的节点，end()应该为哨兵卫的头结点_head。这里从便于理解和实现的角度出发，将_head设为nullptr，即：end()返回空指针。

图3.1 红黑树的begin()和end()

代码3.1：（begin和end）

	//获取begin()位置 -- 最左侧节点iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}

3.2 operator++和operator--

operator++就是查找中序遍历的下一个节点，可分为两种情况讨论：

• 如果节点的右子树不为空，则为右子树最左侧的节点。
• 如果节点的右子树为空，则向上查找孩子不是父亲的右子节点的那个节点。

图3.2 operator++的两种情况

operator--与operator++正好相反，为找中序遍历的前一个节点，亦可分两种情况讨论：

• 如果节点的左子树不为空，则为左子树最右侧的节点。
• 如果节点的左子树为空，则向上查找孩子不是父亲的左子节点的那个节点。

图3.3 operator--的两种情况

代码3.2：（operator++和operator--）

	typedef RBTreeNode<T> Node;    //红黑树节点typedef __RBTree_iterator_<T, Ref, Ptr> Self;	//++运算符重载函数Self& operator++(){if (_node->_right != nullptr){//找右子树的最左侧节点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{//找孩子节点为左孩子节点的位置，或者父亲节点为空Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_right == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}//--运算符重载函数Self& operator--(){if (_node->_left != nullptr){Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}

3.3 红黑树迭代器实现完整版代码

//红黑树迭代器模板
template<class T, class Ref, class Ptr>
struct __RBTree_iterator_
{typedef RBTreeNode<T> Node;    //红黑树节点typedef __RBTree_iterator_<T, Ref, Ptr> Self;Node* _node;//构造函数__RBTree_iterator_(Node* node): _node(node){ }//解引用函数Ref operator*(){return _node->_date;}//成员访问操作符->重载Ptr operator->(){return &_node->_date;}bool operator==(const Self& it) const{return _node == it._node;}bool operator!=(const Self& it) const{return _node != it._node;}//++运算符重载函数Self& operator++(){if (_node->_right != nullptr){//找右子树的最左侧节点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{//找孩子节点为左孩子节点的位置，或者父亲节点为空Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_right == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}//--运算符重载函数Self& operator--(){if (_node->_left != nullptr){Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
};

四. map和set的封装

map和set底层都是通过红黑树来实现的，只需在map和set中定义一颗红黑树的自定义类型变量，然后调用红黑树的接口函数即可。

这里需要特别注意的是map中的operator[]函数，其实现为先调用insert函数，insert函数返回一个键值对，first为插入的节点或Key与插入节点相等位置的迭代器，second为bool类型变量，用来表示是否有新节点成功插入。函数只需返回insert返回的键值对的second的引用即可。

注意用于提取Key的仿函数要在map和set中分别定义。

代码4.1：（map的封装）

namespace zhang
{template <class K, class V>class map{struct KeyOfV{const K& operator()(const std::pair<K,V>& val){return val.first;}};public:typedef typename RBTree<K, std::pair<K, V>, KeyOfV>::iterator iterator;std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return _t.insert(kv);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){std::pair<iterator, bool> ret = insert(std::make_pair(key, V()));return ret.first->second;}private:RBTree<K, std::pair<K,V>, KeyOfV> _t;   //红黑树};
}

代码4.2：（set的模拟实现）

namespace zhang
{template <class K>class set{struct KeyOfV{const K& operator()(const K& val){return val;}};public:typedef typename RBTree<K, K, KeyOfV>::iterator iterator;std::pair<iterator, bool> insert(const K& key){return _t.insert(key);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}K& operator[](const K& key){std::pair<iterator, bool> ret = insert(key);return *ret.first;}private:RBTree<K, K, KeyOfV> _t;   //红黑树};
}

附录：用红黑树封装map和set完整版代码

1. RBTree.h文件

#include<iostream>
#include<assert.h>//枚举常量 -- 红色、黑色
enum Color
{RED,BLACK
};//定义红黑树节点
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _date;  //数据值（set为单个值，map为键值对pair）Color _col;   //节点颜色RBTreeNode(const T& date)   //节点构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _date(date), _col(RED){ }
};//红黑树迭代器模板
template<class T, class Ref, class Ptr>
struct __RBTree_iterator_
{typedef RBTreeNode<T> Node;    //红黑树节点typedef __RBTree_iterator_<T, Ref, Ptr> Self;Node* _node;//构造函数__RBTree_iterator_(Node* node): _node(node){ }//解引用函数Ref operator*(){return _node->_date;}//成员访问操作符->重载Ptr operator->(){return &_node->_date;}bool operator==(const Self& it) const{return _node == it._node;}bool operator!=(const Self& it) const{return _node != it._node;}//++运算符重载函数Self& operator++(){if (_node->_right != nullptr){//找右子树的最左侧节点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{//找孩子节点为左孩子节点的位置，或者父亲节点为空Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_right == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}//--运算符重载函数Self& operator--(){if (_node->_left != nullptr){Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{Node* parent = _node->_parent;Node* cur = _node;while (parent && parent->_left == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}
};//红黑树类模板
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;    //类型重定义红黑树节点public:typedef __RBTree_iterator_<T, T&, T*> iterator;   //迭代器std::pair<iterator, bool> insert(const T& date){//插入第一个节点if (_root == nullptr){_root = new Node(date);_root->_col = BLACK;   //根节点为黑色return std::make_pair(_root, true);}KeyOfT kov;   //用于筛选比较数据的类对象//寻找节点插入的位置Node* parent = nullptr;   Node* cur = _root;while (cur){//如果cur节点的key值大于插入键值对的key，向左子树查找if (kov(cur->_date) > kov(date)){parent = cur;cur = cur->_left;}else if(kov(cur->_date) < kov(date))  //如果cur节点的key值小于插入键值对的key，向左子树查找{parent = cur;cur = cur->_right;}else  //相等表明节点已存在，插入失败{return std::make_pair(cur, false);}}//判断新节点是parent的左节点还是右节点，链接//默认新插入的节点为红色cur = new Node(date);Node* newNode = cur;cur->_col = RED;cur->_parent = parent;if (kov(parent->_date) > kov(date)){parent->_left = cur;}else{parent->_right = cur;}//如果parent节点不为空且为红色，那么红黑树的结构在插入节点后被破坏，需要调整while (parent && parent->_col == RED){Node* grandParent = parent->_parent;   //祖父节点assert(grandParent);assert(grandParent->_col == BLACK);   //断言检查，如果祖父节点为空或为黑色，那么红黑树结构在节点插入之前就存在问题if (parent == grandParent->_left)  //插入在祖父节点的左子树{Node* uncle = grandParent->_right;//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}	else  //情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑{if (parent->_left == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//    g//  p   u//cRotateR(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行左右双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g//  p   u//   u RotateLR(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}else  //parent == grandParent->_right{Node* uncle = grandParent->_left;  //叔叔节点//情况一：cur为红，parent为红，grandFather为黑，uncle为红if (uncle && uncle->_col == RED){//将parent节点和uncle节点变为黑，grandFather节点变为红，然后继续向上调整parent->_col = BLACK;uncle->_col = BLACK;grandParent->_col = RED;cur = grandParent;parent = cur->_parent;}else{//情况二、三：cur为红，parent为红，grandFather为黑，uncle不存在或为黑if (parent->_right == cur){//情况二 -- 进行右单旋 + 变色(parent变黑,grandFather变红)//   g// u   p//       cRotateL(grandParent);parent->_col = BLACK;grandParent->_col = RED;}else{//情况三 -- 进行右左双旋 + 变色（cur节点变为黑，grandFater节点变为红）//    g// u     p//     cRotateRL(grandParent);cur->_col = BLACK;grandParent->_col = RED;}break;}}}_root->_col = BLACK;   //根节点为黑色return std::make_pair(newNode, true);}//中序遍历函数void InOrder(){_InOrder(_root);std::cout << std::endl;}//红黑树检验函数bool IsRBTree(){//空树是合法的红黑树if (_root == nullptr){return true;}//检查根节点颜色if (_root->_col == RED){std::cout << "根节点颜色不是黑色" << std::endl;}int baseBlackNum = 0;   //基准黑色节点个数//以最左侧路径为基准，计算黑色节点个数，每条路径黑色节点数目都应该相同Node* cur = _root;while (cur){if (cur->_col == BLACK){++baseBlackNum;}cur = cur->_left;}bool blackNumTrue = PrevCheck(_root, 0, baseBlackNum);   //检查每条路径黑色节点数目是否相同bool colorTrue = CheckColor(_root);  //检查是否存在连续红色节点return blackNumTrue && colorTrue;}//获取begin()位置 -- 最左侧节点iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}private:bool CheckColor(Node* root){if (root == nullptr){return true;}//如果本节点为红色且父亲节点也为红色，证明存在连续红色节点，结构错误if (root->_col == RED && root->_parent && root->_parent->_col == RED){std::cout << "存在连续的红色节点" << std::endl;return false;}return CheckColor(root->_left) && CheckColor(root->_right);}bool PrevCheck(Node* root, int blackNum, int baseBlackNum){if (root == nullptr){if (blackNum != baseBlackNum){std::cout << "每条路径上黑色节点的数目不同" << std::endl;return false;}else{return true;}}if (root->_col == BLACK){++blackNum;}return PrevCheck(root->_left, blackNum, baseBlackNum)&& PrevCheck(root->_right, blackNum, baseBlackNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << " ";_InOrder(root->_right);}void RotateR(Node* parent)   //右单旋函数{Node* pNode = parent->_parent;    Node* pL = parent->_left;   //左子节点Node* pLR = pL->_right;   //左子节点的右子节点//将pLR节点托管给parent节点的左子节点parent->_left = pLR;if (pLR != nullptr){pLR->_parent = parent;}//将父亲节点托管给pL节点的右子节点pL->_right = parent;  parent->_parent = pL;//此时这颗进行旋转的子树的根节点变为了pL，pL要与pNode节点连接if (parent == _root){_root = pL;pL->_parent = nullptr;}else{pL->_parent = pNode;if (pNode->_left == parent){pNode->_left = pL;}else{pNode->_right = pL;}}}void RotateL(Node* parent)   //左单旋函数{Node* pNode = parent->_parent;Node* pR = parent->_right;    //右子节点Node* pRL = pR->_left;   //右子节点的左子节点//将pLR节点托管给parent节点的右子节点parent->_right = pRL;if (pRL != nullptr){pRL->_parent = parent;}//将parent节点托管给pR的左子节点pR->_left = parent;parent->_parent = pR;if (_root == parent){_root = pR;_root->_parent = nullptr;}else{pR->_parent = pNode;if (pNode->_left == parent){pNode->_left = pR;}else{pNode->_right = pR;}}}void RotateLR(Node* parent)  //左右双旋函数{RotateL(parent->_left);RotateR(parent);}void RotateRL(Node* parent)  //右左双旋函数{RotateR(parent->_right);RotateL(parent);}private:Node* _root = nullptr;
};

2. map.h文件

#include "RBTree.h"namespace zhang
{template <class K, class V>class map{struct KeyOfV{const K& operator()(const std::pair<K,V>& val){return val.first;}};public:typedef typename RBTree<K, std::pair<K, V>, KeyOfV>::iterator iterator;std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return _t.insert(kv);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){std::pair<iterator, bool> ret = insert(std::make_pair(key, V()));return ret.first->second;}private:RBTree<K, std::pair<K,V>, KeyOfV> _t;   //红黑树};
}

3. set.h文件

namespace zhang
{template <class K>class set{struct KeyOfV{const K& operator()(const K& val){return val;}};public:typedef typename RBTree<K, K, KeyOfV>::iterator iterator;std::pair<iterator, bool> insert(const K& key){return _t.insert(key);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}K& operator[](const K& key){std::pair<iterator, bool> ret = insert(key);return *ret.first;}private:RBTree<K, K, KeyOfV> _t;   //红黑树};
}