【C++】：红黑树的应用 --- 封装map和set

点击跳转至文章：【C++】：红黑树深度剖析 — 手撕红黑树！

前言

map 和 set 的底层本质上还是复用，通过对红黑树的改造，再分别套上一层 map 和 set 的 “壳子”，以达到 “一树二用” 的目的。

在改造红黑树的过程中，我大概归纳了以下几个需要重点解决的问题：

(1) 对红黑树节点的改造。关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是 set 则是 K，如果是map，则为pair<K, V>。如何用一个节点结构控制两种类型，使用类模板参数T。

(2) 在插入操作时，如何完成数据的比较。由于我们的节点类型的泛型，如果是 set 则是 K，如果是map，则为pair<K, V>，而pair的比较是由 first 和 second 共同决定的，这显然不符合要求。因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key 数据。

(3) 在红黑树中实现普通迭代器和const迭代器，再套上 “壳子”。

(4) 关于 key 的修改问题。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。这个问题需要单独处理。

(5) 红黑树相关接口的改造。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。

说明：如果大家要自己动手实现封装，可以按照上面五个问题的流程进行实现。但是在本篇文章中由于展示等的原因，无法按照上面的步骤。

一，红黑树的改造

1. 红黑树的主体框架

(1) K 是给find，erase用的，T 是给节点，insert用的；

(2) KeyOfT 是由于下面需要比较，但是比较时不知道T的类型， set是key类型的比较，map是pair类型的比较，要统一变成key的比较。

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*> ConstIterator; //const 迭代器//其他功能的实现……private:Node* _root = nullptr;
};

2. 对红黑树节点结构的改造

//枚举颜色
enum Colour
{RED,BLACK
};//节点类
template <class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;//pair<K, V> _kv;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(BLACK){}
};

3. 红黑树的迭代器

3.1 迭代器类

//迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}bool operator!=(const Self& s){return s._node != _node;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//从局部的某一个过程考虑Self& operator++(){if (_node->_right){//右不为空，右子树的最左节点就是下一个访问的节点Node* leftMost = _node->_right;while (leftMost->_left)leftMost = leftMost->_left;_node = leftMost;}else{//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点Node* cur = _node;Node* parent = cur->_parent;//循环找祖先while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};

迭代器中最复杂的就是 operator++()的实现，它与原先的 vector/list 不同，红黑树的迭代器是要完成二叉树的中序遍历。

为了完成二叉树的中序遍历，我们需要从局部的某一过程考虑，就是假设 it 已经走到了某一节点，要找到下一个访问的节点，分为两种情况：

(1) 当前节点的右子树不为空：

如下图，假设 it 已经到达了13节点，说明此时13的左子树已经访问完了，右子树不为空，下一个要访问的节点就是右子树的最左节点15

(2) 当前节点的右子树为空：

如下图，假设 it 此时到达了15节点，它的右子树为空，下一个访问哪个节点呢？有些人单纯的认为是15的父亲17，其实是错误的。

那假设 it 到达6节点上呢，6的右为空，但是根据中序遍历的顺序，6的父亲1已经访问过了。

其实此时是要找当前节点的祖先，父亲也是祖先之一。

右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先，是哪个祖先呢？沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点。

(a) 假设此时走到了15节点，下一个访问的节点是17，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点；

(b) 假设此时走到了6节点，下一个访问的节点是8，但是此时 cur 是 parent 的右，不满足条件，继续向上查找，cur = parent，parent = parent->_parent，这时 cur 在1，parent 在8，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点

3.2 Begin() 和 End()

//中序遍历，找树的最左节点
Iterator Begin()
{//Node* cur = _root;Node* leftMost = _root;while (leftMost->_left)leftMost = leftMost->_left;return Iterator(leftMost);
}Iterator End()
{return Iterator(nullptr);
}ConstIterator Begin()const
{//Node* cur = _root;Node* leftMost = _root;while (leftMost->_left)leftMost = leftMost->_left;return ConstIterator(leftMost);
}ConstIterator End()const
{return ConstIterator(nullptr);
}Iterator Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_data > key)cur = cur->_left;else if (cur->_data < key)cur = cur->_right;elsereturn Iterator(cur);}return End();
}

四，红黑树相关接口的改造

4.1 Find 函数的改造

查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。

Iterator Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_data > key)cur = cur->_left;else if (cur->_data < key)cur = cur->_right;elsereturn Iterator(cur);}return End();
}

4.2 Insert 函数的改造

map 里的 operator[] 需要依赖 Insert 的返回值

pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);return make_pair(Iterator(_root), true);}KeyOfT kot;Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}elsereturn make_pair(Iterator(cur), false);}cur = new Node(data);Node* newnode = cur;//此处省略变色+旋转部分的代码……

五，红黑树改造的完整代码

说明：由于代码太长，影响展示效果，所以插入部分的 变色+旋转 的代码此处省略，和红黑树的基本一模一样，请前往【C++】：红黑树深度剖析 — 手撕红黑树！

RBTree.h

#include <iostream>
#include <assert.h>
using namespace std;//枚举颜色
enum Colour
{RED,BLACK
};//节点类
template <class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;//pair<K, V> _kv;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(BLACK){}
};//迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}bool operator!=(const Self& s){return s._node != _node;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//从局部的某一个过程考虑Self& operator++(){if (_node->_right){//右不为空，右子树的最左节点就是下一个访问的节点Node* leftMost = _node->_right;while (leftMost->_left)leftMost = leftMost->_left;_node = leftMost;}else{//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点Node* cur = _node;Node* parent = cur->_parent;//循环找祖先while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};//K 是给find，erase用的，T 是给节点，插入用的
// KeyOfT 是由于下面需要比较，但是比较时不知道T的类型，
// set是key类型的比较，map是pair类型的比较，要统一变成key的比较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*> ConstIterator;//中序遍历，找树的最左节点Iterator Begin(){//Node* cur = _root;Node* leftMost = _root;while (leftMost->_left)leftMost = leftMost->_left;return Iterator(leftMost);}Iterator End(){return Iterator(nullptr);}ConstIterator Begin()const{//Node* cur = _root;Node* leftMost = _root;while (leftMost->_left)leftMost = leftMost->_left;return ConstIterator(leftMost);}ConstIterator End()const{return ConstIterator(nullptr);}Iterator Find(const K& key){Node* cur = _root;while (cur){if (cur->_data > key)cur = cur->_left;else if (cur->_data < key)cur = cur->_right;elsereturn Iterator(cur);}return End();}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);return make_pair(Iterator(_root), true);}KeyOfT kot;Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}elsereturn make_pair(Iterator(cur), false);}cur = new Node(data);Node* newnode = cur;//新增节点，颜色为红色cur->_col = RED;//此处省略变色+旋转部分的代码……private:Node* _root = nullptr;};

六，set 的封装实现

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。

为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可。

MySet.h

#include "RBTree.h"namespace cc
{template<class K>class set{// 获取 set 里面的 keystruct SetOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetOfT>::ConstIterator 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 K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetOfT> _t;};
}//使用 const 迭代器 
void Print(const cc::set<int>& s)
{auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;
}//测试代码
void Test_set()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 16,3,7,11,9,26,18,14,15 };cc::set<int> s;for (auto e : a)s.insert(e);for (auto e : s)cout << e << " ";cout << endl;Print(s);
}

七，map 的封装实现

map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可。

map 中 pair 的 first 不能修改，second 可以修改，在 pair 的第一个参数前加 const 即可。

MyMap.h

#include "RBTree.h"namespace cc
{template<class K, class V>class map{//获取 pair 中的 keystruct MapOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapOfT>::ConstIterator 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<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}//给一个key，返回value的引用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>, MapOfT> _t;};
}//测试代码
void Test_map()
{cc::map<string, string> dict;dict.insert({ "left","左边" });dict.insert({ "right","右边" });dict.insert({ "insert","插入" });dict["left"] = "剩余，左边";cc::map<string, string>::iterator it = dict.begin();while (it != dict.end()){//it->first += 'x'; //errit->second += 'y'; //okcout << it->first << ":" << it->second << endl;++it;}cout << endl;
}