红黑树封装map和set

红黑树封装map和set

1. 改良红黑树

如何改良，可以参考stl源码

我们先看库中,map和set的大框架, 发现set在底层红黑树存储的是<k,k>的键值对，不像我们平时认知以为只存储一个k，map在底层红黑树存储的是<k,v>的键值对。继续看库中红黑树的源码

发现在红黑树节点这里并不是我们之前实现的K, V形式，而是只给了一个Value形式。

对于set第二个模板参数是K，其节点中存储的就是K，这里的Value就代表的是K;

对于map第二个模板参数是pair<const K，V>，其节点中存储的就是pair<const K，V>，这里的Value就代表的是pair<const K，V>;

那么在红黑树模板参数设计时，为什么要多设计一个Key的模板参数呢? 是为了拿到单独的K类型，find和erase这些接口函数的参数是K；第二个模板参数才真正决定节点里面存储什么

1.1 改良后的节点

template<class T>
struct RBTreeNode	//三叉链
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)       //默认颜色给红色{}
};

1.2 改良后的类

分别添加仿函数

插入和查找的过程中的比较不能想红黑树一样实现成kv.first的形式，我们要实现成用节点中实际存储的类型去比较，对于set存储的是K，可以直接去比较；对于map存储的是pair，比较时是用pair比较，但是pair的比较并不是我们想要的，我们还是想要pair中的K比较

上面的问题我们可以看库中源码，发现多给了一个模板参数KeyOfValue，其目的是取出K，可以分别给具体的仿函数来实现。

set这里直接返回key就行

struct SetKeyOfT
{const K &operator()(const K &key){return key;}
};

map这里需要返回pair的first, 即K

struct MapKeyOfT
{const K &operator()(const pair<const K, V> &kv){return kv.first;}
};

那么为什么需要这么做，对于set来说直接比较不就行了吗，当然可以，但是map并不是直接用_data类型比较(即pair本身), set为了和map复用同一棵红黑树，所以要实现成这种形式

同样我们插入和查找时也需要修改，用map和set传过来的仿函数定义出一个对象kot，帮助我们取出帮助我们取出_data中的Key。

代码

template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:~RBTree(){_Destroy(_root);_root = nullptr;}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;		//仿函数定义出对象，帮助我们取出_data中的Keywhile (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) >key){cur = cur->_left;}else{return cur;      }}return nullptr;}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);Node* newnode = cur;      //cur可能会变色, 需要提前记录curif (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//处理红黑树颜色while (parent && parent->_col==RED){Node* grandfather = parent->_parent;//找叔叔  =>  看父亲在祖父的哪边if (grandfather->_left == parent)   {Node* uncle = grandfather->_right;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur=grandfather;parent = cur->_parent;}else    //情况2+3: u不存在/u存在且为黑, 旋转 + 变色{//     g//   p   u// cif(cur==parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else    //(grandfather->_right == parent){Node* uncle = grandfather->_left;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else      //情况2+3: u不存在/u存在且为黑, 旋转 + 变色{//     g//   u   p//         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u   p//     cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;   //根节点是黑色的return true;}
private:Node* _root = nullptr;
};	

3. 封装map和set

3.1 set

namespace yj
{template<class K>class set{//作用是：将T中的key提取出来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;};
}

3.2 map

namespace yj
{template<class K, class V>class map{//作用是：将T中的key提取出来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;};
}

3. 迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：

3.1 begin 和 end

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，STL是将end()放在头结点的位置：我们上次设计的RBTree没有头结点这个结构，因此我们也就不与STL的实现方式完全一样，end()就直接设置为nullptr。

iterator begin() // 中序遍历第一个
{Node *cur = _root;while (cur && cur->_left)   //找最左侧节点{cur = cur->_left;}return iterator(cur); // 节点指针构造的迭代器
}iterator end() // 最后一个节点的下一个
{return iterator(nullptr);
}

3.2 operator++()和operator–()

++的实现思路:

1. 右不为空, 下一个就是右子树的最左节点

2. 右为空, 沿着到根的路径, 找孩子是父亲左的那个祖先

Self &operator++()
{if (_node->_right){// 1. 右不为空, 下一个就是右子树的最左节点Node *subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft; // 将节点的地址赋值即可}else{// 2. 右为空, 沿着到根的路径, 找孩子是父亲左的那个祖先Node *cur = _node;Node *parent = _node->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

–的实现思路: 与++相反

1. 左不为空, 下一个就是左子树的最右节点

2. 左为空, 沿着到根的路径, 找孩子是父亲右的那个祖先

Self &operator--()
{if (_node->_left){// 1. 左不为空, 下一个就是左子树的最右节点Node *subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight; // 将节点的地址赋值即可}else{// 2. 左为空, 沿着到根的路径, 找孩子是父亲右的那个祖先Node *cur = _node;Node *parent = _node->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

3.3 const迭代器

如果是const迭代器，那可以在迭代器类中多加上两个模板参数：T&, T*偏特化，当然实际上是Ref，Ptr的全特化；

那如何实现set的const迭代器呢？由于set不能修改普通迭代器就是const迭代器，const迭代器还是const迭代器；

对于map来说普通迭代器就是普通迭代器，const迭代器就是const迭代器，但是map的pair中的value是可以修改的，因此我们就需要在RBTree中把普通迭代器和const迭代器均实现出来，同时也要支持从普通迭代器 隐式类型转换 成构造const迭代器的构造函数。，当map的迭代器类模板被实例化成普通迭代器时，它就是拷贝构造；迭代器类模板被实例化成const迭代器时，它是一个支持用普通迭代器构造初始化const迭代器的构造函数。

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){}// 1. typedef _RBTreeIterator<T, T&, T*> iterator;  拷贝构造//// 支持普通迭代器构造const迭代器的构造函数// 2. typedef _RBTreeIterator<T, const T&, const T*> const_iterator;// 支持从普通迭代器 隐式类型转换 成构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIterator<T, T &, T *> &it): _node(it._node){}
}

set的迭代器

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::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();
}

map的迭代器

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

4. map的operator[]的重载

根据map的[]性质: 返回make_pair<iterator,bool>的first，解引用找到节点value, 借助Insert函数，同时需要将我们插入函数返回类型的从bool变成pair类型

V& operator[](const K &key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));   //V()构造一个匿名对象return ret.first->second; // 找到ret（make_pair<iterator,bool>）的first，解引用找到节点value
}

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; // cur可能会变色, 需要提前记录curif (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 处理红黑树颜色while (parent && parent->_col == RED){Node *grandfather = parent->_parent;// 找叔叔  =>  看父亲在祖父的哪边if (grandfather->_left == parent){Node *uncle = grandfather->_right;// 3种情况// 情况1: u存在且为红, 变色处理, 并继续向上处理// 变色: p,u变黑, g变红if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3: u不存在/u存在且为黑, 旋转 + 变色{//     g//   p   u// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else //(grandfather->_right == parent){Node *uncle = grandfather->_left;// 3种情况// 情况1: u存在且为红, 变色处理, 并继续向上处理// 变色: p,u变黑, g变红if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3: u不存在/u存在且为黑, 旋转 + 变色{//     g//   u   p//         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u   p//     cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK; // 根节点是黑色的return make_pair(iterator(newnode), true);
}

5. 完整代码实现

5.1 RBTree.h

#include<iostream>
#include<utility>
#include<assert.h>
#include<stdlib.h>
using namespace std;//节点的颜色
enum Colour
{RED,BLACK,
};template<class T>
struct RBTreeNode	//三叉链
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)       //默认颜色给红色{}
};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){}// 1. typedef _RBTreeIterator<T, T&, T*> iterator;  拷贝构造// // 支持普通迭代器构造const迭代器的构造函数// 2. typedef _RBTreeIterator<T, const T&, const T*> const_iterator;  //支持从普通迭代器 隐式类型转换 成构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIterator<T, T&, T*>&it):_node(it._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_right){//1. 右不为空, 下一个就是右子树的最左节点Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;     //将节点的地址赋值即可}else{//2. 右为空, 沿着到根的路径, 找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = _node->_parent;while (parent && cur==parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){//1. 左不为空, 下一个就是左子树的最右节点Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;     //将节点的地址赋值即可}else{//2. 左为空, 沿着到根的路径, 找孩子是父亲右的那个祖先Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};//仿函数
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:~RBTree(){_Destroy(_root);_root = nullptr;}typedef _RBTreeIterator<T, T&, T*> iterator;typedef _RBTreeIterator<T, const T&, const T*> const_iterator;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);}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;			//仿函数定义出对象，帮助我们取出_data中的Keywhile (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) >key){cur = cur->_left;}else{return cur;      }}return 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;      //cur可能会变色, 需要提前记录curif (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//处理红黑树颜色while (parent && parent->_col==RED){Node* grandfather = parent->_parent;//找叔叔  =>  看父亲在祖父的哪边if (grandfather->_left == parent)   {Node* uncle = grandfather->_right;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur=grandfather;parent = cur->_parent;}else    //情况2+3: u不存在/u存在且为黑, 旋转 + 变色{//     g//   p   u// cif(cur==parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else    //(grandfather->_right == parent){Node* uncle = grandfather->_left;//3种情况//情况1: u存在且为红, 变色处理, 并继续向上处理//变色: p,u变黑, g变红if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续向上调整cur = grandfather;parent = cur->_parent;}else      //情况2+3: u不存在/u存在且为黑, 旋转 + 变色{//     g//   u   p//         cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u   p//     cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;   //根节点是黑色的return make_pair(iterator(newnode), true);}void Inorder(){_Inorder(_root);}int Height(){return _Height(_root);}bool IsBalance()    //重点检查规则{//先检查根节点if (_root && _root->_col == RED){cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;       //基准值Node* cur = _root;while(cur)               //走最左路径{if (cur->_col == BLACK)++benchmark;cur = cur->_left;}//连续红色节点return _Check(_root, 0,benchmark);}private://左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppnode == nullptr)				//parent本身就是根{_root = subR;_root->_parent = nullptr;}else								//parent只是一棵子树{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;}}int _Height(Node* root){if (root == nullptr)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}bool _Check(Node* root, int blackNum, int benchmark)  //基准值{if (root == nullptr){if (benchmark != blackNum){cout << "某条路径黑色节点的数量不相等" << endl;return false;}return true;}//DFS检查黑色节点数量if (root->_col == BLACK){++blackNum;}//反向检查  ---> 红色节点不能连续if (root->_col == RED&& root->_parent&& root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _Check(root->_left,  blackNum,  benchmark)&& _Check(root->_right, blackNum,  benchmark);}void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);}Node* _root = nullptr;
};

5.2 set.h

#include"RBTree.h"namespace yj
{template<class K>class set{//作用是：将T中的key提取出来struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool>  insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
}

5.3 map.h

#include"RBTree.h"namespace yj
{template<class K, class V>class map{//作用是：将T中的key提取出来struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public://取类模板的内嵌类型前需要添加typename, 因为编译器无法区分取到的是内嵌类型还是静态变量//加typename告诉编译器这是类模板的内嵌类型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();}V& operator[](const K& key){pair<iterator,bool> ret= _t.Insert(make_pair(key, V()));return ret.first->second; //找到ret（make_pair<iterator,bool>）的first，解引用找到节点value}pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}