我们前面实现了红黑树的插入以及删除（删除有一点**bug**），因此我们就能用其来实现 map 以及 set，这里只涉及了之前红黑树的插入，因为我们的重点是 map 与 set 是如何同时使用红黑树实现的以及红黑树的迭代器是如何实现的！
Ⅱ. 对红黑树模板参数的改造
一起回忆一下，之前红黑树的参数模板我们是这样子实现的：
enum Color
{
BLACK,
RED
};
template <class K, class V>
struct RBTreeNode
{
RBTreeNode(const pair<K, V>& kv, Color col = RED)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(col)
{}
RBTreeNode<K, V>* _left; // 节点的左孩子
RBTreeNode<K, V>* _right; // 节点的右孩子
RBTreeNode<K, V>* _parent; // 节点的双亲（红黑树需要旋转，为了实现简单给出该字段）
pair<K, V> _kv; // 节点的键值对
Color _col; // 节点的颜色
};
template <class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//.....
private:
Node* _root;
}; 有没有发现，我们实现的时候默认用的就是**<K, V>** 结构，也就是 map 的结构，但是 set 呢？重写一个红黑树把结构变成**<K, K>**？这样子就造成了数据冗余了！因为其实我们是可以去复用的，我们去 STL 中看看是怎么实现的！
很妙是吧，STL 中的红黑树的 Value 其实接收的 map 和 set 里面分别传过来的数据类型，如果是 set 的 Value 就是 Key，而如果是 map 则 Value 就是 pair<const Key, T> ！这就达到了一棵红黑树就可以封装 map 和 set 啦！
但是很快新的问题就来了！
还记得我们实现红黑树的 Insert 吗，如下：
bool Insert(const T& data)
{
// .......
while (cur)
{
if (cur->_data > data) // 这里对比的时候如果是map，因为map的_data是pair类型，无法直接对比
{
parent = cur;
cur = cur->_left;
}
else if (cur->_data < data)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
// .......
} 可以发现我们之前写的红黑树的插入好像走不通了，因为这里的 data 的类型是 T，但是编译器不知道什么时候传的是 set 的数据类型还是 map 的数据类型，这就导致了在比较的时候出错，那该咋办呀？
我们再去 STL 中瞅一瞅哈哈哈！
可以看出，STL 中是通过传递仿函数来实现 map 和 set 的不同数据类型的通用比较。
通俗的讲，就是如果是 set，就用 set 的比较器比较；如果是 map，就用 map 的比较器比较！
// set的比较器仿函数
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
// map的比较器仿函数
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
}; 然后接下来我们对红黑树的插入进行一些修改:
private:
KeyOfT _kt; // 仿函数对象，这个也可以定义在函数里面
public:
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
// 寻找要插入的位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (_kt(cur->_data) > _kt(data)) // 将他们的key分别提取出来
{
parent = cur;
cur = cur->_left;
}
else if (_kt(cur->_data) < _kt(data)) // 将他们的key分别提取出来
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), false);
}
}
// 插入新节点并将新节点的颜色设为红色
// ......
if (_kt(parent->_data) > _kt(data)) // 将他们的key分别提取出来
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 控制平衡
// ......
return make_pair(iterator(newnode), true);
} But.......好像还有一个问题，STL 库中实现的 insert 返回的值是 pair<iterator, bool>，但是我们红黑树还没有实现迭代器呀，所以我们下面就得好好来讲一下红黑树的迭代器！
一、红黑树的迭代器
迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以下问题：
-
begin()** 与 **end()
我们先来参考一下
STL中是如何定义begin和end的：
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点 ( 最左侧节点 ) 的位置，end()放在最大节点 ( 最右侧节点 ) 的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为 对end()位置的迭代器进行一一操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置。 但是我们在模拟实现的时候做了简化，也就是让end指向nullptr，但其实这是有缺陷的！template <class K, class T, class KeyOfT> class RBTree { public: typedef TreeIterator<T, T&, T*> iterator; // 为了通过复用实现const版本，这里传三个模板参数给迭代器 typedef TreeIterator<T, const T&, const T*> const_iterator; public: iterator begin() { Node* cur = _root; while (cur && cur->_left) // 找到最左节点 { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); // 以nullptr作为end } }🌵 除此之外，这里还有一个重点：回忆一下实现
list的迭代器的时候，为了能够复用的去实现const版本的迭代器，我们这里传三个模板参数给迭代器，当我们需要const的迭代器的时候，只需要将模板参数改为const即可！详细的参考list中的实现！ -
operator++()** 与 operator--() 有了
begin()和end()之后我们就可以来构造我们的迭代器了，那么其实红黑树的迭代器最重要的就是两个：operator++** 和operator--（注意由于我们自己实现的end是指向nullptr的，所以实现细节会有点不一样）
-
对于
operator++()：- 如果目前节点存在右子树，则让
cur移动到右子树的最左节点 - 如果目前节点不存在右子树，说明该节点已经访问完毕，则向上寻找节点不是祖先节点的右子树的那个节点（直到走到空或者找到该节点为止）
- 如果目前节点存在右子树，则让
-
对于
operator--()：- 如果目前节点存在左子树，则让
cur移动到左子树的最右节点 - 如果目前节点不存在左子树，说明该节点已经访问完毕，则向上寻找节点不是祖先节点的左子树的那个节点（直到走到空或者找到该节点为止）
Self& operator++() { // 若右子树不为空，则去访问右子树中序的那个，即右子树的最左节点 if (_node->_right != nullptr) { Node* cur = _node->_right; while (cur->_left) cur = cur->_left; _node = cur; } else // 若右子树为空，说明_node节点已经访问完了，则向上查找为祖先的左的节点 { Node* cur = _node; Node* parent = _node->_parent; while (parent && parent->_right == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } Self operator++(int) // 后置++ { Self tmp = *this; this->operator++(); // 这里不能直接这样调用++_node return tmp; } Self& operator--() { // 若左子树不为空，则去访问左子树中序的那个，即左子树的最右节点 if (_node->_left != nullptr) { Node* cur = _node->_left; while (cur->_right) cur = cur->_right; _node = cur; } else // 若左子树为空，说明_node节点已经访问完了，则向上查找为祖先的右的节点 { Node* cur = _node; Node* parent = cur->_parent; while (parent && parent->_left == cur) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } Self operator--(int) // 后置-- { Self tmp(*this); this->operator--(); return tmp; } - 如果目前节点存在左子树，则让
-
至此我们就将红黑树的迭代器最重要的部分讲完啦，我们将其他部分也实现出来，等会顺便适配一下反向迭代器！
🐛 迭代器的完整代码：
template <class T, class Ref, class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, Ref, Ptr> Self;
// 给反向迭代器中用的
typedef Ref Ref;
typedef Ptr Ptr;
TreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
Self& operator++();
Self operator++(int);
Self& operator--();
Self operator--(int);
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Node* _node;
};🔺 注意： 这里大部分其实和实现 list 迭代器是一样的，所以详细的可以参考 list 的迭代器！
二、红黑树的反向迭代器
有了正向迭代器，我们就可以给红黑树适配出一个反向迭代器啦！
🏗 事实上，我们只要有了一个统一写法的反向迭代器，只要我们存在一个正向迭代器，那么它的反向迭代器就自然出来了！通俗的说，反向迭代器是适配器！
🚗 但是值得注意的是当我们在反向迭代器中去取迭代器中的模板类型如 Ref 的时候，需要加 typename 声明一下该模板类型，代表它是存在的，因为如果不在 typename，此时正向迭代器其实还没实例化，所以我们没法从中取出其模板类型。（具体也可以参考 list 的反向迭代器中的讲解）
// 反向迭代器--迭代器适配器
// 放在"Iterator.h"
template <class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self;
// 要用typename去取iterator中的类型
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
ReverseIterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return _it.operator->();
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(_it);
++_it;
return tmp;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
bool operator==(const Self& s) const
{
return _it == s._it;
}
Iterator _it;
};三、改造完后的红黑树整体框架
#include "Iterator.h" // 反向迭代器的头文件
enum Color
{
BLACK,
RED
};
template <class T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
RBTreeNode<T>* _left; // 节点的左孩子
RBTreeNode<T>* _right; // 节点的右孩子
RBTreeNode<T>* _parent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
T _data; // 节点的值域
Color _col; // 节点的颜色
};
template <class T, class Ref, class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, Ref, Ptr> Self;
// 给反向迭代器中用的
typedef Ref Ref;
typedef Ptr Ptr;
TreeIterator(Node* node)
:_node(node)
{}
Ref operator*();
Ptr operator->();
Self& operator++();
Self operator++(int);
Self& operator--();
Self operator--(int);
bool operator!=(const Self& s) const;
bool operator==(const Self& s) const;
Node* _node;
};
template <class K, class T, class KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, T&, T*> iterator;
typedef TreeIterator<T, const T&, const T*> const_iterator;
typedef ReverseIterator<iterator> reverse_iterator;
// typedef ReverseIterator<const_iterator> const_reverse_iterator; 可以有的，但是这里就不写了
public:
RBTree()
:_root(nullptr)
{}
// 拷贝构造
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = Copy(t._root);
}
// 赋值重载
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
{
swap(t._root, _root);
return *this;
}
~RBTree()
{
Destory(_root);
_root = nullptr;
}
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
reverse_iterator rbegin()
{
Node* cur = _root;
while (cur && cur->_right)
{
cur = cur->_right;
}
return reverse_iterator(iterator(cur));
}
reverse_iterator rend()
{
return reverse_iterator(iterator(nullptr));
}
pair<iterator, bool> Insert(const T& data);
Node* find(const K& key);
void RotateL(Node* parent);
void RotateR(Node* parent);
bool _CheckBlance(Node* root, int blackNum, int count);
bool CheckBlance();
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* copynode = new Node(root->_data);
copynode->_col = root->_col;
copynode->_left = Copy(root->_left);
copynode->_right = Copy(root->_right);
// 将孩子节点的_parent链接上
if (copynode->_left)
copynode->_left->_parent = copynode;
if (copynode->_right)
copynode->_right->_parent = copynode;
return copynode;
}
private:
KeyOfT _kt;
Node* _root;
};Ⅲ. set的模拟实现
从上面的改造红黑树，我们其实也可以发现 set 和 map 就是包装的红黑树啦，很多操作其实就是依赖着红黑树，所以这里就不细讲了，无非就是一些迭代器等等的 typedef 以及插入的返回值等等，具体参考红黑树的笔记！
🐛 值得注意就是这里传给红黑树的 Key 和 Value 都是 Key，以及一个比较器！
#include "RBTree.h"
namespace liren
{
template <class K>
class set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;
public:
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}Ⅳ. map的模拟实现
🐛 与 set 不同的是，map 多了一个 operator[]，以及传给红黑树的 Key 是 Key，但是 Value 是 pair<const K, Value>，其他都基本一样！
#include "RBTree.h"
namespace liren
{
template <class K, class V>
class map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;
public:
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> res = insert(make_pair(key, V()));
return res.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}