红黑树的封装

一、封装思路

在 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.像搜索二叉树一样插入节点curwhile (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}elsereturn {cur, false};}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_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                            uif (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                       uelse 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;}elseassert(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博客解释过。