C++ 红黑树封装map和set

前言

1.红黑树的改造

1.1主题框架

1.2迭代器

operator++ （）

begin（）和end（）

1.3红黑树相关接口的改造

Find函数的改造

Insert 函数的改造

2.红黑树改造的完整代码

3.Set的封装

4.Map的封装

前言

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

在改造红黑树的时候，我们将会面对几个问题。

对红黑树的改造，关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是set的话，则是K，如果是map，则为pair<k,v>。如何用一个节点结构控制两种类型，使用类模板参数T
在插入的过程中，因为是泛型编程，需要用红黑树给map和set套一个“壳子”，在比较大小的过程中，pair的比较是通过first和second共同决定的，因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key数据
关于 key 的修改问题。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。这个问题需要单独处理。
红黑树相关接口的改造。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。

1.红黑树的改造

1.1主题框架

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

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

红黑树的结点构造

using namespace std;
enum color
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* left;RBTreeNode<T>* right;RBTreeNode<T>* _parent;T data;color col;RBTreeNode(const T& data):left(nullptr), right(nullptr), _parent(nullptr), data(data), col(RED){}
};

主体框架

class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T, T&, T*> iterator; //迭代器typedef __TreeIterator<T, const T&, const T*> const_iterator; //const迭代器.......//相应的接口
private:	Node* root = nullptr;
};

1.2迭代器

template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}Self& operator++(){if (_node->right){// 下一个就是右子树的最左节点Node* cur = _node->right;while (cur->left){cur = cur->left;}_node = cur;}else{// 左子树 根 右子树// 右为空，找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

operator++ （）

这里需要重点提的是operator++

它与以往的容器不相同，这是通过二叉树构建，根据它的中序遍历实现++

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

1.当前节点的右子树不为空

当结点是it的时候，说明左子树已经全部访问完了，开始访问右子树，右子树不为空，我们下一个访问的节点是15，所以要找到右子树的最左节点。

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

当it为该节点时，右子树为空，访问的下一个节点时8，因为it被访问完时，代表着根节点已经访问完了，要找祖先作为祖先父亲的左节点即可。

begin（）和end（）

iterator begin()
{Node* cur = root;while (cur&&cur->left){cur = cur->left;}return iterator(cur);
}
iterator end()
{return iterator(nullptr);
}
const_iterator begin()const
{Node* cur = root;while (cur&&cur->left){cur = cur->left;}return const_iterator(cur);
}
const_iterator end()const
{	return const_iterator(nullptr);
}

1.3红黑树相关接口的改造

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();
}

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;//此处省略变色+旋转部分的代码……

剩下的变色或旋转代码上一篇讲到过

红黑树

2.红黑树改造的完整代码

#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;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* grandparent = parent->_parent;if (parent == grandparent->left){Node* uncle = grandparent->right;if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;if (grandparent == root){grandparent->col = BLACK;return make_pair(root, true);}else{grandparent->col = RED;cur = grandparent;parent = cur->_parent;}}else{if (cur = parent->left){RotateR(grandparent);parent->col = RED;grandparent->col = BLACK;}else{RotateL(parent);RotateR(grandparent);cur->col = BLACK;grandparent->col = RED;}break;}}else//parent=grandparent->right{Node* uncle = grandparent->left;if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;if (grandparent == root){grandparent->col = BLACK;return make_pair(root, true);}else{grandparent->col = RED;cur = grandparent;parent = cur->_parent;}}else{if (cur == parent->right){RotateL(grandparent);parent->col = BLACK;grandparent->col = RED;}else{RotateR(parent);RotateL(grandparent);cur->col = BLACK;grandparent->col = RED;}break;}}}}root->col = BLACK;return make_pair(newnode, true);
}private:void RotateL(Node* parent)
{Node* subR = parent->right;Node* subRL = subR->left;subR->left = parent;parent->right = subRL;if (subRL){subRL->_parent = parent;}Node* parentParent = parent->_parent;parent->_parent = subR;if (parent == root){root = subR;subR->_parent = nullptr;}else{if (parentParent->left == parent){parentParent->left = subR;}else{parentParent->right = subR;}subR->_parent = parentParent;}}
void RotateR(Node* parent)
{Node* subL = parent->left;Node* subLR = parent->right;parent->left = subLR;subL->right = parent;if (subLR){subLR->_parent = parent;}Node* parentParent = parent->_parent;parent->_parent = subL;if (root == parent){root = subL;subL->_parent = nullptr;}else{if (parentParent->left == parent){parentParent->left = subL;}else{parentParent->right = subL;}subL->_parent = parentParent;}
}    Node* _root = nullptr;};

3.Set的封装

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

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

namespace bit
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
}
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);
}

4.Map的封装

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