当前位置:   article > 正文

<map与set的模拟实现>——《C++高阶》_cpp用map实现封装

cpp用map实现封装

 目录

<红黑树模拟实现STL中的map与set> 

1.红黑树的迭代器

2. 改造红黑树

3.map的模拟实现

附用红黑树:

(1)map.h:

(2)RBTree.h:

(3)test.cpp:

4.set的模拟实现

附用红黑树:

(1)set.h:

(2)RBTree.h:

后记:●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教!

                                                                       ——By 作者:新晓·故知


<红黑树模拟实现STL中的map与set> 

GIF:

1.红黑树的迭代器

迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器,需要考虑以前问题: begin()与end()
STL明确规定,begin()与end()代表的是一段前闭后开的区间,而对红黑树进行中序遍历后,
可以得到一个有序的序列,因此:begin()可以放在红黑树中最小节点(即最左侧节点)的位
end()放在最大节点(最右侧节点)的下一个位置,关键是最大节点的下一个位置在哪块?
能否给成nullptr呢?答案是行不通的,因为对end()位置的迭代器进行--操作,必须要能找最
后一个元素,此处就不行,因此最好的方式是将end()放在头结点的位置
图片源于网络:(这里仅做学习用途,如有侵权,请联系删除!) 
  •  operator++()与operator--()
    1. // 找迭代器的下一个节点,下一个节点肯定比其大
    2. void Increasement()
    3. {
    4. //分两种情况讨论:_pNode的右子树存在和不存在
    5. // 右子树存在
    6. if (_pNode->_pRight)
    7. {
    8. // 右子树中最小的节点,即右子树中最左侧节点
    9. _pNode = _pNode->_pRight;
    10. while (_pNode->_pLeft)
    11. _pNode = _pNode->_pLeft;
    12. }
    13. else
    14. {
    15. // 右子树不存在,向上查找,直到_pNode != pParent->right
    16. PNode pParent = _pNode->_pParent;
    17. while (pParent->_pRight == _pNode)
    18. {
    19. _pNode = pParent;
    20. pParent = _pNode->_pParent;
    21. }
    22. // 特殊情况:根节点没有右子树
    23. if (_pNode->_pRight != pParent)
    24. _pNode = pParent;
    25. }
    26. }
    27. // 获取迭代器指向节点的前一个节点
    28. void Decreasement()
    29. {
    30. //分三种情况讨论:_pNode 在head的位置,_pNode 左子树存在,_pNode 左子树不存在
    31. // 1. _pNode 在head的位置,--应该将_pNode放在红黑树中最大节点的位置
    32. if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED)
    33. _pNode = _pNode->_pRight;
    34. else if (_pNode->_pLeft)
    35. {
    36. // 2. _pNode的左子树存在,在左子树中找最大的节点,即左子树中最右侧节点
    37. _pNode = _pNode->_pLeft;
    38. while (_pNode->_pRight)
    39. _pNode = _pNode->_pRight;
    40. }
    41. else
    42. {
    43. // _pNode的左子树不存在,只能向上找
    44. PNode pParent = _pNode->_pParent;
    45. while (_pNode == pParent->_pLeft)
    46. {
    47. _pNode = pParent;
    48. pParent = _pNode->_pParent;
    49. }
    50. _pNode = pParent;
    51. }
    52. }

2. 改造红黑树

  1. // 因为关联式容器中存储的是<key, value>的键值对,因此
  2. // k为key的类型,
  3. // ValueType: 如果是map,则为pair<K, V>; 如果是set,则为k
  4. // KeyOfValue: 通过value来获取key的一个仿函数类
  5. template<class K, class ValueType, class KeyOfValue>
  6. class RBTree
  7. {
  8. typedef RBTreeNode<ValueType> Node;
  9. typedef Node* PNode;
  10. public:
  11. typedef RBTreeIterator<ValueType, ValueType*, ValueType&> Iterator;
  12. public:
  13. RBTree();
  14. ~RBTree()
  15. /
  16. // Iterator
  17. Iterator Begin() { return Iterator(_pHead->_pLeft); }
  18. Iterator End() { return Iterator(_pHead); }
  19. //
  20. // Modify
  21. pair<Iterator, bool> Insert(const ValueType& data)
  22. {
  23. // 插入节点并进行调整
  24. // 参考上文...
  25. return make_pair(Iterator(pNewNode), true);
  26. }
  27. // 将红黑树中的节点清空
  28. void Clear();
  29. Iterator Find(const K& key);
  30. //
  31. // capacity
  32. size_t Size()const;
  33. bool Empty()const;
  34. // ……
  35. private:
  36. PNode _pHead;
  37. size_t _size;  // 红黑树中有效节点的个数
  38. };

3.map的模拟实现

map的底层结构就是红黑树,因此在map中直接封装一棵红黑树,然后将其接口包装下即可
  1. namespace bite
  2. {
  3. template<class K, class V>
  4. class map
  5. {
  6. typedef pair<K, V> ValueType;
  7. // 作用:将value中的key提取出来
  8. struct KeyOfValue
  9. {
  10. const K& operator()(const ValueType& v)
  11. {
  12. return v.first;
  13. }
  14. };
  15. typedef RBTree<K, ValueType, KeyOfValue> RBTree;
  16. public:
  17. typedef typename RBTree::Iterator iterator;
  18. public:
  19. map() {}
  20. /
  21. // Iterator
  22. iterator begin() { return _t.Begin(); }
  23. iterator end() { return _t.End(); }
  24. /
  25. // Capacity
  26. size_t size()const { return _t.Size(); }
  27. bool empty()const { return _t.Empty(); }
  28. /
  29. // Acess
  30. V& operator[](const K& key)
  31. {
  32. return (*(_t.Insert(ValueType(key, V()))).first).second;
  33. }
  34. const V& operator[](const K& key)const;
  35. // modify
  36. pair<iterator, bool> insert(const ValueType& data)
  37. {
  38. return _t.Insert(data);
  39. }
  40. void clear() { _t.Clear(); }
  41. iterator find(const K& key) { return _t.Find(key); }
  42. private:
  43. RBTree _t;
  44. };
  45. }

附用红黑树:

(1)map.h:

  1. #pragma once
  2. #include"RBTree.h"
  3. namespace my
  4. {
  5. template<class K, class V>
  6. class map
  7. {
  8. struct MapKeyOfT
  9. {
  10. const K& operator()(const pair<K, V>& kv)
  11. {
  12. return kv.first;
  13. }
  14. };
  15. public:
  16. typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
  17. typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
  18. iterator begin()
  19. {
  20. return _t.Begin();
  21. }
  22. iterator end()
  23. {
  24. return _t.End();
  25. }
  26. pair<iterator, bool> insert(const pair<K, V>& kv)
  27. {
  28. return _t.Insert(kv);
  29. }
  30. iterator find(const K& key)
  31. {
  32. return _t.Find(key);
  33. }
  34. V& operator[](const K& key)
  35. {
  36. pair<iterator, bool> ret = insert(make_pair(key, V()));
  37. return ret.first->second;
  38. }
  39. private:
  40. RBTree<K, pair<K, V>, MapKeyOfT> _t;
  41. };
  42. void test_map1()
  43. {
  44. map<string, int> m;
  45. m.insert(make_pair("111", 1));
  46. m.insert(make_pair("555", 5));
  47. m.insert(make_pair("333", 3));
  48. m.insert(make_pair("222", 2));
  49. //迭代器遍历
  50. map<string, int>::iterator it = m.begin();
  51. while (it != m.end())
  52. {
  53. cout << it->first << ":" << it->second << endl;
  54. ++it;
  55. }
  56. cout << endl;
  57. //范围for遍历
  58. for (auto& kv : m)
  59. {
  60. cout << kv.first << ":" << kv.second << endl;
  61. }
  62. cout << endl;
  63. }
  64. void test_map2()
  65. {
  66. string arr[] = { "ƻ", "", "ƻ", "", "ƻ", "ƻ", "", "ƻ", "㽶", "ƻ", "㽶" };
  67. //迭代器遍历
  68. map<string, int> countMap;
  69. for (auto& str : arr)
  70. {
  71. countMap[str]++;
  72. }
  73. //范围for遍历
  74. for (const auto& kv : countMap)
  75. {
  76. cout << kv.first << ":" << kv.second << endl;
  77. }
  78. }
  79. void test_map3()
  80. {
  81. map<string, string> dict;
  82. dict["insert"];
  83. dict["insert"] = "";
  84. dict["left"] = "";
  85. }
  86. }

(2)RBTree.h:

  1. #pragma once
  2. #include<iostream>
  3. #include<vector>
  4. #include<queue>
  5. #include<cassert>
  6. using namespace std;
  7. enum Colour
  8. {
  9. RED,
  10. BLACK,
  11. };
  12. template<class T>
  13. struct RBTreeNode
  14. {
  15. RBTreeNode<T>* _left;
  16. RBTreeNode<T>* _right;
  17. RBTreeNode<T>* _parent;
  18. T _data;
  19. Colour _col;
  20. RBTreeNode(const T& data)
  21. :_data(data)
  22. , _left(nullptr)
  23. , _right(nullptr)
  24. , _parent(nullptr)
  25. , _col(RED)
  26. {}
  27. };
  28. //T决定红黑树存什么数据
  29. //set RBTree<K,K>
  30. //map RBTree<K,pair<K,V>>
  31. //KeyOfT -> 支持取出T对象中key的仿函数
  32. template<class T, class Ref, class Ptr>
  33. struct __RBTreeIterator
  34. {
  35. typedef RBTreeNode<T> Node;
  36. typedef __RBTreeIterator<T, Ref, Ptr> Self;
  37. Node* _node;
  38. __RBTreeIterator(Node* node)
  39. :_node(node)
  40. {}
  41. //运算符*重载
  42. Ref operator*()
  43. {
  44. return _node->_data;
  45. }
  46. //运算符->重载
  47. Ptr operator->()
  48. {
  49. return &_node->_data;
  50. }
  51. //重载 前置++
  52. Self& operator++()
  53. {
  54. if (_node->_right == nullptr)
  55. {
  56. // 找祖先里面,孩子是父亲左的那个
  57. Node* cur = _node;
  58. Node* parent = cur->_parent;
  59. while (parent && parent->_right == cur)
  60. {
  61. cur = cur->_parent;
  62. parent = parent->_parent;
  63. }
  64. _node = parent;
  65. }
  66. else
  67. {
  68. // 右子树的最左节点
  69. Node* subLeft = _node->_right;
  70. while (subLeft->_left)
  71. {
  72. subLeft = subLeft->_left;
  73. }
  74. _node = subLeft;
  75. }
  76. return *this;
  77. }
  78. //重载 后置++
  79. Self operator++(int)
  80. {
  81. Self tmp(*this);
  82. ++(*this);
  83. return tmp;
  84. }
  85. //重载 前置--
  86. Self& operator--()
  87. {
  88. if (_node->_left == nullptr)
  89. {
  90. // 找祖先里面,孩子是父亲
  91. Node* cur = _node;
  92. Node* parent = cur->_parent;
  93. while (parent && cur == parent->_left)
  94. {
  95. cur = cur->_parent;
  96. parent = parent->_parent;
  97. }
  98. _node = parent;
  99. }
  100. else
  101. {
  102. // 左子树的最右节点
  103. Node* subRight = _node->_left;
  104. while (subRight->_right)
  105. {
  106. subRight = subRight->_right;
  107. }
  108. _node = subRight;
  109. }
  110. return *this;
  111. }
  112. //重载 后置--
  113. Self operator--(int)
  114. {
  115. Self tmp(*this);
  116. --(*this);
  117. return tmp;
  118. }
  119. //重载 !=
  120. bool operator!=(const Self& s) const
  121. {
  122. return _node != s._node;
  123. }
  124. //重载 ==
  125. bool operator==(const Self& s) const
  126. {
  127. return _node == s->_node;
  128. }
  129. };
  130. template<class K, class T, class KeyOfT>
  131. class RBTree
  132. {
  133. typedef RBTreeNode<T> Node; //默认为私有
  134. public:
  135. typedef __RBTreeIterator<T, T&, T*> iterator;
  136. typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
  137. // 构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的
  138. iterator Begin()
  139. {
  140. Node* subLeft = _root;
  141. while (subLeft && subLeft->_left)
  142. {
  143. subLeft = subLeft->_left;
  144. }
  145. return iterator(subLeft);
  146. }
  147. iterator End()
  148. {
  149. return iterator(nullptr);
  150. }
  151. const_iterator Begin() const
  152. {
  153. Node* subLeft = _root;
  154. while (subLeft && subLeft->_left)
  155. {
  156. subLeft = subLeft->_left;
  157. }
  158. return const_iterator(subLeft);
  159. }
  160. const_iterator End() const
  161. {
  162. return const_iterator(nullptr);
  163. }
  164. //insert数据
  165. pair<iterator, bool> Insert(const T& data)
  166. {
  167. // 1、搜索树的规则插入
  168. // 2、看是否违反平衡规则,如果违反就需要处理:旋转
  169. if (_root == nullptr)
  170. {
  171. _root = new Node(data);
  172. _root->_col = BLACK;
  173. return make_pair(iterator(_root), true);
  174. }
  175. KeyOfT kot;
  176. Node* parent = nullptr;
  177. Node* cur = _root;
  178. while (cur)
  179. {
  180. if (kot(cur->_data) < kot(data))
  181. {
  182. parent = cur;
  183. cur = cur->_right;
  184. }
  185. else if (kot(cur->_data) > kot(data))
  186. {
  187. parent = cur;
  188. cur = cur->_left;
  189. }
  190. else
  191. {
  192. return make_pair(iterator(cur), true);
  193. }
  194. }
  195. cur = new Node(data);
  196. Node* newnode = cur;
  197. cur->_col = RED;
  198. if (kot(parent->_data) < kot(data))
  199. {
  200. parent->_right = cur;
  201. }
  202. else
  203. {
  204. parent->_left = cur;
  205. }
  206. cur->_parent = parent;
  207. // 存在连续红色节点
  208. while (parent && parent->_col == RED)
  209. {
  210. Node* grandfater = parent->_parent;
  211. assert(grandfater);
  212. if (grandfater->_left == parent)
  213. {
  214. Node* uncle = grandfater->_right;
  215. // 情况一:
  216. if (uncle && uncle->_col == RED) // 叔叔存在且为红
  217. {
  218. // 变色
  219. parent->_col = uncle->_col = BLACK;
  220. grandfater->_col = RED;
  221. // 继续往上处理
  222. cur = grandfater;
  223. parent = cur->_parent;
  224. }
  225. else // 叔叔不存在 或者 叔叔存在且为黑
  226. {
  227. if (cur == parent->_left) // 单旋
  228. {
  229. // g
  230. // p
  231. // c
  232. RotateR(grandfater);
  233. parent->_col = BLACK;
  234. grandfater->_col = RED;
  235. }
  236. else // 双旋
  237. {
  238. // g
  239. // p
  240. // c
  241. RotateL(parent);
  242. RotateR(grandfater);
  243. cur->_col = BLACK;
  244. grandfater->_col = RED;
  245. }
  246. break;
  247. }
  248. }
  249. else //(grandfater->_right == parent)
  250. {
  251. Node* uncle = grandfater->_left;
  252. // 情况一:
  253. if (uncle && uncle->_col == RED)
  254. {
  255. // 变色
  256. parent->_col = uncle->_col = BLACK;
  257. grandfater->_col = RED;
  258. // 继续往上处理
  259. cur = grandfater;
  260. parent = cur->_parent;
  261. }
  262. else
  263. {
  264. if (cur == parent->_right)
  265. {
  266. // g
  267. // p
  268. // c
  269. RotateL(grandfater);
  270. parent->_col = BLACK;
  271. grandfater->_col = RED;
  272. }
  273. else // 双旋
  274. {
  275. // g
  276. // p
  277. // c
  278. RotateR(parent);
  279. RotateL(grandfater);
  280. cur->_col = BLACK;
  281. grandfater->_col = RED;
  282. }
  283. break;
  284. }
  285. }
  286. }
  287. _root->_col = BLACK;
  288. return make_pair(iterator(newnode), true);
  289. }
  290. //左旋
  291. void RotateL(Node* parent)
  292. {
  293. Node* subR = parent->_right;
  294. Node* subRL = subR->_left;
  295. parent->_right = subRL;
  296. if (subRL)
  297. subRL->_parent = parent;
  298. Node* ppNode = parent->_parent;
  299. subR->_left = parent;
  300. parent->_parent = subR;
  301. if (parent == _root)
  302. {
  303. _root = subR;
  304. _root->_parent = nullptr;
  305. }
  306. else
  307. {
  308. if (parent == ppNode->_left)
  309. {
  310. ppNode->_left = subR;
  311. }
  312. else
  313. {
  314. ppNode->_right = subR;
  315. }
  316. subR->_parent = ppNode;
  317. }
  318. }
  319. //右旋
  320. void RotateR(Node* parent)
  321. {
  322. Node* subL = parent->_left;
  323. Node* subLR = subL->_right;
  324. parent->_left = subLR;
  325. if (subLR)
  326. subLR->_parent = parent;
  327. Node* ppNode = parent->_parent;
  328. subL->_right = parent;
  329. parent->_parent = subL;
  330. if (parent == _root)
  331. {
  332. _root = subL;
  333. _root->_parent = nullptr;
  334. }
  335. else
  336. {
  337. if (ppNode->_left == parent)
  338. {
  339. ppNode->_left = subL;
  340. }
  341. else
  342. {
  343. ppNode->_right = subL;
  344. }
  345. subL->_parent = ppNode;
  346. }
  347. }
  348. iterator Find(const K& key)
  349. {
  350. Node* cur = _root;
  351. KeyOfT kot;
  352. while (cur)
  353. {
  354. if (kot(cur->_data) < key)
  355. {
  356. cur = cur->_right;
  357. }
  358. else if (kot(cur->_data) > key)
  359. {
  360. cur = cur->_left;
  361. }
  362. else
  363. {
  364. return iterator(cur);
  365. }
  366. }
  367. return End();
  368. }
  369. private:
  370. Node* _root = nullptr;
  371. };
  372. 层序遍历
  373. //vector<vector<int>> levelOrder()
  374. //{
  375. // cout << "层序遍历:" << endl;
  376. // vector<vector<int>> vv;
  377. // if (_root == nullptr)
  378. // return vv;
  379. //
  380. // queue<Node*> q;
  381. // int levelSize = 1;
  382. // q.push(_root);
  383. //
  384. // while (!q.empty())
  385. // {
  386. //
  387. // // levelSize控制一层一层出
  388. // vector<int> levelV;
  389. // while (levelSize--)
  390. // {
  391. // Node* front = q.front();
  392. // q.pop();
  393. // levelV.push_back(front->_kv.first);
  394. // if (front->_left)
  395. // q.push(front->_left);
  396. //
  397. // if (front->_right)
  398. // q.push(front->_right);
  399. // }
  400. // vv.push_back(levelV);
  401. // for (auto e : levelV)
  402. // {
  403. // cout << e << " ";
  404. // }
  405. // cout << endl;
  406. //
  407. // // 上一层出完,下一层就都进队列
  408. // levelSize = q.size();
  409. // }
  410. //
  411. // return vv;
  412. //}
  413. //
  414. //
  415. 求最长路径
  416. //int _maxHeight(Node* root)
  417. //{
  418. // if (root == nullptr)
  419. // return 0;
  420. //
  421. // int lh = _maxHeight(root->_left);
  422. // int rh = _maxHeight(root->_right);
  423. //
  424. // return lh > rh ? lh + 1 : rh + 1;
  425. //}
  426. 求最短路径
  427. //int _minHeight(Node* root)
  428. //{
  429. // if (root == nullptr)
  430. // return 0;
  431. //
  432. // int lh = _minHeight(root->_left);
  433. // int rh = _minHeight(root->_right);
  434. //
  435. // return lh < rh ? lh + 1 : rh + 1;
  436. //}
  437. 1.中序遍历(递归版)
  438. //void _InOrder(Node* root)
  439. //{
  440. // if (root == nullptr)
  441. // return;
  442. //
  443. // _InOrder(root->_left);
  444. // cout << root->_kv.first << " ";
  445. // _InOrder(root->_right);
  446. //}
  447. 2.前序遍历(递归版)
  448. //void _PrevOrder(Node* root)
  449. //{
  450. // if (root == nullptr)
  451. // return;
  452. //
  453. // cout << root->_kv.first << " ";
  454. // _PrevOrder(root->_left);
  455. // _PrevOrder(root->_right);
  456. //}
  457. 3.后序遍历(递归版)
  458. //void _PostOrder(Node* root)
  459. //{
  460. // if (root == nullptr)
  461. // return;
  462. //
  463. // _PostOrder(root->_left);
  464. // _PostOrder(root->_right);
  465. // cout << root->_kv.first << " ";
  466. //}
  467. 判断是否为有效红黑树
  468. //bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
  469. //{
  470. // //走到null之后,判断k和black是否相等
  471. // if (nullptr == pRoot)
  472. // {
  473. // if (k != blackCount)
  474. // {
  475. // cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;
  476. // return false;
  477. // }
  478. // return true;
  479. // }
  480. //
  481. // // 统计黑色节点的个数
  482. // if (BLACK == pRoot->_col)
  483. // k++;
  484. //
  485. // // 检测当前节点与其双亲是否都为红色
  486. // if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
  487. // {
  488. // cout << "违反性质三:存在连在一起的红色节点" << endl;
  489. // return false;
  490. // }
  491. //
  492. // return _IsValidRBTree(pRoot->_left, k, blackCount) &&
  493. // _IsValidRBTree(pRoot->_right, k, blackCount);
  494. //}
  495. //
  496. //public:
  497. // //遍历
  498. // void InOrder()
  499. // {
  500. // cout << "中序遍历:";
  501. // _InOrder(_root);
  502. // cout << endl;
  503. // }
  504. // void PrevOrder()
  505. // {
  506. // cout << "前序遍历:";
  507. // _PrevOrder(_root);
  508. // cout << endl;
  509. // }
  510. // void PostOrder()
  511. // {
  512. // cout << "后序遍历:";
  513. // _PostOrder(_root);
  514. // cout << endl;
  515. // }
  516. //
  517. // void Height()
  518. // {
  519. // cout << "最长路径:" << _maxHeight(_root) << endl;
  520. // cout << "最短路径:" << _minHeight(_root) << endl;
  521. // }
  522. //
  523. // bool IsBalanceTree()
  524. // {
  525. // // 检查红黑树几条规则
  526. //
  527. // Node* pRoot = _root;
  528. // // 空树也是红黑树
  529. // if (nullptr == pRoot)
  530. // return true;
  531. //
  532. // // 检测根节点是否满足情况
  533. // if (BLACK != pRoot->_col)
  534. // {
  535. // cout << "违反红黑树性质二:根节点必须为黑色" << endl;
  536. // return false;
  537. // }
  538. //
  539. // // 获取任意一条路径中黑色节点的个数 -- 比较基准值
  540. // size_t blackCount = 0;
  541. // Node* pCur = pRoot;
  542. // while (pCur)
  543. // {
  544. // if (BLACK == pCur->_col)
  545. // blackCount++;
  546. //
  547. // pCur = pCur->_left;
  548. // }
  549. //
  550. // // 检测是否满足红黑树的性质,k用来记录路径中黑色节点的个数
  551. // size_t k = 0;
  552. // return _IsValidRBTree(pRoot, k, blackCount);
  553. // }

(3)test.cpp:

  1. #include"map.h"
  2. int main()
  3. {
  4. //my::test_map1();
  5. my::test_map2();
  6. //my::test_map3();
  7. return 0;
  8. }

4.set的模拟实现

set的底层为红黑树,因此只需在set内部封装一棵红黑树,即可将该容器实现出来(具体实现可参 考map)。
  1. namespace bite
  2. {
  3. template<class K>
  4. class set
  5. {
  6. typedef K ValueType;
  7. // 作用是:将value中的key提取出来
  8. struct KeyOfValue
  9. {
  10. const K& operator()(const ValueType& key)
  11. {
  12. return key;
  13. }
  14. };
  15. // 红黑树类型重命名
  16. typedef RBTree<K, ValueType, KeyOfValue> RBTree;
  17. public:
  18. typedef typename RBTree::Iterator iterator;
  19. public:
  20. Set() {}
  21. /
  22. // Iterator
  23. iterator Begin();
  24. iterator End();
  25. /
  26. // Capacity
  27. size_t size()const;
  28. bool empty()const;
  29. // modify
  30. pair<iterator, bool> insert(const ValueType& data)
  31. {
  32. return _t.Insert(data);
  33. }
  34. void clear();
  35. iterator find(const K& key);
  36. private:
  37. RBTree _t;
  38. };
  39. }

附用红黑树:

(1)set.h:

  1. #pragma once
  2. #include "RBTree.h"
  3. namespace my
  4. {
  5. template<class K>
  6. class set
  7. {
  8. struct SetKeyOfT
  9. {
  10. const K& operator()(const K& key)
  11. {
  12. return key;
  13. }
  14. };
  15. public:
  16. typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
  17. typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
  18. iterator begin() const
  19. {
  20. return _t.Begin();
  21. }
  22. iterator end() const
  23. {
  24. return _t.End();
  25. }
  26. pair<iterator, bool> insert(const K& key)
  27. {
  28. //pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
  29. auto ret = _t.Insert(key);
  30. return pair<iterator, bool>(iterator(ret.first._node), ret.second);
  31. }
  32. iterator find(const K& key)
  33. {
  34. return _t.Find(key);
  35. }
  36. private:
  37. RBTree<K, K, SetKeyOfT> _t;
  38. };
  39. void test_set1()
  40. {
  41. set<int> s;
  42. s.insert(8);
  43. s.insert(6);
  44. s.insert(11);
  45. s.insert(5);
  46. s.insert(6);
  47. s.insert(7);
  48. s.insert(10);
  49. s.insert(13);
  50. s.insert(12);
  51. s.insert(15);
  52. //迭代器遍历
  53. set<int>::iterator it = s.begin();
  54. while (it != s.end())
  55. {
  56. cout << *it << " ";
  57. ++it;
  58. }
  59. cout << endl;
  60. //范围for遍历
  61. for (auto e : s)
  62. {
  63. cout << e << " ";
  64. }
  65. cout << endl;
  66. }
  67. }

(2)RBTree.h:

  1. #pragma once
  2. #include<iostream>
  3. #include<vector>
  4. #include<queue>
  5. #include<cassert>
  6. using namespace std;
  7. enum Colour
  8. {
  9. RED,
  10. BLACK,
  11. };
  12. template<class T>
  13. struct RBTreeNode
  14. {
  15. RBTreeNode<T>* _left;
  16. RBTreeNode<T>* _right;
  17. RBTreeNode<T>* _parent;
  18. T _data;
  19. Colour _col;
  20. RBTreeNode(const T& data)
  21. :_data(data)
  22. , _left(nullptr)
  23. , _right(nullptr)
  24. , _parent(nullptr)
  25. , _col(RED)
  26. {}
  27. };
  28. //T决定红黑树存什么数据
  29. //set RBTree<K,K>
  30. //map RBTree<K,pair<K,V>>
  31. //KeyOfT -> 支持取出T对象中key的仿函数
  32. template<class T, class Ref, class Ptr>
  33. struct __RBTreeIterator
  34. {
  35. typedef RBTreeNode<T> Node;
  36. typedef __RBTreeIterator<T, Ref, Ptr> Self;
  37. Node* _node;
  38. __RBTreeIterator(Node* node)
  39. :_node(node)
  40. {}
  41. //运算符*重载
  42. Ref operator*()
  43. {
  44. return _node->_data;
  45. }
  46. //运算符->重载
  47. Ptr operator->()
  48. {
  49. return &_node->_data;
  50. }
  51. //重载 前置++
  52. Self& operator++()
  53. {
  54. if (_node->_right == nullptr)
  55. {
  56. // 找祖先里面,孩子是父亲左的那个
  57. Node* cur = _node;
  58. Node* parent = cur->_parent;
  59. while (parent && parent->_right == cur)
  60. {
  61. cur = cur->_parent;
  62. parent = parent->_parent;
  63. }
  64. _node = parent;
  65. }
  66. else
  67. {
  68. // 右子树的最左节点
  69. Node* subLeft = _node->_right;
  70. while (subLeft->_left)
  71. {
  72. subLeft = subLeft->_left;
  73. }
  74. _node = subLeft;
  75. }
  76. return *this;
  77. }
  78. //重载 后置++
  79. Self operator++(int)
  80. {
  81. Self tmp(*this);
  82. ++(*this);
  83. return tmp;
  84. }
  85. //重载 前置--
  86. Self& operator--()
  87. {
  88. if (_node->_left == nullptr)
  89. {
  90. // 找祖先里面,孩子是父亲
  91. Node* cur = _node;
  92. Node* parent = cur->_parent;
  93. while (parent && cur == parent->_left)
  94. {
  95. cur = cur->_parent;
  96. parent = parent->_parent;
  97. }
  98. _node = parent;
  99. }
  100. else
  101. {
  102. // 左子树的最右节点
  103. Node* subRight = _node->_left;
  104. while (subRight->_right)
  105. {
  106. subRight = subRight->_right;
  107. }
  108. _node = subRight;
  109. }
  110. return *this;
  111. }
  112. //重载 后置--
  113. Self operator--(int)
  114. {
  115. Self tmp(*this);
  116. --(*this);
  117. return tmp;
  118. }
  119. //重载 !=
  120. bool operator!=(const Self& s) const
  121. {
  122. return _node != s._node;
  123. }
  124. //重载 ==
  125. bool operator==(const Self& s) const
  126. {
  127. return _node == s->_node;
  128. }
  129. };
  130. template<class K, class T, class KeyOfT>
  131. class RBTree
  132. {
  133. typedef RBTreeNode<T> Node; //默认为私有
  134. public:
  135. typedef __RBTreeIterator<T, T&, T*> iterator;
  136. typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
  137. // 构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的
  138. iterator Begin()
  139. {
  140. Node* subLeft = _root;
  141. while (subLeft && subLeft->_left)
  142. {
  143. subLeft = subLeft->_left;
  144. }
  145. return iterator(subLeft);
  146. }
  147. iterator End()
  148. {
  149. return iterator(nullptr);
  150. }
  151. const_iterator Begin() const
  152. {
  153. Node* subLeft = _root;
  154. while (subLeft && subLeft->_left)
  155. {
  156. subLeft = subLeft->_left;
  157. }
  158. return const_iterator(subLeft);
  159. }
  160. const_iterator End() const
  161. {
  162. return const_iterator(nullptr);
  163. }
  164. //insert数据
  165. pair<iterator, bool> Insert(const T& data)
  166. {
  167. // 1、搜索树的规则插入
  168. // 2、看是否违反平衡规则,如果违反就需要处理:旋转
  169. if (_root == nullptr)
  170. {
  171. _root = new Node(data);
  172. _root->_col = BLACK;
  173. return make_pair(iterator(_root), true);
  174. }
  175. KeyOfT kot;
  176. Node* parent = nullptr;
  177. Node* cur = _root;
  178. while (cur)
  179. {
  180. if (kot(cur->_data) < kot(data))
  181. {
  182. parent = cur;
  183. cur = cur->_right;
  184. }
  185. else if (kot(cur->_data) > kot(data))
  186. {
  187. parent = cur;
  188. cur = cur->_left;
  189. }
  190. else
  191. {
  192. return make_pair(iterator(cur), true);
  193. }
  194. }
  195. cur = new Node(data);
  196. Node* newnode = cur;
  197. cur->_col = RED;
  198. if (kot(parent->_data) < kot(data))
  199. {
  200. parent->_right = cur;
  201. }
  202. else
  203. {
  204. parent->_left = cur;
  205. }
  206. cur->_parent = parent;
  207. // 存在连续红色节点
  208. while (parent && parent->_col == RED)
  209. {
  210. Node* grandfater = parent->_parent;
  211. assert(grandfater);
  212. if (grandfater->_left == parent)
  213. {
  214. Node* uncle = grandfater->_right;
  215. // 情况一:
  216. if (uncle && uncle->_col == RED) // 叔叔存在且为红
  217. {
  218. // 变色
  219. parent->_col = uncle->_col = BLACK;
  220. grandfater->_col = RED;
  221. // 继续往上处理
  222. cur = grandfater;
  223. parent = cur->_parent;
  224. }
  225. else // 叔叔不存在 或者 叔叔存在且为黑
  226. {
  227. if (cur == parent->_left) // 单旋
  228. {
  229. // g
  230. // p
  231. // c
  232. RotateR(grandfater);
  233. parent->_col = BLACK;
  234. grandfater->_col = RED;
  235. }
  236. else // 双旋
  237. {
  238. // g
  239. // p
  240. // c
  241. RotateL(parent);
  242. RotateR(grandfater);
  243. cur->_col = BLACK;
  244. grandfater->_col = RED;
  245. }
  246. break;
  247. }
  248. }
  249. else //(grandfater->_right == parent)
  250. {
  251. Node* uncle = grandfater->_left;
  252. // 情况一:
  253. if (uncle && uncle->_col == RED)
  254. {
  255. // 变色
  256. parent->_col = uncle->_col = BLACK;
  257. grandfater->_col = RED;
  258. // 继续往上处理
  259. cur = grandfater;
  260. parent = cur->_parent;
  261. }
  262. else
  263. {
  264. if (cur == parent->_right)
  265. {
  266. // g
  267. // p
  268. // c
  269. RotateL(grandfater);
  270. parent->_col = BLACK;
  271. grandfater->_col = RED;
  272. }
  273. else // 双旋
  274. {
  275. // g
  276. // p
  277. // c
  278. RotateR(parent);
  279. RotateL(grandfater);
  280. cur->_col = BLACK;
  281. grandfater->_col = RED;
  282. }
  283. break;
  284. }
  285. }
  286. }
  287. _root->_col = BLACK;
  288. return make_pair(iterator(newnode), true);
  289. }
  290. //左旋
  291. void RotateL(Node* parent)
  292. {
  293. Node* subR = parent->_right;
  294. Node* subRL = subR->_left;
  295. parent->_right = subRL;
  296. if (subRL)
  297. subRL->_parent = parent;
  298. Node* ppNode = parent->_parent;
  299. subR->_left = parent;
  300. parent->_parent = subR;
  301. if (parent == _root)
  302. {
  303. _root = subR;
  304. _root->_parent = nullptr;
  305. }
  306. else
  307. {
  308. if (parent == ppNode->_left)
  309. {
  310. ppNode->_left = subR;
  311. }
  312. else
  313. {
  314. ppNode->_right = subR;
  315. }
  316. subR->_parent = ppNode;
  317. }
  318. }
  319. //右旋
  320. void RotateR(Node* parent)
  321. {
  322. Node* subL = parent->_left;
  323. Node* subLR = subL->_right;
  324. parent->_left = subLR;
  325. if (subLR)
  326. subLR->_parent = parent;
  327. Node* ppNode = parent->_parent;
  328. subL->_right = parent;
  329. parent->_parent = subL;
  330. if (parent == _root)
  331. {
  332. _root = subL;
  333. _root->_parent = nullptr;
  334. }
  335. else
  336. {
  337. if (ppNode->_left == parent)
  338. {
  339. ppNode->_left = subL;
  340. }
  341. else
  342. {
  343. ppNode->_right = subL;
  344. }
  345. subL->_parent = ppNode;
  346. }
  347. }
  348. iterator Find(const K& key)
  349. {
  350. Node* cur = _root;
  351. KeyOfT kot;
  352. while (cur)
  353. {
  354. if (kot(cur->_data) < key)
  355. {
  356. cur = cur->_right;
  357. }
  358. else if (kot(cur->_data) > key)
  359. {
  360. cur = cur->_left;
  361. }
  362. else
  363. {
  364. return iterator(cur);
  365. }
  366. }
  367. return End();
  368. }
  369. private:
  370. Node* _root = nullptr;
  371. };
  372. 层序遍历
  373. //vector<vector<int>> levelOrder()
  374. //{
  375. // cout << "层序遍历:" << endl;
  376. // vector<vector<int>> vv;
  377. // if (_root == nullptr)
  378. // return vv;
  379. //
  380. // queue<Node*> q;
  381. // int levelSize = 1;
  382. // q.push(_root);
  383. //
  384. // while (!q.empty())
  385. // {
  386. //
  387. // // levelSize控制一层一层出
  388. // vector<int> levelV;
  389. // while (levelSize--)
  390. // {
  391. // Node* front = q.front();
  392. // q.pop();
  393. // levelV.push_back(front->_kv.first);
  394. // if (front->_left)
  395. // q.push(front->_left);
  396. //
  397. // if (front->_right)
  398. // q.push(front->_right);
  399. // }
  400. // vv.push_back(levelV);
  401. // for (auto e : levelV)
  402. // {
  403. // cout << e << " ";
  404. // }
  405. // cout << endl;
  406. //
  407. // // 上一层出完,下一层就都进队列
  408. // levelSize = q.size();
  409. // }
  410. //
  411. // return vv;
  412. //}
  413. //
  414. //
  415. 求最长路径
  416. //int _maxHeight(Node* root)
  417. //{
  418. // if (root == nullptr)
  419. // return 0;
  420. //
  421. // int lh = _maxHeight(root->_left);
  422. // int rh = _maxHeight(root->_right);
  423. //
  424. // return lh > rh ? lh + 1 : rh + 1;
  425. //}
  426. 求最短路径
  427. //int _minHeight(Node* root)
  428. //{
  429. // if (root == nullptr)
  430. // return 0;
  431. //
  432. // int lh = _minHeight(root->_left);
  433. // int rh = _minHeight(root->_right);
  434. //
  435. // return lh < rh ? lh + 1 : rh + 1;
  436. //}
  437. 1.中序遍历(递归版)
  438. //void _InOrder(Node* root)
  439. //{
  440. // if (root == nullptr)
  441. // return;
  442. //
  443. // _InOrder(root->_left);
  444. // cout << root->_kv.first << " ";
  445. // _InOrder(root->_right);
  446. //}
  447. 2.前序遍历(递归版)
  448. //void _PrevOrder(Node* root)
  449. //{
  450. // if (root == nullptr)
  451. // return;
  452. //
  453. // cout << root->_kv.first << " ";
  454. // _PrevOrder(root->_left);
  455. // _PrevOrder(root->_right);
  456. //}
  457. 3.后序遍历(递归版)
  458. //void _PostOrder(Node* root)
  459. //{
  460. // if (root == nullptr)
  461. // return;
  462. //
  463. // _PostOrder(root->_left);
  464. // _PostOrder(root->_right);
  465. // cout << root->_kv.first << " ";
  466. //}
  467. 判断是否为有效红黑树
  468. //bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
  469. //{
  470. // //走到null之后,判断k和black是否相等
  471. // if (nullptr == pRoot)
  472. // {
  473. // if (k != blackCount)
  474. // {
  475. // cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;
  476. // return false;
  477. // }
  478. // return true;
  479. // }
  480. //
  481. // // 统计黑色节点的个数
  482. // if (BLACK == pRoot->_col)
  483. // k++;
  484. //
  485. // // 检测当前节点与其双亲是否都为红色
  486. // if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
  487. // {
  488. // cout << "违反性质三:存在连在一起的红色节点" << endl;
  489. // return false;
  490. // }
  491. //
  492. // return _IsValidRBTree(pRoot->_left, k, blackCount) &&
  493. // _IsValidRBTree(pRoot->_right, k, blackCount);
  494. //}
  495. //
  496. //public:
  497. // //遍历
  498. // void InOrder()
  499. // {
  500. // cout << "中序遍历:";
  501. // _InOrder(_root);
  502. // cout << endl;
  503. // }
  504. // void PrevOrder()
  505. // {
  506. // cout << "前序遍历:";
  507. // _PrevOrder(_root);
  508. // cout << endl;
  509. // }
  510. // void PostOrder()
  511. // {
  512. // cout << "后序遍历:";
  513. // _PostOrder(_root);
  514. // cout << endl;
  515. // }
  516. //
  517. // void Height()
  518. // {
  519. // cout << "最长路径:" << _maxHeight(_root) << endl;
  520. // cout << "最短路径:" << _minHeight(_root) << endl;
  521. // }
  522. //
  523. // bool IsBalanceTree()
  524. // {
  525. // // 检查红黑树几条规则
  526. //
  527. // Node* pRoot = _root;
  528. // // 空树也是红黑树
  529. // if (nullptr == pRoot)
  530. // return true;
  531. //
  532. // // 检测根节点是否满足情况
  533. // if (BLACK != pRoot->_col)
  534. // {
  535. // cout << "违反红黑树性质二:根节点必须为黑色" << endl;
  536. // return false;
  537. // }
  538. //
  539. // // 获取任意一条路径中黑色节点的个数 -- 比较基准值
  540. // size_t blackCount = 0;
  541. // Node* pCur = pRoot;
  542. // while (pCur)
  543. // {
  544. // if (BLACK == pCur->_col)
  545. // blackCount++;
  546. //
  547. // pCur = pCur->_left;
  548. // }
  549. //
  550. // // 检测是否满足红黑树的性质,k用来记录路径中黑色节点的个数
  551. // size_t k = 0;
  552. // return _IsValidRBTree(pRoot, k, blackCount);
  553. // }

(3)test.cpp:

  1. #include"set.h"
  2. int main()
  3. {
  4. my::test_set1();
  5. return 0;
  6. }

后记:
●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教!

                                                                       ——By 作者:新晓·故知

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/991914
推荐阅读
相关标签
  

闽ICP备14008679号