嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的
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 u
RotateR(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 u
RotateL(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