进阶数据结构：用红黑树实现封装map和set
嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的
passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let’s go！
我的博客：yuanManGan
我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记 闲言碎语小记坊
进阶数据结构 走进Linux的世界 题山采玉 领略算法真谛
用红黑树实现封装map和set
实现步骤：
- 实现红黑树
- 封装 map 和 set 框架解决KeyOfT
- iterator
- const_iterator
- key不支持修改的问题
- operator[ ]
1.实现红黑树
上集我们已经实现了一个普通的红黑树 进阶数据结构：红黑树，
2.封装 map 和 set 框架解决KeyOfT
查看stl源码借鉴了解
发现实现 set 和 map 都包含了一个 tree 头文件，我们那篇博客实现的 key-value 的红黑树，那我们是不是要实现两个红黑树一个是 key 的一个 key-value 的呢？
不急我们看看源码：
template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc = allocator<_Val> >class _Rb_tree{}
我们凑凑这模板，这怎么又有key又有value那它怎么实现的set , set 不是不要value吗？
我来解释一下吧：
- 可能写这个代码的程序员写的不太规范，这个地方的Val代表的不是我们之前写代码的value。
- 而是比如我们set传入的key，map传入的key_value,代表的是这一类，而不是单纯的value
- 我们就这样形成了模板，本质上编译器还是写了两份代码，但增加了复用，减少了我们自己写。
那又有人问了，那我们不是只要一个模板参数就够了吗，为什么前面还得加个key呢？
- 我们实现 find 等功能的时候需要使用到 key，所以不能偷懒
更改我们的红黑树
我们写就写的规范一点，我们将 V 替换为 T
//原本
////////////////////////////////////////////////////////////////
template <class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr) // 按声明顺序放在_col之前, _col(RED){}
};
template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://...
private:Node* _root = nullptr;
};
////////////////////////////////////////////////////////////////
//修改后
template <class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _parent;RBTreeNode<V>* _left;RBTreeNode<V>* _right;Colour _col;RBTreeNode(T& data): _data(data), _parent(nullptr), _left(nullptr), _right(nullptr) // 按声明顺序放在_col之前, _col(RED){}
};
template <class K, class T>
class RBTree
{typedef RBTreeNode<K, T> Node;
public://...
private:Node* _root = nullptr;
};
我们在修改 Insert 这个函数的时候就遇到的问题，我们怎么比较插入节点与原节点的大小呢？
- 我们可以引入一个模板参数 KeyOfT 分别在 set和 map头文件里面重载 ( ) 实现比较逻辑，如果是set就直接返回 key ，map就返回kv中的 first。
//set.h
template<class K>
class set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public://...
private:RBTree<K, K, SetKeyOfT> _t;
};
//map.h
template<class K, class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public://...
private:RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
insert
KeyOfT kot;
bool Insert(const T& data)
{//插入//空树if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else {return false;}}cur = new Node(data);cur->_col = RED;if (kot(data) > kot(parent->_data)){//是p的右子树parent->_right = cur;}else{//是p的左子树parent->_left = cur;}cur->_parent = parent;//变色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//u存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{//u存在但为黑if (cur == parent->_left){//c在左// g p // p u ---> c g// c uRotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//c在右// g RotateL(p) g RotateR(g) c// p u -----------> c u --------> p g// c p u RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//u存在且为红if (uncle && uncle->_col == RED){//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{//u存在但为黑if (cur == parent->_right){//c在右// g p // u p ---> g c// c uRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//c在z左// g RotateR(p) g RotateL(g) c// u p -----------> u c --------> g p// c p u RotateR(parent);RotateL