1. set和map中的红黑树
前一篇红黑树的源代码：
#pragma once #include <iostream> #include <assert.h> #include <time.h> using namespace std; enum Colour // 枚举颜色 { RED, BLACK }; template<class K, class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; // 比AVL树少了平衡因子，多了颜色 RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) {} }; template<class K, class V> struct RBTree { typedef RBTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; // 根给黑色 return true; } Node* parent = nullptr; Node* cur = _root; while (cur) // 找到要插入的结点 { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); cur->_col = RED; // 默认插入红色结点 if (parent->_kv.first < kv.first) // 找到位置后插入结点 { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) // 父亲存在且为红才需要处理 { Node* grandfather = parent->_parent; assert(grandfather); // 确定的可以断言下，否则就是插入前就不是红黑树 assert(grandfather->_col == BLACK); if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红(可以直接复制到下面uncle在左边) { // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else // 情况二或情况三：叔叔存在且为黑或叔叔不存在 { if(cur == parent->_left) // 情况二的右旋+变色(parent在左) { // g // p u // c RotateR(grandfather); parent->_col = BLACK; // 父亲变为根了 grandfather->_col = RED; } else // 情况二的左右双旋+变色(parent在左) { // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; // cur变为根了 grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红 { // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else // 情况二或情况三：叔叔存在且为黑或叔叔不存在 { if (cur == parent->_right) // 情况二的左旋+变色(parent在右) { // g // u p // c RotateL(grandfather); parent->_col = BLACK; // 父亲变为根了 grandfather->_col = RED; } else // 情况二的右左双旋+变色(parent在右) { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; // cur变为根了 grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) // 验证性质二 { cout << "根节点不是黑色" << endl; return false; } int benchmark = 0; // 黑色节点数量基准值 //Node* cur = _root; // 这种方法是先遍历一遍，然后传值，不过我们可以传引用 //while (cur) //{ // if (cur->_col == BLACK) // { // ++benchmark; // } // cur = cur->_left; //} return PrevCheck(_root, 0, benchmark); // 验证性质三和四 } protected: bool PrevCheck(Node* root, int blackNum, int& benchmark) { if (root == nullptr) { if (benchmark == 0) { benchmark = blackNum; return true; } if (blackNum != benchmark) // 验证性质三 { cout << "某条黑色节点的数量不相等" << endl; return false; } else { return true; } } if (root->_col == BLACK) { ++blackNum; } if (root->_col == RED && root->_parent->_col == RED) // 验证性质四 { cout << "存在连续的红色节点" << endl; return false; } return PrevCheck(root->_left, blackNum, benchmark) && PrevCheck(root->_right, blackNum, benchmark); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } void RotateL(Node* parent) { Node* subR = parent->_right; // 动了三个标记了的结点，共更新六个指针，这更新两个指针 Node* subRL = subR->_left; parent->_right = subRL; if (subRL) // subRL不为空才更新 { subRL->_parent = parent; } Node* ppNode = parent->_parent; // 记录parent的parent，防止parent是一颗子树的头结点 subR->_left = parent; // 再更新两个指针 parent->_parent = subR; if (_root == parent) // 最后更新两个指针 { _root = subR; subR->_parent = nullptr; } else // parent是一颗子树的头结点 { if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; // 更新两个节点 if (subLR) { subLR->_parent = parent; } Node* ppNode = parent->_parent; subL->_right = parent; // 再更新两个节点 parent->_parent = subL; if (_root == parent) // 最后更新两个结点 { _root = subL; subL->_parent = nullptr; } else { if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } } Node* _root = nullptr; };
在前一篇学习红黑树的时候，实现的是KV模型，节点中存放的是键值对pair。
而set中的节点只存放一个key值，map中的节点存放的是键值对。
但是map和set却使用的是同一颗红黑树。
这到底是怎么实现的呢？怎么做到一会儿是键值，一会又是键值对的呢？
看一下STL库中是如何实现的：
map和set中都既有key值，又有数据类型，map中的数据类型是键值对pair，
而set中的数据类型也是key值。STL模板中，红黑树中的数据类型只有一个。
无论是map还是set，底层封装的都是红黑树，
区别在于给红黑树实例化的是什么类型的模板参数。
map给红黑树传的模板参数是键值对pair。
set给红黑树传的模板参数是键值Key。
对于红黑树而言，它是不知道接收到的第二个模板参数value是什么类型的，
它只能推演。所以set对应的红黑树中的数据类型就是一个key值，
而map对应的红黑树中的数据类型就是一个键值对。
接下来就是对我们实现的红黑树进行改造，（配合上一篇一起看）
首先就是对结点进行改造，将原本的KV键值对数据类型改成T，像STL中一样，只有一个，
让编译器自己去推演这个数据类型是key值还是键值对：
template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; // 结点中的数据 Colour _col; // 比AVL树少了平衡因子，多了颜色 RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) {} };
红黑树中也不再用键值对去构建新节点，而是使用那一个数据类型T。
先改一点是这样的：
Set.h:
#pragma once #include "RedBlackTree.h" namespace rtx { template <class K> class set { protected: RBTree <K, K> _t; }; }
Map.h:
#pragma once #include "RedBlackTree.h" namespace rtx { template <class K,class V> class map { protected: RBTree <K, pair<K, V>> _t; }; }
set中，向红黑树传的模板参数是，第二个K传给节点，作为节点是数据类型。
map中，向红黑树传的模板参数是>键值对，
第二个参数键值对pair传给节点，作为节点的数据类型。
现在有一个问题，给红黑树传模板参数时，第一个参数K类型的作用是什么？
对于insert来说，set和map中都可以不要第一个参数K，因为第二个参数中就有K，
可以用来比较。但是对于find接口来说，它需要的只是K。set中第二个参数也是K，
所以第一个K也可以省略。map中第二个参数是一个键值对，如果省略了第一K后，
红黑树中只有一个键值对类型，在使用find的时候，无法确定拿到first的数据类型，
此时就需要第一个模板参数K来确定find的类型了。
虽然set中可以不需要第一个模板参数K，但是map不可以，因它两使用的一个红黑树，
所以为了统一，第一个模板参数K不能省略。
2. 仿函数比较键值对
改了数据那插入的所有比较都要改了，
站在红黑树的角度，并不知道它接收到的模板参数value是来自set中的键值还是map中的键值对。
在插入结点进行比较时：
set：cur->data 与 data进行比较，插入结点中的key值直接和树中的key值比较大小，决定插入左还是右即可。
map：cur->data.first 与 data.first进行比较，插入结点中的键值对的first和树种键值对的first比较，决定插入左还是右。
既然使用的是模板，是泛型编程，那么在比较处到底该写成map和set中的哪种比较方式呢？
要知道set中的data不是键值对，是没有first的，而map中的data直接比较又不符合我们的要求。
（pair也能比较键值对，不过它在first一样时比较了second，但我们不想比较second）
（关于set和map的细节可以回去看看
此专栏第26篇，后面实现方括号也要知道细节，链接：从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别-CSDN博客）
此时我们也不能自己重新定义键值对的比较方式，因为库中已经有了，
我们无法再重载一个函数名，返回值，参数都相同的比较方式。
为了能够在红黑树中使用统一的比较方式，这里采用仿函数的方式：
在set和map中各定义一个仿函数，专门用来获取key值的，
并且将这个仿函数当作模板参数传给红黑树。
实现下仿函数和封装下insert，现在的部分代码就是这样：
set中存放的数据本身就是key，所以获取key时有点多此一举，但是为了和红黑树的结构以及map的结构统一，也需要写一个。
map中存放的数据是键值对，所以仿函数返回的是键值对中的first，依次来获取到key值。
在插入函数inset中，创建仿函数对象koft。
在需要进行键值key比较的位置，使用仿函数koft获取键值进行比较，然后决定插入左边函数右边。
使用仿函数的方法，压根就不用关心比较的是键值还是键值对，因为set和map都会给红黑树传它自己获取键值的仿函数，最终比较的都是键值。
set和map中的插入直接复用红黑树中的插入即可。
但是set中插入的是一个键值，而map中插入的是一个键值对。
跑一下测试用例：
#include "RedBlackTree.h" #include "Set.h" #include "Map.h" namespace rtx { void TestSet() { set<int> s; s.insert(1); s.insert(5); s.insert(3); s.insert(5); } void TestMap() { map<int,int> m; m.insert(make_pair(6, 1)); m.insert(make_pair(2, 1)); m.insert(make_pair(3, 1)); m.insert(make_pair(2, 1)); } } int main() { rtx::TestSet(); rtx::TestMap(); return 0; }
如果想遍历，那么就要实现迭代器了。
3. 红黑树迭代器的实现
这里实现的和库里的不太一样，库里的实现是带哨兵位头结点的，它指向根结点，
它的左指向中序遍历的第一个结点，右指向中序遍历的最后一个结点。
但不用哨兵位头结点也能实现，所以就不改了。
set和map的迭代器就是红黑树的迭代器：
这里可以参考list的迭代器，红黑树也是通过指针来链接的。
template<class T, class Ref, class Ptr> struct __RBTreeInterator { public: typedef RBTreeNode<T> Node; typedef __RBTreeIterator<T, Ref, Ptr> Self; Node* _node; __RBTreeIterator(Node* node) :_node(node) {} };
最基本的迭代器如上面所示代码，迭代器中只有一个成员变量，那就是节点node。
下面就是逐渐完善迭代器支持的功能了，比如解引用，判断等于，加加，减减，等操作。
解引用+箭头+等于+不等于：（这里和链表是一样的，就不再详细讲解了）
template<class T, class Ref, class Ptr> struct __RBTreeIterator { public: typedef RBTreeNode<T> Node; typedef __RBTreeIterator<T, Ref, Ptr> Self; Node* _node; __RBTreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } };
比较的内容是两个迭代器指向节点是否相同，而不是节点中的值。
无论是普通对象还是const对象，都可以调用const版本，并且仅仅是进行比较，
所以只有const版本的就够用了。
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现（下）：https://developer.aliyun.com/article/1522303?spm=a2c6h.13148508.setting.17.50c04f0es3cPJy
