深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构】手撕红黑树

2023-03-14

node cur _col
目录一、红黑树简介1、红黑树的简介2、红黑树的性质二、红黑树的插入（看叔叔的颜色就行）1、为什么新插入的节点必须给红色？2、插入红色节点后，判定红黑树性质是否被破坏2.1情况一：uncle存在且为红2.2情况二：uncle不存在/存在且为黑（直线）2.3情况三：uncle不存在/存在且为黑（折线）2

目录

一、红黑树简介

1、红黑树的简介

2、红黑树的性质

二、红黑树的插入（看叔叔的颜色就行）

1、为什么新插入的节点必须给红色？

2、插入红色节点后，判定红黑树性质是否被破坏

2.1情况一：uncle存在且为红

2.2情况二：uncle不存在/存在且为黑（直线）

2.3情况三：uncle不存在/存在且为黑（折线）

2.4总结

3、红黑树插入代码

三、红黑树的平衡检测

四、红黑树整体代码

一、红黑树简介

1、红黑树的简介

红黑树和AVL树一样，因其逻辑复杂，面试时现场要求手撕就是纯纯刁难面试者。但某大厂面试官曾要求某些求职者现场手撕红黑树（我赌5毛，让面试官撕，他也撕不出来，而且你家员工上班手搓红黑树啊？），随后求职遭遇被发到网上吐槽，这便有了“手撕红黑树”的梗，也让红黑树成为了知名度最高的数据结构。（话虽如此，对于红黑树的性质、插入思想等概念还是需要掌握的）

2、红黑树的性质

红黑树本质也是一种二叉搜索树。底层结构需要使用二叉搜索树的地方，基本上都会使用红黑树来实现，而AVL树也因此坐上了冷板凳。

红黑树通过在每个节点上添加一个存储位，用于存储“RED”或“BLACK”。通过节点上红/黑颜色限制，确保最长路径不超过最短路径的两倍，因而它是接近平衡的树形结构。最短路径：全黑；最长路径：一黑一红交替。

1、红黑树的根节点是黑色的；

2、没有连续的红色节点（如果某个节点为红色，则它的左右孩子必须是黑色）

3、无论哪个节点，其每条路径的黑色节点数量相同；

4、所有的空节点（NIL节点）可以认为是黑色的。

最优情况：全黑或每条路径都是一黑一红的满二叉树，高度logN

最差情况：每颗子树左子树全黑，右子树一黑一红。高度2*logN。

可以发现，最坏情况的时间复杂度和AVL树一样，都是O(logN)，但是红黑树这种近似平衡的结构减少了大量旋转，综合性能优于AVL树。

二、红黑树的插入（看叔叔的颜色就行）

1、为什么新插入的节点必须给红色？

新节点给红色，可能会违反上面说的红黑树性质2；如果新节点给黑色，必定会违反性质3。

2、插入红色节点后，判定红黑树性质是否被破坏

情况一调整后可能变成情况一、情况二、情况三。

2.1情况一：uncle存在且为红

这种情况cur、parent、grandfather都是确定颜色的，唯独uncle的颜色是不确定的。

可以这么想：cur为红那么就需要将parent变为黑；parent变黑需要控制每条路径上黑节点的数量相同，那么就要把uncle变黑；如果grandfather不是根，需要反转为红，用以控制路径黑节点数量相同。继续向上调整即可。

2.2情况二：uncle不存在/存在且为黑（直线）

uncle的情况分两种。

uncle不存在，则cur为插入节点，单旋即可。

uncle存在且为黑是第一种情况变过来的。

2.3情况三：uncle不存在/存在且为黑（折线）

uncle的情况分两种。

uncle不存在，则cur为插入节点，两次单旋即可。

uncle存在且为黑，先掰直

2.4总结

插入新节点时，父节点为红，看叔叔的颜色。

1、叔叔存在且为红，变色，向上调整（可能变为三种情况中的任意一种）

2、叔叔不存在/存在且为黑，直线。单旋+变色

3、叔叔不存在/存在且为黑，折线，两次单旋+变色

3、红黑树插入代码

  1. bool Insert(const pair<K,V>& kv)
  2. {
  3.     if (_root == nullptr)
  4.     {
  5.         _root = new Node(kv);
  6.         _root->_col = BLACK;//根节点给黑色
  7.         return true;
  8.     }
  9.     //_root不为空
  10.     Node* parent = nullptr;
  11.     Node* cur = _root;
  12.     while (cur)
  13.     {
  14.         if (cur->_kv.first < kv.first)
  15.         {
  16.             parent = cur;
  17.             cur = cur->_right;
  18.         }
  19.         else if (cur->_kv.first > kv.first)
  20.         {
  21.             parent = cur;
  22.             cur = cur->_left;
  23.         }
  24.         else//相等说明元素相同，插入失败
  25.             return false;
  26.     }
  27.     //开始插入
  28.     cur = new Node(kv);
  29.     cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。  
  30.     if (parent->_kv.first < kv.first)
  31.     {
  32.         parent->_right = cur;
  33.         cur->_parent = parent;//维护cur的父指针
  34.     }
  35.     else
  36.     {
  37.         parent->_left = cur;
  38.         cur->_parent = parent;
  39.     }
  40.     //调整
  41.     while (parent&&parent->_col == RED)
  42.     {
  43.         Node* grandfather = parent->_parent;//找到祖父
  44.         if (grandfather->_left == parent)//如果父亲是祖父的左孩子
  45.         {
  46.             Node* uncle = grandfather->_right;//找到叔叔
  47.             //情况一：叔叔存在且为红
  48.             if (uncle != nullptr && uncle->_col == RED)
  49.             {
  50.                 //变色
  51.                 parent->_col = uncle->_col = BLACK;
  52.                 grandfather->_col = RED;
  53.                 
  54.                 cur = grandfather;
  55.                 parent = cur->_parent;
  56.             }
  57.             else//情况二或情况三
  58.             {
  59.                 if (cur == parent->_left)//情况二，直线
  60.                 {
  61.                     RotateRight(grandfather);//右单旋
  62.                     parent->_col = BLACK;
  63.                     grandfather->_col = RED;
  64.                 }
  65.                 else//情况三，折线
  66.                 {
  67.                     RotateLeft(parent);//左单旋
  68.                     RotateRight(grandfather);//右单旋
  69.                     cur->_col = BLACK;
  70.                     grandfather->_col = RED;
  71.                 }
  72.                 break;
  73.             }
  74.         }
  75.         else//如果父亲是祖父的右孩子
  76.         {
  77.             Node* uncle = grandfather->_left;
  78.             if (uncle != nullptr && uncle->_col == RED)
  79.             {
  80.                 parent->_col =uncle->_col= BLACK;
  81.                 grandfather->_col = RED; 
  82.  
  83.                 cur = grandfather;
  84.                 parent = cur->_parent;
  85.             }
  86.             else
  87.             {
  88.                 if (cur == parent->_right)//情况二，直线
  89.                 {
  90.                     //g
  91.                     //  p
  92.                     //    c
  93.                     RotateLeft(grandfather);//左单旋
  94.                     parent->_col = BLACK;
  95.                     grandfather->_col = RED;
  96.                 }
  97.                 else//情况三，折线
  98.                 {
  99.                     //g
  100.                     //  p
  101.                     //c   
  102.                     RotateRight(parent);//右单旋
  103.                     RotateLeft(grandfather);//左单旋
  104.                     cur->_col = BLACK;
  105.                     grandfather->_col = RED;
  106.                 }
  107.                 break;
  108.             }
  109.         }
  110.     }
  111.     _root->_col=BLACK;
  112.     return true;
  113. }

三、红黑树的平衡检测

  1. bool Check(Node* root,int blackNum,const int ref)//检查有没有连续红节点
  2. {
  3.     if (root == nullptr)
  4.     {
  5.         if (blackNum != ref)
  6.         {
  7.             cout << "路径上黑节点数量不一致" << endl;
  8.             return false;
  9.         }
  10.         return true;
  11.     }
  12.     if (root->_col == BLACK)
  13.     {
  14.         ++blackNum;
  15.     }
  16.  
  17.     if (root->_col == RED && root->_parent->_col == RED)
  18.     {
  19.         cout << "违反规则，父子均为红" << endl;
  20.         return false;
  21.     }
  22.     return Check(root->_left, blackNum,ref) && Check(root->_right, blackNum, ref);
  23. }
  24. bool _IsBalance()
  25. {
  26.     if (_root == nullptr)
  27.         return true;
  28.     if (_root->_col != BLACK)
  29.     {
  30.         return false;
  31.     }
  32.     //数一下一条路径黑色节点数量
  33.     int ref = 0;//统计一条路上黑色节点的数量
  34.     Node* left = _root;
  35.     while (left != nullptr)
  36.     {
  37.         if (left->_col == BLACK)
  38.         {
  39.             ++ref;
  40.         }
  41.         left = left->_left;
  42.     }
  43.     return Check(_root,0,ref);
  44. }

1、在_IsBalance中确定号一条路径中黑色节点的数量，作为参数传递给Check函数，Check函数需要在递归至根节点时，统计，每条路径黑色节点数量是否和基准值ref相等。

2、Check函数中还需要判断：子节点为红，父节点也为红（此时不平衡）

四、红黑树整体代码

  1. #pragma once
  2. #include <iostream>
  3. #include <map>
  4. #include <set>
  5. #include <string>
  6. using namespace std;
  7. enum Color
  8. {
  9. RED,
  10. BLACK,
  11. };
  12. template <class K,class V>
  13. struct RBTreeNode
  14. {
  15. RBTreeNode(const pair<K,V>& kv)
  16. :_parent(nullptr)
  17. ,_left(nullptr)
  18. ,_right(nullptr)
  19. ,_kv(kv)
  20. ,_col(RED)
  21. {}
  22. RBTreeNode<K,V>* _parent;
  23. RBTreeNode<K, V>* _left;
  24. RBTreeNode<K, V>* _right;
  25. pair<K, V> _kv;
  26. Color _col;
  27. };
  28. template <class K, class V>
  29. class RBTree
  30. {
  31. public:
  32. typedef RBTreeNode<K,V> Node;
  33. bool Insert(const pair<K,V>& kv)
  34. {
  35. if (_root == nullptr)
  36. {
  37. _root = new Node(kv);
  38. _root->_col = BLACK;//根节点给黑色
  39. return true;
  40. }
  41. //_root不为空
  42. Node* parent = nullptr;
  43. Node* cur = _root;
  44. while (cur)
  45. {
  46. if (cur->_kv.first < kv.first)
  47. {
  48. parent = cur;
  49. cur = cur->_right;
  50. }
  51. else if (cur->_kv.first > kv.first)
  52. {
  53. parent = cur;
  54. cur = cur->_left;
  55. }
  56. else//相等说明元素相同，插入失败
  57. return false;
  58. }
  59. //开始插入
  60. cur = new Node(kv);
  61. cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。  
  62. if (parent->_kv.first < kv.first)
  63. {
  64. parent->_right = cur;
  65. cur->_parent = parent;//维护cur的父指针
  66. }
  67. else
  68. {
  69. parent->_left = cur;
  70. cur->_parent = parent;
  71. }
  72. //调整
  73. while (parent&&parent->_col == RED)
  74. {
  75. Node* grandfather = parent->_parent;//找到祖父
  76. if (grandfather->_left == parent)//如果父亲是祖父的左孩子
  77. {
  78. Node* uncle = grandfather->_right;//找到叔叔
  79. //情况一：叔叔存在且为红
  80. if (uncle != nullptr && uncle->_col == RED)
  81. {
  82. //变色
  83. parent->_col = uncle->_col = BLACK;
  84. grandfather->_col = RED;
  86. cur = grandfather;
  87. parent = cur->_parent;
  88. }
  89. else//情况二或情况三
  90. {
  91. if (cur == parent->_left)//情况二，直线
  92. {
  93. RotateRight(grandfather);//右单旋
  94. parent->_col = BLACK;
  95. grandfather->_col = RED;
  96. }
  97. else//情况三，折线
  98. {
  99. RotateLeft(parent);//左单旋
  100. RotateRight(grandfather);//右单旋
  101. cur->_col = BLACK;
  102. grandfather->_col = RED;
  103. }
  104. break;
  105. }
  106. }
  107. else//如果父亲是祖父的右孩子
  108. {
  109. Node* uncle = grandfather->_left;
  110. if (uncle != nullptr && uncle->_col == RED)
  111. {
  112. parent->_col =uncle->_col= BLACK;
  113. grandfather->_col = RED; 
  114.  
  115. cur = grandfather;
  116. parent = cur->_parent;
  117. }
  118. else
  119. {
  120. if (cur == parent->_right)//情况二，直线
  121. {
  122. //g
  123. //  p
  124. //    c
  125. RotateLeft(grandfather);//左单旋
  126. parent->_col = BLACK;
  127. grandfather->_col = RED;
  128. }
  129. else//情况三，折线
  130. {
  131. //g
  132. //  p
  133. //c   
  134. RotateRight(parent);//右单旋
  135. RotateLeft(grandfather);//左单旋
  136. cur->_col = BLACK;
  137. grandfather->_col = RED;
  138. }
  139. break;
  140. }
  141. }
  142. }
  143. _root->_col=BLACK;
  144. return true;
  145. }
  146. void Inorder()
  147. {
  148. _Inorder(_root);
  149. }
  150. bool IsBalance()
  151. {
  152. return _IsBalance();
  153. }
  154. private:
  155. void _Inorder(Node* root)
  156. {
  157. if (root == nullptr)
  158. return;
  159.  
  160. _Inorder(root->_left);
  161. cout << root->_kv.first << ":" << root->_kv.second << endl;
  162. _Inorder(root->_right);
  163. }
  164. bool Check(Node* root,int blackNum,const int ref)//检查有没有连续红节点
  165. {
  166. if (root == nullptr)
  167. {
  168. if (blackNum != ref)
  169. {
  170. cout << "路径上黑节点数量不一致" << endl;
  171. return false;
  172. }
  173. return true;
  174. }
  175. if (root->_col == BLACK)
  176. {
  177. ++blackNum;
  178. }
  179.  
  180. if (root->_col == RED && root->_parent->_col == RED)
  181. {
  182. cout << "违反规则，父子均为红" << endl;
  183. return false;
  184. }
  185. return Check(root->_left, blackNum,ref) && Check(root->_right, blackNum, ref);
  186. }
  187. bool _IsBalance()
  188. {
  189. if (_root == nullptr)
  190. return true;
  191. if (_root->_col != BLACK)
  192. {
  193. return false;
  194. }
  195. //数一下一条路径黑色节点数量
  196. int ref = 0;//统计一条路上黑色节点的数量
  197. Node* left = _root;
  198. while (left != nullptr)
  199. {
  200. if (left->_col == BLACK)
  201. {
  202. ++ref;
  203. }
  204. left = left->_left;
  205. }
  206. return Check(_root,0,ref);
  207. }
  208. void RotateLeft(Node* parent)//左单旋
  209. {
  210. Node* grandfather = parent->_parent;
  211. Node* cur = parent->_right;
  212. if (parent == _root)
  213. {
  214. _root = cur;
  215. cur->_parent = nullptr;
  216. }
  217. else
  218. {
  219. if (grandfather->_left == parent)//需要判定parent原来属于grandfather的哪一边
  220. grandfather->_left = cur;
  221. else
  222. grandfather->_right = cur;
  223. cur->_parent = grandfather;
  224. }
  225. parent->_right = cur->_left;
  226. if (cur->_left != nullptr)
  227. cur->_left->_parent = parent;
  228. cur->_left = parent;
  229. parent->_parent = cur;
  230. }
  231. void RotateRight(Node* parent)//右单旋
  232. {
  233. Node* grandfather = parent->_parent;
  234. Node* cur = parent->_left;
  235. if (parent == _root)
  236. {
  237. _root = cur;
  238. cur->_parent = nullptr;
  239. }
  240. else
  241. {
  242. if (grandfather->_left == parent)
  243. {
  244. grandfather->_left = cur;
  245. cur->_parent = grandfather;
  246. }
  247. else
  248. {
  249. grandfather->_right = cur;
  250. cur->_parent = grandfather;
  251. }
  252. }
  253. parent->_parent = cur;
  254. parent->_left = cur->_right;
  255. if (cur->_right != nullptr)
  256. cur->_right->_parent = parent;
  257. cur->_right = parent;
  258. }
  259. private:
  260. Node* _root=nullptr;
  261. };
  262. void TestAVLTree()
  263. {
  264. //int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  265. //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  266. int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
  267. //int a[] = { 9,8,7,6,5,4,3,2,1};
  268. RBTree<int, int> t;
  269. for (auto e : a)
  270. {
  271. t.Insert(make_pair(e, e));
  272. }
  273.  
  274. t.Inorder();
  275.  
  276. //cout << t.IsBalance() << endl;
  277. }
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览40346 人正在系统学习中
任何时间，任何地点，
微信名片
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪