红黑树的封装
一、封装思路
在 STL 中 map set 的底层就是封装了一棵红黑树。
其中连接红黑树和容器的是迭代器，map set 暴露出的接口都不是自己写的，而是红黑树写的，外部接口封装红黑树接口。
所以写出红黑树为 map set 写的接口，再在上层的 map set 类中包装一下即可。
之前的红黑树就是单纯的在树上插入节点，为了实现 map set 就需要红黑树再实现迭代器。
二、红黑树细节实现
1、迭代器
本质就是封装了一个节点，用于遍历红黑树找到目标值。
（1）整体设计
与链表迭代器一样，需要迭代器重载解引用和箭头，所以模板依旧设计成：
template<class T, class Ref, class Ptr>
来适应 const 迭代器的复用。
（2）重载解引用
// 解引用迭代器是取数据
Ref operator*()
{
return _node->_data;
}（3）重载箭头
// 取数据的地址
Ptr operator->()
{
return &(_node->_data);
}（4）重载不等于
bool operator!=(const Self& it)
{
return _node != it._node;
}（5）后置++
// 1.如果右子树存在，访问右子树的最左节点
// 2.如果右子树不存在，如果我是父亲的左，那就访问父亲
// 如果我是父亲的右，表示父亲也完了，向上判断，直到是左孩子
Self& operator++()
{
if (_node->_right)
{
Node* cur = _node->_right;
while (cur->_left)
cur = cur->_left;
_node = cur;
}
else
{
Node* cur = _node;
while (cur->_parent && cur == cur->_parent->_right)
cur = cur->_parent;
_node = cur->_parent;
}
return *this;
}（6）后置--
// 1.如果左子树存在，返回左子树的最右节点
// 2.如果左子树不存在，如果是父亲的右孩子，返回根
// 如果是父亲的左孩子，向上找直到是右孩子
Self& operator--()
{
Node* cur = _node;
if (_node->_left)
{
while (cur->_right)
cur = cur->_right;
_node = cur;
}
else
{
while (cur && cur == cur->_parent->_left)
cur = cur->_parent;
_node = cur->_parent;
}
return *this;
}2、红黑树
到这里迭代器已经实现完毕，要把裸的迭代器实现出不同的形式花样就是在红黑树这一层实现的。
（1）整体设计
从这里开始就要考虑如何把容器与红黑树相关联。
难点一
map 是 kv 模型，set 是 key 模型，类型都不一样，怎么防止在一份红黑树代码中参数的冲突？
库里面的解决办法是：template<class K, class T>
这里的 T 是存放的数据类型，即 map 是 pair<K, V>，set 是 K，这样至少能传入正确的参数了。
但是红黑树主要功能插入删除的比较参数是 key，所以直接传入的参数 T 用于比较（map 的 pair<K, V> 比较逻辑是 K 大的就返回，K 不大就 V 大的返回，显然不符合比较逻辑）是不行的，我们需要都是比较 K，所以还需要一个内部类提取 map set 的 key 值。
所以最终的红黑树模板参数如下：
template<class K, class T, class KeyOfT>
K 是 key 的类型，T 是容器存储的数据类型，KeyOfT 是分别在 map 和 set 中实现的内部类分别提取其中的 key 用于插入删除函数的比较。
难点二
迭代器分为 const 迭代器和非 const 迭代器，所以在红黑树中也要封装。
不用写两份迭代器代码，之前迭代器的模板参数就起作用了：其实 const 和非 const 的区别就是指向的内容不能修改，就是解引用和箭头的重载返回值不能被修改，利用模板实例化就能解决问题：
// 红黑树中定义两个迭代器，模板参数不同即可
typedef __RBTreeIterator<T, T&, T*> Iterator;
typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;（2）构造析构
由于已经要和容器接轨了，所以要考虑深浅拷贝问题，这里封装了常见的默认成员函数
RBTree() = default; // 由于已经写了拷贝构造，强制生成默认构造
// 私有的概念只针对于类外，类内可以访问其他对象的私有成员
RBTree(const RBTree<K, T, KeyOfT>& tree)
{
_root = Copy(tree._root);
}
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> tree)
{
swap(_root, tree._root);
}
~RBTree()
{
Destroy(_root);
_root = nullptr;
}（3）迭代器封装
在迭代器类中已经处理了迭代器的使用逻辑，在红黑树这一层就是封装容器的迭代器常用功能
Iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left)
leftMin = leftMin->_left;
return leftMin;
}
Iterator end()
{
return Iterator(nullptr);
}
ConstIterator begin() const
{
Node* leftMin = _root;
while (leftMin && leftMin->_left)
leftMin = leftMin->_left;
return leftMin;
}
ConstIterator end() const
{
return ConstIterator(nullptr);
}注意 const 迭代器函数后面需要加 const 构成函数重载。
（4）insert 改造
和库里面保持一致，插入函数返回插入元素的迭代器和是否插入成功的 pair
为了比较的正确性要利用内部类 KeyOfT 来取出数据的 key 进行比较
pair<Iterator, bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return {_root, true};
}
Node* cur = _root;
Node* parent = cur;
KeyOfT kot;
// 1.像搜索二叉树一样插入节点cur
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;
}
else
return {cur, false};
}
cur = new Node(data);
Node* newnode = cur;
if (kot(parent->_data) < kot(data))
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
// 新插入是红色，如果父亲是黑色就没事
while (parent && parent->_col == RED)
{
Node* g = parent->_parent;
Node* uncle = parent == g->_left ? g->_right : g->_left;
// 情况一：叔叔存在且为红，u p 变黑，g变红，向上
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
g->_col = RED;
cur = g;
parent = cur->_parent;
}
// 情况二：叔叔存在且为黑或叔叔不存在
else
{
// u parent cur 的位置决定的是左右单旋双旋
// gB pB
// pR u -> cR gR
// cR u
if (cur == parent->_left && parent == g->_left)
{
RotateR(g);
parent->_col = BLACK;
g->_col = RED;
}
// gB gB cB
// pR u -> cR u -> pR gR
// cR pR u
else if (cur == parent->_right && parent == g->_left)
{
RotateL(parent);
RotateR(g);
cur->_col = BLACK;
g->_col = RED;
}
// gB pB
// u pR -> gR cR
// cR u
else if (cur == parent->_right && parent == g->_right)
{
RotateL(g);
g->_col = RED;
parent->_col = BLACK;
}
// gB gB cB
// u pR -> u cR -> gR pR
// cR pR u
else if (cur == parent->_left && parent == g->_right)
{
RotateR(parent);
RotateL(g);
cur->_col = BLACK;
g->_col = RED;
}
else
assert(false);
break;
}
}
_root->_col = BLACK;
return {newnode, true};
}三、容器细节实现
首先容器的实现共性是 map set 上层确确实实只传入 <K, V> 和 <K>，是底层红黑树为了适应容器，底层红黑树的实例化是 <K, pair<K, V>, KeyOfT> 和 <K, K, KeyOfT>
其次两者都要实现各自的 KeyOfT 内部类来告诉底层红黑树要怎么取到 key 值。
最后容器封装底层红黑树写好的迭代器代码交给外部使用。
1、set 实现
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::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();
}
iterator find(const K& key)
{
return _t.find(key);
}
pair<iterator, bool> insert(const K& key)
{
return _t.insert(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};2、map 实现
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<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>::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();
}
iterator find(const K& key)
{
return _t.find(key);
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.insert({ key, V() });
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};值得一提的是 map 还要重载 []，其实现逻辑已经在博客map和set-CSDN博客解释过。