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. //1.先看树中，kv是否存在 12. Node* parent = nullptr; 13. Node* cur = _root; 14. while (cur) 15. { 16. if (cur->_kv.first < kv.first) 17. { 18. //kv比当前节点值大，向右走 19. parent = cur; 20. cur = cur->_right; 21. } 22. else if (cur->_kv.first > kv.first) 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->_kv.first < kv.first) 39. { 40. //kv比parent值大，插入到parent的右边 41. parent->_right = newNode; 42. cur->_parent = parent; 43. } 44. else 45. { 46. //kv比parent值小，插入到parent的左边 47. parent->_left = newNode; 48. cur->_parent = parent; 49. } 50. cur = newNode; 51. 52. //如果父亲存在，且父亲颜色为红就要处理 53. while (parent && parent->_col == RED) 54. { 55. //关键看叔叔 56. Node* grandfather = parent->_parent; 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. }
五、红黑树查找
查找比较简单，递归向左走或向右走：
1. //查找 2. Node* Find(const K& key) 3. { 4. Node* cur = _root; 5. while (cur) 6. { 7. if (cur->_kv.first < key)//key比当前节点小，就向右查找 8. { 9. cur = cur->_right; 10. } 11. else if (cur->_kv.first > key)//key比当前节点大，就向左查找 12. { 13. cur = cur->_left; 14. } 15. else//找到了 16. { 17. return cur; 18. } 19. } 20. return nullptr;//空树，直接返回 21. }
六、红黑树检查是否平衡
检查是否平衡还是要用到递归子函数
（1）需要判断是否满足红黑树的4条性质
（2）计算最左路径上的黑色节点个数，递归路径时，需要计算该条路径上的黑色节点个数是否和最左路径上的节点个数相等
1. bool _CheckBalance(Node* root, int blackNum, int count) 2. { 3. if (root == nullptr) 4. { 5. if (count != blackNum) 6. { 7. cout << "黑色节点数量不相等" << endl; 8. return false; 9. } 10. return true; 11. } 12. 13. if (root->_col == RED && root->_parent->_col == RED) 14. { 15. cout << "存在连续红色节点" << endl; 16. return false; 17. } 18. 19. if (root->_col == BLACK) 20. { 21. count++; 22. } 23. 24. return _CheckBalance(root->_left, blackNum, count) 25. && _CheckBalance(root->_right, blackNum, count); 26. } 27. 28. //检查是否平衡 29. bool CheckBlance() 30. { 31. if (_root == nullptr) 32. { 33. return true; 34. } 35. 36. if (_root->_col == RED) 37. { 38. cout << "根节点为红色" << endl; 39. return false; 40. } 41. 42. //找最左路径做黑色节点数量参考值 43. int blackNum = 0; 44. Node* left = _root; 45. while (left) 46. { 47. if (left->_col == BLACK) 48. { 49. blackNum++; 50. } 51. left = left->_left; 52. } 53. 54. int count = 0; 55. return _CheckBlance(_root, blackNum, count); 56. }
对于以下红黑树，递归过程如下：
七、红黑树遍历
遍历也很简单，中序递归遍历左子树和右子树：
1. //遍历 2. void _InOrder(Node* root) 3. { 4. if (root == nullptr) 5. { 6. return; 7. } 8. 9. _InOrder(root->_left); 10. cout << root->_kv.first << ":" << root->_kv.second << endl; 11. _InOrder(root->_right); 12. } 13. 14. void InOrder() 15. { 16. _InOrder(_root); 17. cout << endl; 18. }
八、红黑树验证
1. #include "RedBlackTree.h" 2. 3. void TestRBTree() 4. { 5. //,1,3,5,15,7,16,14 6. int a[] = { 4,2,6,1,3,5,15,7,16 }; 7. RBTree<int, int> t; 8. for (auto e : a) 9. { 10. t.Insert(make_pair(e, e)); 11. } 12. 13. t.InOrder(); 14. //cout << t.CheckBalance() << endl; 15. } 16. 17. int main() 18. { 19. TestRBTree(); 20. return 0; 21. }
插入成功：
