一、map和set类模板
在【C++】-- STL之map和set详解一文中提到，set用value标识元素(value就是key，类型为T)，并且每个value必须唯一 。
template < class Key>//set
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair：
typedef pair<const Key, T> value_type;
template < class Key, class T>//map
用红黑树同时封装出set和map时，set传给value的是一个value，map传给value的是一个pair，set和map传给红黑树的value决定了这棵树里面存的节点值类型。上层容器不同，底层红黑树的Key和T也不同。
在上层容器set中，K和T都代表Key，底层红黑树节点当中存储K和T都是一样的；map中，K代表键值Key，T代表由Key和Value构成的键值对，底层红黑树中只能存储T。所以红黑树为了满足同时支持set和map，节点当中存储T。
这就要对红黑树进行改动。
二、红黑树节点定义
1.红黑树的节点修改
把【C++】-- 红黑树详解的红黑树节点定义由类模板
template<class K,class V>
修改为
template<class T>
那么节点定义就修改为
1. //红黑树节点定义 2. template<class T> 3. struct RBTreeNode 4. { 5. RBTreeNode<T>* _left;//节点的左孩子 6. RBTreeNode<T>* _right;//节点的右孩子 7. RBTreeNode<T>* _parent;//节点的父亲 8. 9. T _data;//节点的值，_data里面存的是K就传K，存的是pair就传pair 10. Colour _col;//节点颜色 11. 12. RBTreeNode(const T& x) 13. :_left(nullptr) 14. , _right(nullptr) 15. , _parent(nullptr) 16. , _data(x) 17. , _col(RED) 18. {} 19. };
由于红黑树不知道上层传的是K还是pair，这是由上层传递的模板参数T决定的，上层是封装我的map和set。
2.仿函数
（1）节点比较大小时存在的问题
红黑树插入节点时，需要比较节点的大小，kv需要改成_data：
1. //插入 2. pair<Node*, bool> Insert(const T& data) 3. { 4. if (_root == nullptr) 5. { 6. _root = new Node(data); 7. _root->_col = BLACK; 8. return make_pair(_root, true); 9. } 10. 11. //1.先看树中，kv是否存在 12. Node* parent = nullptr; 13. Node* cur = _root; 14. while (cur) 15. { 16. if (cur->_data < data) 17. { 18. //kv比当前节点值大，向右走 19. parent = cur; 20. cur = cur->_right; 21. } 22. else if (cur->_data > data) 23. { 24. //kv比当前节点值小，向左走 25. parent = cur; 26. cur = cur->_left; 27. } 28. else 29. { 30. //kv和当前节点值相等，已存在，插入失败 31. return make_pair(cur, false); 32. } 33. } 34. 35. //2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了 36. Node* newNode = new Node(kv); 37. newNode->_col = RED; 38. if (parent->_data < data) 39. { 40. //kv比parent值大，插入到parent的右边 41. parent->_right = newNode; 42. newNode->_parent = parent; 43. } 44. else 45. { 46. //kv比parent值小，插入到parent的左边 47. parent->_left = newNode; 48. newNode->_parent = parent; 49. } 50. cur = newNode; 51. 52. //如果父亲存在，且父亲颜色为红就要处理 53. while (parent && parent->_col == RED) 54. { 55. //情况一和情况二、三的区别关键看叔叔 56. Node* grandfather = parent->_parent;//当父亲是红色时，根据规则（2）根节点一定是黑色，祖父一定存在 57. if (parent == grandfather->_left)//父亲是祖父的左子树 58. { 59. Node* uncle = grandfather->_right; 60. //情况一：叔叔存在且为红 61. if (uncle->_col == RED) 62. { 63. parent->_col = uncle->_col = BLACK; 64. grandfather->_col = RED; 65. 66. //继续向上调整 67. cur = grandfather; 68. parent = cur->_parent; 69. } 70. else//情况二+情况三：叔叔不存在或叔叔存在且为黑 71. { 72. //情况二：单旋 73. if (cur == parent->_left) 74. { 75. RotateR(grandfather); 76. parent->_col = BLACK; 77. grandfather->_col = RED; 78. } 79. else//情况三：双旋 80. { 81. RotateL(parent); 82. RotateR(grandfather); 83. cur->_col = BLACK; 84. grandfather->_col = RED; 85. } 86. break;//插入结束 87. } 88. } 89. else//父亲是祖父的右子树 90. { 91. Node* uncle = grandfather->_left; 92. //情况一：叔叔存在且为红 93. if (uncle && uncle->_col == RED) 94. { 95. parent->_col = uncle->_col = BLACK; 96. grandfather->_col = RED; 97. 98. //继续往上调整 99. cur = grandfather; 100. parent = grandfather->_parent; 101. } 102. else//情况二+情况三：叔叔不存在或叔叔存在且为黑 103. { 104. //情况二：单旋 105. if (cur == parent->_right) 106. { 107. RotateL(grandfather); 108. parent->_col = BLACK; 109. grandfather->_col = RED; 110. } 111. else//情况三：双旋 112. { 113. RotateR(parent); 114. RotateL(grandfather); 115. cur->_col = BLACK; 116. grandfather->_col = RED; 117. } 118. break;//插入结束 119. } 120. } 121. 122. } 123. _root->_col = BLACK; 124. 125. return make_pair(newNode, true); 126. }
但是以上代码在插入新节和查找节点时，当和当前节点比较大小时，Key可以比较，但是pair比较不了，也就是set可以比较，但是map比较不了。这就需要写一个仿函数，如果是map就取_data里面的first也就是Key进行比较，通过泛型解决红黑树里面存的是什么。所以上层容器map需要向底层的红黑树提供仿函数来获取T里面的Key，这样无论上层容器是set还是map，都可以用统一的方式进行比较了。
（2）仿函数
仿函数让一个类的使用看上去像个函数。仿函数是在类中实现了一个operator( )，是一个类的对象，这个类就有了类似函数的行为，所以这个类就是一个仿函数类，目的是为了让函数拥有类的性质。
这个类的对象即仿函数，可以当作一般函数去用，只不过仿函数的功能是在一个类中的运算符operator()中实现的，使用的时候把函数作为参进行传递即可。更详细的理解请参考【C++】-- STL容器适配器之priority_queue第三节第1小节的内容。
set有set的仿函数，map有map的仿函数，尽管set的仿函数看起来没有什么作用，但是，必须要把它传给底层红黑树，这样红黑树就能根据仿函数分别获取set的key和map的first。
①set的仿函数
1. namespace delia 2. { 3. template<class K> 4. class set 5. { 6. //仿函数，获取set的key 7. struct SetKeyOfT 8. { 9. const K& operator()(const K& key) 10. { 11. return key; 12. } 13. }; 14. 15. public: 16. bool insert(const K& k) 17. { 18. _t.Insert(k); 19. return true; 20. } 21. 22. private: 23. RBTree<K, K,SetKeyOfT> _t; 24. }; 25. }
②map的仿函数
1. namespace delia 2. { 3. template<class K,class V> 4. class map 5. { 6. //仿函数，获取map的first 7. struct MapKeyOfT 8. { 9. const K& operator()(const pair<const K, V>& kv) 10. { 11. return kv.first; 12. } 13. }; 14. 15. public: 16. //插入 17. bool insert(const pair<const K, V>& kv) 18. { 19. _t.Insert(kv); 20. return true; 21. } 22. private: 23. RBTree<K, pair<const K, V>, MapKeyOfT> _t; 24. }; 25. }
有了仿函数红黑树的类在实现时，就要在模板参数中增加KeyOfT仿函数。
（3）修改红黑树定义
1. template<class K, class T, class KeyOfT> 2. class RBTree 3. { 4. typedef RBTreeNode<T> Node; 5. 6. private: 7. Node* _root; 8. };
（4）修改红黑树插入
1. //插入 2. pair<Node*, bool> Insert(const pair<K, V>& kv) 3. { 4. if (_root == nullptr) 5. { 6. _root = new Node(kv); 7. _root->_col = BLACK; 8. return make_pair(_root, true); 9. } 10. 11. KeyOfT kot; 12. 13. //1.先看树中，kv是否存在 14. Node* parent = nullptr; 15. Node* cur = _root; 16. while (cur) 17. { 18. if (kot(cur->_data) < kot(data)) 19. { 20. //kv比当前节点值大，向右走 21. parent = cur; 22. cur = cur->_right; 23. } 24. else if (kot(cur->_data) > kot(data)) 25. { 26. //kv比当前节点值小，向左走 27. parent = cur; 28. cur = cur->_left; 29. } 30. else 31. { 32. //kv和当前节点值相等，已存在，插入失败 33. return make_pair(cur, false); 34. } 35. } 36. 37. //2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了 38. Node* newNode = new Node(kv); 39. newNode->_col = RED; 40. if (kot(parent->_data) < kot(data)) 41. { 42. //kv比parent值大，插入到parent的右边 43. parent->_right = newNode; 44. newNode->_parent = parent; 45. } 46. else 47. { 48. //kv比parent值小，插入到parent的左边 49. parent->_left = newNode; 50. newNode->_parent = parent; 51. } 52. cur = newNode; 53. 54. //如果父亲存在，且父亲颜色为红就要处理 55. while (parent && parent->_col == RED) 56. { 57. //情况一和情况二、三的区别关键看叔叔 58. Node* grandfather = parent->_parent;//当父亲是红色时，根据规则（2）根节点一定是黑色，祖父一定存在 59. if (parent == grandfather->_left)//父亲是祖父的左子树 60. { 61. Node* uncle = grandfather->_right; 62. //情况一：叔叔存在且为红 63. if (uncle->_col == RED) 64. { 65. parent->_col = uncle->_col = BLACK; 66. grandfather->_col = RED; 67. 68. //继续向上调整 69. cur = grandfather; 70. parent = cur->_parent; 71. } 72. else//情况二+情况三：叔叔不存在或叔叔存在且为黑 73. { 74. //情况二：单旋 75. if (cur == parent->_left) 76. { 77. RotateR(grandfather); 78. parent->_col = BLACK; 79. grandfather->_col = RED; 80. } 81. else//情况三：双旋 82. { 83. RotateL(parent); 84. RotateR(grandfather); 85. cur->_col = BLACK; 86. grandfather->_col = RED; 87. } 88. break;//插入结束 89. } 90. } 91. else//父亲是祖父的右子树 92. { 93. Node* uncle = grandfather->_left; 94. //情况一：叔叔存在且为红 95. if (uncle && uncle->_col == RED) 96. { 97. parent->_col = uncle->_col = BLACK; 98. grandfather->_col = RED; 99. 100. //继续往上调整 101. cur = grandfather; 102. parent = grandfather->_parent; 103. } 104. else//情况二+情况三：叔叔不存在或叔叔存在且为黑 105. { 106. //情况二：单旋 107. if (cur == parent->_right) 108. { 109. RotateL(grandfather); 110. parent->_col = BLACK; 111. grandfather->_col = RED; 112. } 113. else//情况三：双旋 114. { 115. RotateR(parent); 116. RotateL(grandfather); 117. cur->_col = BLACK; 118. grandfather->_col = RED; 119. } 120. break;//插入结束 121. } 122. } 123. 124. } 125. _root->_col = BLACK; 126. 127. return make_pair(newNode, true); 128. } 129. 130. void RotateR(Node* parent) 131. { 132. Node* subL = parent->_left; 133. Node* subLR = nullptr; 134. 135. if (subL) 136. { 137. subLR = subL->_right; 138. } 139. //1.左子树的右子树变我的左子树 140. parent->_left = subLR; 141. 142. if (subLR) 143. { 144. subLR->_parent = parent; 145. } 146. 147. //左子树变父亲 148. subL->_right = parent; 149. Node* parentParent = parent->_parent; 150. parent->_parent = subL; 151. 152. 153. if (parent == _root)//parent是根 154. { 155. _root = subL; 156. _root->_parent = nullptr; 157. } 158. else//parent不是根，是子树 159. { 160. if (parentParent->_left == parent) 161. { 162. //parent是自己父亲的左子树,将subL作为parent父亲的左孩子 163. parentParent->_left = subL; 164. } 165. else 166. { 167. //parent是自己父亲的右子树,将subL作为parent父亲的右孩子 168. parentParent->_right = subL; 169. } 170. 171. //subL的父亲就是parent的父亲 172. subL->_parent = parentParent; 173. } 174. } 175. 176. void RotateL(Node* parent) 177. { 178. Node* subR = parent->_right; 179. Node* subRL = nullptr; 180. 181. if (subR) 182. { 183. subRL = subR->_left; 184. } 185. 186. //1.右子树的左子树变我的右子树 187. parent->_right = subRL; 188. 189. if (subRL) 190. { 191. subRL->_parent = parent; 192. } 193. 194. //2.右子树变父亲 195. subR->_left = parent; 196. Node* parentParent = parent->_parent; 197. parent->_parent = subR; 198. 199. if (parent == _root)//parent是根 200. { 201. _root = parent; 202. _root->_parent = nullptr; 203. } 204. else//parent不是根，是子树 205. { 206. if (parentParent->_left == parent) 207. { 208. //parent是自己父亲的左子树,将subR作为parent父亲的左孩子 209. parentParent->_left = subR; 210. } 211. else 212. { 213. //parent是自己父亲的右子树,将subR作为parent父亲的右孩子 214. parentParent->_right = subR; 215. } 216. 217. //subR的父亲就是parent的父亲 218. subR->_parent = parentParent; 219. } 220. }
（5）修改红黑树查找
1. //查找 2. Node* Find(const K& key) 3. { 4. KeyOfT kot; 5. Node* cur = _root; 6. while (cur) 7. { 8. if (kot(cur->_data) < key) 9. { 10. cur = cur->_right; 11. } 12. else if (kot(cur->_data) > key) 13. { 14. cur = cur->_left; 15. } 16. else 17. { 18. return cur; 19. } 20. } 21. return nullptr;//空树，直接返回 22. }
