C++ 封装红黑树实现 map 和 set
红黑树结构
// RBTree.h
enum Colour { BLACK, RED };
template <class T>
struct RBTreeNode {
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};
其中 key 参数为 K，value 参数为 V，红黑树中的数据类型使用 T。RBTree 实现了泛型，但不知道 T 参数是 K 还是 pair<K, V>。因此我们在 map 和 set 层分别实现一个 MapOfT 和 SetOfT 的仿函数传给 RBTree 的 KeyOfT，然后 RBTree 中通过 KeyOfT 仿函数取出 T 类型对象中的 key，这样才方便比较。
实现迭代器
迭代器实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，使迭代器像指针一样访问的行为。
迭代器 ++
迭代器 ++ 的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下一个结点。
若 set 或 map 里的 key 是 {1, 2, 3, 4, 5, 6}，迭代器 it 指向的是 key 为 3 的节点，迭代器 ++，即要让 it 指向 key 为 4 的节点。因为 set 或 map 里的数据是有序的，所以迭代器 ++ 就是要根据底层的红黑树，找到大于当前迭代器指向的 key。
迭代器 ++ 时，如果 it 指向的结点的右子树不为空，要访问下一个结点是右子树的中序第一个，一棵树中序第一个是最左结点，所以直接找右子树的最左结点即可。因为默认小的在左，大的在右，++it 即在右子树中找比现在的 it 指向的节点的 key 大的，右子树所有节点的 key 都比现在 it 的 key 大，应该找右子树中最小的 key，即右子树的最左节点。
迭代器 ++ 时，如果 it 指向的结点的右子树为空，代表当前结点及当前结点所在的子树也访问完了，要访问的下一个结点在当前结点的祖先中，所以要沿着当前结点到根的路径向上找。
迭代器 ++，it 指向的节点右子树为空，如何正确找到下一个要访问的节点？从类定义中可知 it 有 2 个成员变量，其中一个就是指向当前节点的指针_node，让 cur 为 it->_node，cur 指向节点的父亲节点为 parent，不断向上回溯，当 parent 的左孩子为 cur 时，parent 就是 ++it 后 it 所在的位置。因为 it 指向节点的右为空说明该节点的 key 已经是某一子树里最大的 key 了，回溯分析如下图。
