[C++] map、set的 红黑树 封装（一）
标题：[C++] map、set的 红黑树 封装
@水墨不写bug
（图片来源于网络）
目录
一、红黑树与AVL树的比较（为什么容器选择红黑树）
二、map、set的封装
1.模板参数
2.红黑树迭代器设计
正文开始：
一、红黑树与AVL树的比较（为什么容器选择红黑树）
AVL树保证了二叉树的绝对平衡，也就是左右子树的高度差的小于等于1；
红黑树保证了二叉树的相对平衡，具体是最长路径的长度不大于最短路径的2倍；
红黑树和AVL树都是高效的二叉平衡树，唯一不同的是保证平衡的策略不同。红黑树的高度必然比AVL树高，但是红黑树拥有自己独特的优势。
两种平衡二叉树的增删改查的时间复杂度都是O(log N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
二、map、set的封装
1.模板参数
C++的STL内关联性容器map、set的底层实现都是红黑树，并且是同一个类模板实例化出来的类。但是对于这一点你会或多或少有一些疑问：
1.map和set的数据类型不同，怎么实现共用一种实现方式？
2.红黑树的迭代器又是如何设计的？
在之前的文章中，我们详细讲解了红黑树的实现：《[数据结构] RBTree && 模拟实现RBTree》
为了实现红黑树，我们首先实现了红黑树的节点类，对于红黑树的一个节点，根据需要实现为三叉链型，此外包含了数据和颜色：（具体如下）
namespace ddsm {enum COLOR{BLACK,RED};//这里的模板参数是一个不确定的类型，可以是int，也可以是pair，//根据传入的模板参数来决定实例化出的类内部的成员在_data的类型template<class V>struct RBTreeNode{RBTreeNode<V>* _parent;RBTreeNode<V>* _left;RBTreeNode<V>* _right;V _data;COLOR _col;//红黑树节点的默认构造RBTreeNode(const V& data = V()):_parent(nullptr),_left(nullptr),_right(nullptr), _data(data),_col(RED){}}; }
以红黑树节点类为基础，我们在上面提到的文章中实现了基本的红黑树。为了解决map、set复用同一颗红黑树但是存储数据类型不同的问题，我们在实现map和set时采取了不同方法：
不着急，我们具体慢慢理解一下：
在设计红黑树的时候，我们提前约定好，传入的模板参数第一个K，用于find或者erase时的查找，（find和erase的查找需要根据key来查找）；传入的第二个模板参数是数据域，代表存入的数据类型。而第三个模板参数是为了便于封装时复用而设计的。
由于我们在find的时候，并不知道容器内是否有我们要查找的对象，所以我们用key来查找是理所当然的；
同时，我们在插入的时候，也只需要表示插入的对象即可，不需要单独的指出插入对象的key（查找键值）和value（数据域），但是在insert的逻辑中，却需要我们根据key的大小关系来决定插入的位置，这就需要我们在知道value（数据域）的情况下提取出key。这个功能可以通过仿函数来实现：
通过仿函数，我们就可以通过实例化一个仿函数对象，将数据域交给这个对象处理，这样就能够取到value对应的key。
于是，在insert的逻辑中，我们决定插入位置时，在需要用key比较的地方，通过仿函数处理value得到key，再进行比较：
bool insert(const V& data) {//对于空的特殊处理if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}//找到插入位置Node* cur = _root, * parent = nullptr;KeyOfV keyofv;//创建仿函数对象，map和set各自会实例化出自己对应的类，这些类又会各//自调用自己对应的仿函数类实例化出的对象while (cur){if (keyofv(cur->_data) < keyofv(data)){parent = cur;cur = cur->_right;}else if (keyofv(cur->_data) > keyofv(data)){parent = cur;cur = cur->_left;}else{//插入失败,有相同值return false;}}//new并连接cur = new Node(data);if (keyofv(parent->_data) < keyofv(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//降低平衡//二叉树逻辑结束，红黑树开始//cur为红，p为红，g为黑，while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){//uncle在右侧// g// p u// Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//u存在且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续向上处理cur = grandfather;parent = cur->_parent;}else//u不存在或者u存在且为黑//旋转{if (cur == parent->_left){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else{//uncle在左侧s// g// u p// Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle存在且为红{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else//uncle不存在或者存在且为黑//旋转{if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return true; }
2.红黑树迭代器设计
map和set内拥有迭代器，有begin和end接口，这是实现范围for的基础。为map和set底层的红黑树实现出迭代器对于map、set容器的使用有极大的方便。
什么是迭代器，你一定知道：迭代器是一种类似于指针的东西。指针是内置类型的，它有自己的行为逻辑：“*”表示解运用，取出指针指向的数据；“++”表示指针向后移动一个数据类型的长度（如果是线性容器的话，有意义）。“--”则相反；
指针就是一种迭代器！在之前我们模拟实现string，vector的时候，我们就是用对应数据类型的指针来模拟迭代器的。指针是一种没有任何限制的迭代器，我们如果不满意指针的行为，就可以通过封装指针并在类内重载运算符的方法，来改变指针的内置默认行为。
在明白这一点之后，我们实现红黑树迭代器就畅行无阻了，我们直接封装一个红黑树节点的指针作为红黑树的迭代器，内部重载了++，==，!=，*等等运算符（可以根据逻辑需求自行添加）：这就是红黑树迭代器的大框架，具体实现我们后面再讨论：
//迭代器类似于指针，内置类型的指针的++，*，==，!= 运算默认成立
//红黑树迭代器类目的在于 重载++,*,==,!=运算符，红黑树迭代器按照我们想要的方式进行运算
template<class V>
struct RBTreeIterator
{typedef RBTreeIterator<V> Self;typedef RBTreeNode<V> Node;Node* _node;RBTreeIterator(Node* node):_node(node){}Self& operator++();bool operator!=(const Self& s);bool operator==(const Self& s);V& operator*();};在红黑树内为了与上层区分，迭代器名称首字母大写：
//V在于类型不确定：单个内置类型 / pair类型
template<class K,class V,class KeyOfV>
class RBTree
{typedef RBTreeNode<V> Node;typedef Node* PNode;
public:typedef RBTreeIterator<V> Iterator;Node* _root;
};别忘记了上层的实现，我们在map和set中也各自规范一下迭代器的名称：
template<class K,class V>
class map
{struct MapKeyOfV{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public://封装红黑树的Iterator，在本封装层套一层壳typedef typename RBTree<K, pair<K, V>, MapKeyOfV>::Iterator iterator;private:RBTree<K, pair<K, V>, MapKeyOfV> _rbtree;
};
template<class K>
class set
{struct SetKeyOfV{const K& operator()(const K& key){return key;}};
public://封装红黑树的Iterator，在本封装层套一层壳typedef typename RBTree<K, K, SetKeyOfV>::Iterator iterator;
private:RBTree<K, K, SetKeyOfV> _rbtree;
};待续~
未经作者同意禁止转载