• C++实现红黑树

    1.红黑树的基本概念

     2.节点的定义

    1. // 基本定义
    2. enum RBTColor{RED, BLACK};
    3. template<class T>
    4. class RBTNode{
    5. public:
    6. 	RBTColor color; // 颜色
    7. 	T key; // 键值 
    8. 	RBTNode* left; // 左孩子
    9. 	RBTNode* right; // 右孩子
    10. 	RBTNode* parent; // 父节点
    11. 	RBTNode(T value, RBTColor c, RBTNode* p, RBTNode* l, RBTNode* r):
    12. 		key(value),color(c),parent(p),left(l),right(r){
    13. 	} 
    14. };

    3.红黑树类的定义

    1. template<class T>
    2. class RBTree{
    3. private:
    4. 	RBTNode<T>* mRoot;
    5. public:
    6. 	RBTree();
    7. 	~RBTree();
    8. 	// 前序遍历
    9. 	void preOrder();
    10. 	// 中序遍历 
    11. 	void inOrder();
    12. 	// 后序遍历 
    13. 	void postOrder();
    14. 	RBTNode<T>* iterativeSearch(T key);
    15. 	// (递归实现)查找”红黑树“中键值为key的节点
    16. 	RBTNode<T>* search(T key); 
    17. 	// 查找最小节点：返回最小节点的键值
    18. 	T minimum();
    19. 	// 查找最大节点：返回最大节点的键值
    20. 	T maximum(); 
    21. 	// 将节点（key为节点键值）插入到红黑树中
    22. 	void insert(T key);
    23. 	// 删除节点（key为节点键值）
    24. 	void remove(T key);
    25. 	// 销毁红黑树
    26. 	void destroy();
    27. 	// 打印红黑树
    28. 	void print(); 
    29. private:
    30. 	// 前序遍历”红黑树“
    31. 	void preOrder(RBTNode<T>* tree) const;
    32. 	// 中序遍历”红黑树“ 
    33. 	void inOrder(RBTNode<T>* tree) const;
    34. 	// 后续遍历“红黑树” 
    35. 	void postOrder(RBTNode<T>* tree) const;
    36. 	// (递归实现)查找”红黑树“中键值为key的节点
    37. 	RBTNode<T>* search(RBTNode<T>* x ,T key) const;
    38. 	// (非递归实现)查找”红黑树“中键值为key的节点
    39. 	RBTNode<T>* iterativeSearch(RBTNode<T>* x ,T key) const;  
    40. 	// 查找最小节点：返回最小节点的键值
    41. 	RBTNode<T>* minimum(RBTNode<T>* tree);
    42. 	// 查找最大节点：返回最大节点的键值
    43. 	RBTNode<T>* maximum(RBTNode<T>* tree);
    44. 	// 查找节点(X)的后继节点，即查找在红黑树中大于该节点值的最小节点 
    45. 	RBTNode<T>* successor(RBTNode<T>* x); 
    46. 	// 查找节点(X)的前驱节点，即查找在红黑树中小于该节点值的最大节点 
    47. 	RBTNode<T>* predecessor(RBTNode<T>* x);   
    48. 	// 左旋
    49. 	void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);
    50. 	// 右旋
    51. 	void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);
    52. 	// 插入函数
    53. 	void insert(RBTNode<T>*&root, RBTNode<T>* node);
    54. 	// 插入修正函数
    55. //	void insertFixUp(RBTNode<T>*&root, RBTNode<T>* node, RBTNode<T>* parent);
    56. 	void insertFixUp(RBTNode<T>*&root, RBTNode<T>* node);
    57. 	// 删除的修正函数 
    58. 	void removeFixUp(RBTNode<T>*&root, RBTNode<T>* node, RBTNode<T>* parent);
    59. 	// 查找需要替代删除的节点 
    60. 	RBTNode<T>* findReplaceNode(RBTNode<T>* node);
    61. 	// 销毁红黑树
    62. 	void destroy(RBTNode<T>* &tree);
    63. 	// 打印红黑树
    64. 	void print(RBTNode<T>* &tree, T key, int direction); 
    65.  
    66. #define rb_parent(r) ((r)->parent)
    67. #define rb_color(r) ((r)->color)
    68. #define rb_is_red(r) ((r)->color == RED)
    69. #define rb_is_black(r) ((r)->color == BLACK)
    70. #define rb_set_black(r) do{(r)->color = BLACK;}while(0)
    71. #define rb_set_red(r) do{(r)->color = RED;}while(0)
    72. #define rb_set_parent(r, p) do{(r)->parent=(p);}while(0)
    73. #define rb_set_color(r,c) do{(r)->color = (c);}while(0)
    74. };

    4.红黑树中几个主要的算法解析

    4.1前驱算法思路

    查找节点(X)的前驱节点，即查找在红黑树中小于该节点值的最大节点 。

    如上图所示，节点值为10的前驱应该是以其左孩子为根节点的子树中的最大值节点，即节点值为8。查找思路：若查找节点X的前驱，则先移动到X的左孩子(X->left)，再一直查找右孩子直到右孩子为空。

    4.2后继算法思路

    查找节点(X)的后继节点，即查找在红黑树中大于该节点值的最小节点 

    如上图所示，节点值为10的后继节点应该是以其右孩子为根节点的子树中的最小值节点，即节点值为11。查找思路：若查找节点X的后继，则先移动到X的右孩子(X->right)，再一直查找左孩子直到左孩子为空。

    4.3插入算法思路

    （1）插入的节点若是根节点，则直接染黑

     （2）插入的节点X（不管是左孩子还是右孩子）的父节点P为黑色，则不用操作

    （3）L为P的左孩子，若新插入的节点X的父节点L和叔叔节点R都是红色，则将L和R染黑，P染红，再将P作为新插入的节点继续向上判断 

     （4）L为P的左孩子，若插入的节点X的父节点L为红色且X为L的左孩子，叔叔节点R为黑色，则根据P右旋，将L染黑，P染红

    （5）若插入节点X为父节点L的右孩子，且L为红色，叔叔节点R为黑色，则先根据L左转，再根据P右转，将X染黑，P染红

    （6）R为P的右孩子，若插入的节点X的父节点R为红色且X为L的右孩子，叔叔节点L为黑色，则根据P左旋，将R染黑，P染红

    （7）R为P的右节点，若插入节点X为父节点R的左孩子，且R为红色，叔叔节点L为黑色，则先根据R右转，再根据P左转，将X染黑，P染红

    4.4删除算法思路

    删除节点方案：

    1.找到前驱节点，复制前驱节点值覆盖预备删除的节点的值，然后删除前驱节点

    2.找到后继节点，复制后继节点值覆盖预备删除的节点的值，然后删除后继节点

    通过前驱节点与后继节点的替换，可以将删除的节点转移到叶子节点上，方便操作

    蓝色节点表示红或者黑，下面删除的节点都是以删除节点x为例

    （1）删除节点x为红色，不管是父节点的左孩子还是右孩子，则直接删除

    （2）删除的节点x为黑色，且其兄弟节点Y为叶节点且为黑色，则将x删除，p变为黑色，Y变为红色 

     （3）节点X与Y为黑色，且节点X的兄弟节点Y，只包含左孩子L且为红色，则删除节点X后，需要先根据Y右旋，再据P左旋，将L变为P的颜色，再将P染黑

     （4）节点X与Y为黑色，节点X的兄弟节点Y，只包含右孩子R且为红色，则删除节点X后，据P左旋，再将Y变为P的颜色，将P和R染黑。

     （5）节点X和其兄弟节点Y都为黑色，Y的左孩子与右孩子都为红色，将节点X删除，再根据P进行左旋，再将Y变为P的颜色，P和R变黑

    ​​​​

    （6）被删除的节点X为黑色，其兄弟节点Y为红色，则Y的左孩子与右孩子比为黑色。删除节点X，在根据P进行左旋，再将Y染黑，L染红

    4.5红黑树代码

    有点大800行左右

    1. #include<iostream>
    2. #include <iomanip>
    3. using namespace std;
    4. /**
    5. 	1.节点红或者黑
    6. 	2. 根节点为黑色
    7. 	3.空叶节点为黑色
    8. 	4.红色节点的孩子是黑色
    9. 	5.从根节点出发到所以空叶节点的简单路径中黑色节点数量相等
    10. 	
    11. 	初始插入节点是红色 
    12. 	1.插入位置为根，直接染黑
    13. 	2.父亲节点如果是黑色，则不需要染色或者旋转
    14. 	3.父亲节点是红色，叔叔节点也是红色。父亲和叔叔节点染成黑色，爷爷染成红色，
    15. 	  把爷爷看成新插入的节点，循环向上插入
    16. 	4.父亲节点是红色，叔叔节点是黑色。
    17. 		（1）当前节点是其父节点的左节点且父节点是祖父节点的左孩子，
    18. 			 则父节点右旋转，父节点变黑，祖父节点变红，父节点的右子树变为祖父节点的左子树。
    19. 		（2）当前节点是其父节点的右孩子且父节点是祖父节点的右孩子，
    20. 			 则父节点左旋，父节点变黑，祖父节点变红，父节点的左孩子变为祖父节点的右孩子。
    21. 	5. 父亲节点是红色，叔叔节点是黑色
    22. 		（1） 当前节点是其父节点的右节点且父节点是祖父节点的左节点，
    23. 			  则先以父节点进行左旋转，再以祖父节点右旋转【4.1】 
    24. 		（2） 当前节点是父节点的左节点且父节点是祖父节点的右节点，
    25. 			  则先以父节点右旋转，再以祖父节点左旋转【4.2】 
    26. */
    27. // 基本定义
    28. enum RBTColor{RED, BLACK};
    29. template<class T>
    30. class RBTNode{
    31. public:
    32. 	RBTColor color; // 颜色
    33. 	T key; // 键值 
    34. 	RBTNode* left; // 左孩子
    35. 	RBTNode* right; // 右孩子
    36. 	RBTNode* parent; // 父节点
    37. 	RBTNode(T value, RBTColor c, RBTNode* p, RBTNode* l, RBTNode* r):
    38. 		key(value),color(c),parent(p),left(l),right(r){
    39. 	} 
    40. };
    41. template<class T>
    42. class RBTree{
    43. private:
    44. 	RBTNode<T>* mRoot;
    45. public:
    46. 	RBTree();
    47. 	~RBTree();
    48. 	// 前序遍历
    49. 	void preOrder();
    50. 	// 中序遍历 
    51. 	void inOrder();
    52. 	// 后序遍历 
    53. 	void postOrder();
    54. 	RBTNode<T>* iterativeSearch(T key);
    55. 	// (递归实现)查找”红黑树“中键值为key的节点
    56. 	RBTNode<T>* search(T key); 
    57. 	// 查找最小节点：返回最小节点的键值
    58. 	T minimum();
    59. 	// 查找最大节点：返回最大节点的键值
    60. 	T maximum(); 
    61. 	// 将节点（key为节点键值）插入到红黑树中
    62. 	void insert(T key);
    63. 	// 删除节点（key为节点键值）
    64. 	void remove(T key);
    65. 	// 销毁红黑树
    66. 	void destroy();
    67. 	// 打印红黑树
    68. 	void print(); 
    69. private:
    70. 	// 前序遍历”红黑树“
    71. 	void preOrder(RBTNode<T>* tree) const;
    72. 	// 中序遍历”红黑树“ 
    73. 	void inOrder(RBTNode<T>* tree) const;
    74. 	// 后续遍历“红黑树” 
    75. 	void postOrder(RBTNode<T>* tree) const;
    76. 	// (递归实现)查找”红黑树“中键值为key的节点
    77. 	RBTNode<T>* search(RBTNode<T>* x ,T key) const;
    78. 	// (非递归实现)查找”红黑树“中键值为key的节点
    79. 	RBTNode<T>* iterativeSearch(RBTNode<T>* x ,T key) const;  
    80. 	// 查找最小节点：返回最小节点的键值
    81. 	RBTNode<T>* minimum(RBTNode<T>* tree);
    82. 	// 查找最大节点：返回最大节点的键值
    83. 	RBTNode<T>* maximum(RBTNode<T>* tree);
    84. 	// 查找节点(X)的后继节点，即查找在红黑树中大于该节点值的最小节点 
    85. 	RBTNode<T>* successor(RBTNode<T>* x); 
    86. 	// 查找节点(X)的前驱节点，即查找在红黑树中小于该节点值的最大节点 
    87. 	RBTNode<T>* predecessor(RBTNode<T>* x);   
    88. 	// 左旋
    89. 	void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);
    90. 	// 右旋
    91. 	void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);
    92. 	// 插入函数
    93. 	void insert(RBTNode<T>*&root, RBTNode<T>* node);
    94. 	// 插入修正函数
    95. //	void insertFixUp(RBTNode<T>*&root, RBTNode<T>* node, RBTNode<T>* parent);
    96. 	void insertFixUp(RBTNode<T>*&root, RBTNode<T>* node);
    97. 	// 删除的修正函数 
    98. 	void removeFixUp(RBTNode<T>*&root, RBTNode<T>* node, RBTNode<T>* parent);
    99. 	// 查找需要替代删除的节点 
    100. 	RBTNode<T>* findReplaceNode(RBTNode<T>* node);
    101. 	
    102. 	// 销毁红黑树
    103. 	void destroy(RBTNode<T>* &tree);
    104. 	// 打印红黑树
    105. 	void print(RBTNode<T>* &tree, T key, int direction); 
    106.  
    107. #define rb_parent(r) ((r)->parent)
    108. #define rb_color(r) ((r)->color)
    109. #define rb_is_red(r) ((r)->color == RED)
    110. #define rb_is_black(r) ((r)->color == BLACK)
    111. #define rb_set_black(r) do{(r)->color = BLACK;}while(0)
    112. #define rb_set_red(r) do{(r)->color = RED;}while(0)
    113. #define rb_set_parent(r, p) do{(r)->parent=(p);}while(0)
    114. #define rb_set_color(r,c) do{(r)->color = (c);}while(0)	
    115. };
    116. /**
    117. *构造函数 
    118. */
    119. template<class T>
    120. RBTree<T>::RBTree():mRoot(NULL){
    121. 	//mRoot = NULL;
    122. }
    123. /**
    124. * 析构函数 
    125. */
    126. template<class T>
    127. RBTree<T>::~RBTree(){
    128. 	destroy();
    129. }
    130. /**
    131. * 前序遍历”红黑树“ 
    132. */
    133. template<class T>
    134. void RBTree<T>::preOrder(RBTNode<T>* tree) const{
    135. 	if(tree != NULL){
    136. 		cout << tree->key << " ";
    137. 		preOrder(tree->left);
    138. 		preOrder(tree->right);
    139. 	}
    140. }
    141. template<class T>
    142. void RBTree<T>::preOrder(){
    143. 	this->preOrder(mRoot);
    144. }
    145. /**
    146. * 中序遍历”红黑树“ 
    147. */
    148. template<class T>
    149. void RBTree<T>::inOrder(RBTNode<T>* tree) const{
    150. 	if(tree != NULL){
    151. 		inOrder(tree->left);
    152. 		cout << tree->key << " ";
    153. 		inOrder(tree->right);
    154. 	}
    155. }
    156. template<class T>
    157. void RBTree<T>::inOrder(){
    158. 	this->inOrder(mRoot);
    159. }
    160. /**
    161. * 后序遍历”红黑树“ 
    162. */
    163. template<class T>
    164. void RBTree<T>::postOrder(RBTNode<T>* tree) const{
    165. 	if(tree != NULL){
    166. 		postOrder(tree->left);
    167. 		postOrder(tree->right);
    168. 		cout << tree->key << " ";
    169. 	}
    170. }
    171. template<class T>
    172. void RBTree<T>::postOrder(){
    173. 	this->postOrder(mRoot);
    174. }
    175. /**
    176. * (递归实现)查找”红黑树“中键值为key的节点
    177. */ 
    178. template<class T>
    179. RBTNode<T>* RBTree<T>::search(RBTNode<T>* x, T key) const{
    180. 	if(x == NULL || x->key == key){
    181. 		return x;
    182. 	}
    183. 	if(key < x->key){
    184. 		return search(x->left, key);
    185. 	}else{
    186. 		return search(x->right, key);
    187. 	}
    188. } 
    189. template<class T>
    190. RBTNode<T>* RBTree<T>::search(T key){
    191. 	return search(mRoot, key);
    192. }
    193. // (非递归实现)查找”红黑树“中键值为key的节点
    194. template<class T>
    195. RBTNode<T>* RBTree<T>::iterativeSearch(RBTNode<T>* x ,T key) const{
    196. 	while(x != NULL && x->key != key){
    197. 		if(key < x->key){
    198. 			return iterativeSearch(x->left, key);
    199. 		}else{
    200. 			return iterativeSearch(x->right, key);
    201. 		}
    202. 	}
    203. 	return x;
    204. }
    205. template<class T>
    206. RBTNode<T>* RBTree<T>::iterativeSearch(T key){
    207. 	return iterativeSearch(mRoot, key);
    208. }
    209. /**
    210. * 查找最小节点：返回最小节点的键值
    211. */
    212. template<class T>
    213. RBTNode<T>* RBTree<T>::minimum(RBTNode<T>* tree){
    214. 	if(tree == NULL){
    215. 		return NULL;
    216. 	}
    217. 	while(tree->left != NULL){
    218. 		tree = tree->left;
    219. 	}
    220. 	return tree;
    221. }
    222. template<class T>
    223. T RBTree<T>::minimum(){
    224. 	RBTNode<T>* p = minimum(mRoot);
    225. 	if(p != NULL){
    226. 		return p->key;
    227. 	}
    228. 	return 0;
    229. }
    230. /**
    231. * 查找最大节点：返回最大节点的键值
    232. */
    233. template<class T>
    234. RBTNode<T>* RBTree<T>::maximum(RBTNode<T>* tree){
    235. 	if(tree == NULL){
    236. 		return NULL;
    237. 	}
    238. 	while(tree->right != NULL){
    239. 		tree = tree->right;
    240. 	}
    241. 	return tree;
    242. }
    243. template<class T>
    244. T RBTree<T>::maximum(){
    245. 	RBTNode<T>* p = maximum(mRoot);
    246. 	if(p != NULL){
    247. 		return p->key;
    248. 	}
    249. 	return 0;
    250. }
    251. /**
    252. * 查找节点(X)的后继节点，即查找在红黑树中大于该节点值的最小节点 
    253. */ 
    254. template<class T>
    255. RBTNode<T>* RBTree<T>::successor(RBTNode<T>* x){
    256. 	// 如果x存在右孩子，则x的后继节点为其右孩子作为根节点子树的最小节点
    257. 	if(x->right != NULL){
    258. 		return minimum(x->right);
    259. 	} 
    260. 	// 如果x没有右孩子，则x有一下两种可能
    261. 	// 1.x是父节点的左孩子，则x的后继节点为父节点
    262. 	// 2.x是父节点的右孩子，则需要循环查找x的最低父节点，并且该父节点具有左孩子 
    263. 	RBTNode<T>* y = x->parent;
    264. 	while(y != NULL && x != y->left){
    265. 			x = y;
    266. 			y = y->parent;
    267. 	}
    268. 	return y;
    269. }
    270. /**
    271. * 查找节点(X)的前驱节点，即查找在红黑树中小于该节点值的最大节点 
    272. */ 
    273. template<class T>
    274. RBTNode<T>* RBTree<T>::predecessor(RBTNode<T>* x){
    275. 	// 如果x存在左孩子，则x的后继节点为其右孩子作为根节点子树的最大节点
    276. 	if(x->left != NULL){
    277. 		return maximum(x->left);
    278. 	} 
    279. 	// 如果x没有左孩子，则x有一下两种可能
    280. 	// 1.x是父节点的右孩子，则x的后继节点为父节点
    281. 	// 2.x是父节点的左孩子，则需要循环查找x的最低父节点，并且该父节点具有右孩子 
    282. 	RBTNode<T>* y = x->parent;
    283. 	while(y != NULL && x != y->right){
    284. 			x = y;
    285. 			y = y->parent;
    286. 	}
    287. 	return y;
    288. }
    289. /**
    290. 左旋
    291. 		 px											px
    292.    		/	         对x进行左旋转                 /
    293. 	   x             ------------>                y
    294. 	  / \										 / \
    295. 	 lx  y                                      x   ry
    296. 	    / \ 								   / \
    297. 	   ly  ry								  lx  ly 
    298. */
    299.  
    300. template<class T>
    301. void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x){
    302. 	// 设置x的右孩子y
    303. 	RBTNode<T>* y = x->right;
    304. 	// 将y的左孩子设为x的右孩子
    305. 	// 如果y的左孩子非空，将x设为y的左孩子的父亲
    306. 	x->right = y->left; 
    307. 	if(y->left != NULL){
    308. 		y->left->parent = x;
    309. 	}
    310. 	// 将x的父节点设置为y的父节点
    311. 	y->parent = x->parent;
    312. 	if(x->parent == NULL){
    313. 		root = y; // 如果x的父节点为空，则将y设为根节点 
    314. 	} else{
    315. 		if(x->parent->left == x){
    316. 			x->parent->left = y; // 如果x是他父节点的左孩子，则将y设为x的父节点的左孩子 
    317. 		}else{
    318. 			x->parent->right = y;// 如果x是他父节点的右孩子，则将y设为x的父节点的右孩子 
    319. 		}
    320. 	}
    321. 	// 将x设为y的左孩子
    322. 	y->left = x;
    323. 	// 将x的父节点设为y
    324. 	x->parent = y; 
    325. }
    326. /**
    327. 右旋转
    328. 			py 								py
    329. 		   /							   /
    330. 		  y								  x
    331. 		 / \	  对y进行右旋转 		 / \
    332. 		x   ry    ------------>     	lx  y
    333. 	   / \								   / \
    334. 	  lx  rx							  rx  ry
    335. */ 
    336. template<class T>
    337. void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y){
    338. 	// 获取节点x 
    339. 	RBTNode<T>* x = y->left;
    340. 	// 如果x的右孩子非空,则将x的右孩子设置为y的左孩子
    341. 	y->left = x->right;
    342. 	if(x->right != NULL){
    343. 		x->right->parent = y;
    344. 	} 
    345. 	// 将x的父节点指向y的父节点 
    346. 	x->parent = y->parent;
    347. 	if(y->parent == NULL){
    348. 		root = x; // 如果y为根节点，则将x变为新的根节点 
    349. 	}else{
    350. 		if(y->parent->left == y){
    351. 			y->parent->left = x; // 如果y为父节点的左孩子，则将x设置为父节点的左孩子 
    352. 		}else{
    353. 			y->parent->right = x; // 如果y为父节点的右孩子，则将x设置为父节点的右孩子 
    354. 		}
    355. 	}
    356. 	y->parent = x; // 将y的父节点设置为x
    357. 	x->right = y;  // 将x的右孩子设置为y 	
    358. }
    359. /**
    360. 红黑树插入修正函数
    361. 在向红黑树中插入节点之后（失去平衡），再调用该函数 ；
    362. 目的是将它重新塑造成一颗红黑树 
    363. 参数说明：
    364. 	root 红黑树的根
    365. 	node 插入的节点 
    366. */
    367. //#define rb_parent(r) ((r)->parent)
    368. //#define rb_color(r) ((r)->color)
    369. //#define rb_is_red(r) ((r)->color == RED)
    370. //#define rb_is_black(r) ((r)->color == BLACK)
    371. //#define rb_set_black(r) do{(r)->color = BLACK;}while(0)
    372. //#define rb_set_red(r) do{(r)->color = RED;}while(0)
    373. //#define rb_set_parent(r, p) do{(r)->parent=(p);}while(0)
    374. //#define rb_set_color(r,c) do{(r)->color = (c);}while(0)
    375. /**
    376. 	初始插入节点是红色 
    377. 	1.插入位置为根，直接染黑
    378. 	2.父亲节点如果是黑色，则不需要染色或者旋转
    379. 	3.父亲节点是红色，叔叔节点也是红色。父亲和叔叔节点染成黑色，爷爷染成红色，
    380. 	  把爷爷看成新插入的节点，循环向上插入
    381. 	4.父亲节点是红色，叔叔节点是黑色。
    382. 		（1）当前节点是其父节点的左节点且父节点是祖父节点的左孩子，
    383. 			 则父节点右旋转，父节点变黑，祖父节点变红，父节点的右子树变为祖父节点的左子树。
    384. 		（2）当前节点是其父节点的右孩子且父节点是祖父节点的右孩子，
    385. 			 则父节点左旋，父节点变黑，祖父节点变红，父节点的左孩子变为祖父节点的右孩子。
    386. 	5. 父亲节点是红色，叔叔节点是黑色
    387. 		（1） 当前节点是其父节点的右节点且父节点是祖父节点的左节点，
    388. 			  则先以父节点进行左旋转，再以祖父节点右旋转【4.1】 
    389. 		（2） 当前节点是父节点的左节点且父节点是祖父节点的右节点，
    390. 			  则先以父节点右旋转，再以祖父节点左旋转【4.2】 
    391. */ 
    392. template<class T>
    393. void RBTree<T>::insertFixUp(RBTNode<T>*&root, RBTNode<T>* node){
    394. 	// 定义父节点和祖父节点 
    395. 	RBTNode<T>* parent;
    396. 	RBTNode<T>* gparent;
    397. 	RBTNode<T>* uncle;
    398. 	parent = rb_parent(node);
    399. 	// 1.插入位置为根，直接染黑
    400. 	if(parent == NULL){
    401. 		rb_set_black(node);
    402. 		root = node;
    403. 		return;
    404. 	}	
    405. 	// 2.父亲节点如果是黑色，则不需要染色或者旋转
    406. 	if(rb_is_black(parent)){
    407. 		return;
    408. 	} 
    409. 	RBTNode<T>* curNode = node;
    410. 	parent = rb_parent(curNode);
    411. 	while(parent != NULL && rb_is_red(parent)){
    412. 		gparent = rb_parent(parent);
    413. 		// 先讨论父节点是祖父节点左孩子的情况 
    414. 		if(parent == gparent->left){
    415. 			uncle = gparent->right;
    416. 			if(uncle == NULL || rb_is_black(uncle)){
    417. 				if(curNode == parent->right){
    418. 					// 5.若插入节点为父节点的右孩子，且父节点为红色，叔叔节点为黑色，
    419. 					// 则先根据父节点左转，（再根据祖父右转，将当前染黑，祖父染红）跳转到4 	
    420. 					leftRotate(root, parent); 
    421. 					curNode = parent;
    422. 					parent = rb_parent(curNode);	
    423. 				}
    424. 				if(curNode == parent->left){
    425. 					// 4.父节点为祖父节点的左孩子，若插入的节点的父节点为红色且为父节点的左孩子，叔叔节点为黑色，
    426. 					// 则根据祖父节点右旋，将父节点染黑，祖父染红
    427. 					rightRotate(root, gparent); 
    428. 					rb_set_black(parent); // 将父节点染黑 
    429. 					rb_set_red(gparent);  // 将祖父节点染红 
    430. 					break;
    431. 				}
    432. 			}
    433. 		}// 父节点是祖父节点右孩子的情况 
    434. 		else{
    435. 			uncle = gparent->left;
    436. 			if(uncle == NULL || rb_is_black(uncle)){		
    437. 				if(curNode == parent->left){
    438. 					// 7.父节点为祖父节点的右孩子，若插入节点为父节点的左孩子，且父节点为红色，叔叔节点为黑色，
    439. 					// 则先根据父节点右转，（再根据祖父左转，将当前染黑，祖父染红）跳转到6
    440. 					rightRotate(root, parent); 
    441. 					curNode = parent;
    442. 					parent = rb_parent(curNode);	
    443. 				}
    444. 				if(curNode == parent->right){
    445. 					// 6.父节点为祖父节点的右孩子，若父节点为红色且插入节点为父节点的右孩子，叔叔节点为黑色，
    446. 					//则根据祖父左旋，将父节点染黑，祖父染红
    447. 					leftRotate(root, gparent); 
    448. 					rb_set_black(parent); // 将父节点染黑 
    449. 					rb_set_red(gparent);  // 将祖父节点染红 
    450. 					break;	
    451. 				}
    452. 			}
    453. 		}
    454. 		//3.父亲节点是红色，叔叔节点也是红色。父亲和叔叔节点染成黑色，
    455. 		//  爷爷染成红色，把爷爷看成新插入的节点，循环向上插入 
    456. 		if(uncle != NULL && rb_is_red(uncle)){
    457. 			rb_set_black(parent); // 将父节点染黑 
    458. 			rb_set_black(uncle);  // 将叔叔节点染黑 
    459. 			rb_set_red(gparent);  // 将祖父节点染红 
    460. 			curNode = gparent;
    461. 			parent = rb_parent(curNode);
    462. 		}
    463. 	}
    464. 	// 将根节点设为黑色
    465. 	rb_set_black(root); 
    466. }
    467. // 插入函数
    468. /**
    469. * 将节点插入到红黑树中
    470. * root : 红黑树的根节点
    471. * node : 插入的节点 
    472. */
    473. template<class T>
    474. void RBTree<T>::insert(RBTNode<T>*&root, RBTNode<T>* node){
    475. 	RBTNode<T>* y = NULL;
    476. 	RBTNode<T>* x = root;
    477. 	// 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉树中
    478. 	while(x != NULL){
    479. 		y = x;
    480. 		if(node->key < x->key){
    481. 			x = x->left;
    482. 		}else{
    483. 			x = x->right;
    484. 		}
    485. 	} 
    486. 	node->parent = y;
    487. 	if(y != NULL){
    488. 		if(node->key < y->key){
    489. 			y->left = node;
    490. 		}else{
    491. 			y->right = node;
    492. 		}
    493. 	}else{
    494. 		root = node;
    495. 	}
    496. 	// 2.设置节点的颜色为红色
    497. 	node->color = RED;
    498. 	// 3.将它重新修正为一颗红黑树
    499. 	insertFixUp(root, node); 
    500. }
    501. /**
    502. * 将节点（key为节点键值）插入到红黑树中
    503. * 参数说明 
    504. * key ：插入点的键值 
    505. */
    506. template<class T>
    507. void RBTree<T>::insert(T key){
    508. 	RBTNode<T>* z = NULL;
    509. 	// 如果新建节点失败，则返回
    510. 	if((z = new RBTNode<T>(key, RED, NULL, NULL, NULL)) == NULL){
    511. 		return;
    512. 	} 
    513. 	insert(mRoot, z);
    514. }
    515. /**
    516.  红黑树删除修正函数
    517.  在从红黑树中删除插入节点之后（红黑树失去平衡），再调用该函数，目的是将它重新塑造成一颗红黑树
    518.  参数说明：
    519.  root : 红黑树的根
    520.  node : 待修正的节点 
    522. 删除操作：
    523. 主题思想是：若删除的节点不是叶子节点，则可以查找该节点的后继节点的值将其代替，再删除替代它的节点，因为后继节点一般是叶节点，
    524. 			则删除操作可以简化为对叶节点进行操作。
    525. 	1.叶节点是红色，直接删除
    526. 	2.	
    527. */
    528. // 查找需要替代删除的节点 ,叶子节点即可 
    529. template<class T>
    530. RBTNode<T>* RBTree<T>::findReplaceNode(RBTNode<T>* node){
    531. 	// 1.node本身就是叶子节点
    532. 	// 2.node存在左孩子或者右孩子
    533. 	RBTNode<T>* curNode = node;
    534. 	RBTNode<T>* preNode = node;
    535. 	while(curNode->left != NULL || curNode->right != NULL){
    536. 		// 先找后继节点 
    537. 		if(curNode->right != NULL){
    538. 			curNode = this->successor(curNode);
    539. 		}
    540. 		preNode->key = curNode->key;
    541. 		preNode = curNode;
    542. 		// 查找前驱节点 
    543. 		if(curNode->left != NULL){
    544. 			curNode = this->predecessor(curNode);
    545. 		}
    546. 		preNode->key = curNode->key;
    547. 		preNode = curNode;
    548. 	}
    549. 	return curNode; 
    550. }
    551. //#define rb_parent(r) ((r)->parent)
    552. //#define rb_color(r) ((r)->color)
    553. //#define rb_is_red(r) ((r)->color == RED)
    554. //#define rb_is_black(r) ((r)->color == BLACK)
    555. //#define rb_set_black(r) do{(r)->color = BLACK;}while(0)
    556. //#define rb_set_red(r) do{(r)->color = RED;}while(0)
    557. //#define rb_set_parent(r, p) do{(r)->parent=(p);}while(0)
    558. //#define rb_set_color(r,c) do{(r)->color = (c);}while(0)
    559.  
    560. template<class T>
    561. void RBTree<T>::removeFixUp(RBTNode<T>*&root, RBTNode<T>* node, RBTNode<T>* parent){
    562. 	RBTNode<T>* x = this->findReplaceNode(node); // 将删除的节点转移到叶子节点 
    563. 	RBTNode<T>* p = rb_parent(x);
    564. 	RBTNode<T>* y = NULL;
    565. 	RBTNode<T>* l = NULL; 
    566. 	RBTNode<T>* r = NULL;
    567. 	// 先判断删除的叶子节点为父节点的左孩子情况 
    568. 	if(x == p->left){
    569. 		y = p->right; // x的兄弟节点
    570. 		if(y != NULL){
    571. 			l = y->left;
    572. 			r = y->right; 	
    573. 		}
    574. 		// 1. 删除节点为红色，不管是父节点的左孩子还是右孩子，则直接删除
    575. 		if(rb_is_red(x)){
    576. 			p->left = NULL;
    577. 			delete x;
    578. 		}// 2.删除的节点x为黑色，且其兄弟节点Y为叶节点且为黑色，则将x删除，p变为黑色，Y变为红色
    579. 		else if(y == NULL || (rb_is_black(x) && rb_is_black(y) && l == NULL && r == NULL)){
    580. 			p->left = NULL;
    581. 			delete x;
    582. 			rb_set_black(p);
    583. 			if(y != NULL){
    584. 				rb_set_red(y);
    585. 			}
    586. 		}// 3.节点x与Y为黑色，节点X的兄弟节点Y，只包含左孩子L且为红色，则删除节点X后，需要先根据Y右旋，再据P左旋，将L变为P的颜色，
    587. 		 //再将P染黑
    588. 		else if(y != NULL && l != NULL && r == NULL && rb_is_red(l) && rb_is_black(x) && rb_is_black(y)){
    589. 			p->left = NULL;
    590. 			delete x;
    591. 			rightRotate(root, y); // 根据y右旋
    592. 			leftRotate(root, p); // 根据p左旋
    593. 			l->color = p->color;
    594. 			rb_set_black(p);
    595. 		}//  4.节点X与Y为黑色，节点X的兄弟节点Y，只包含右孩子R且为红色，则删除节点X后，据P左旋，再将Y变为P的颜色，
    596. 		// 将P和R染黑。
    597. 		else if(y != NULL && l == NULL && r != NULL && rb_is_red(r) && rb_is_black(x) && rb_is_black(y)){
    598. 			p->left = NULL;
    599. 			delete x;
    600. 			leftRotate(root, p); // 根据p左旋
    601. 			y->color = p->color;
    602. 			rb_set_black(p);
    603. 			rb_set_black(r);
    604. 		}// 5.节点X和其兄弟节点Y都为黑色，Y的左孩子与右孩子都为红色，将节点X删除，再根据P进行左旋，再将Y变为P的颜色，
    605. 		 // P和R变黑
    606. 		else if(y != NULL && l != NULL && r != NULL && rb_is_red(l) && rb_is_red(r) && rb_is_black(x) && rb_is_black(y)){
    607. 			p->left = NULL;
    608. 			delete x;
    609. 			leftRotate(root, p); // 根据p左旋
    610. 			y->color = p->color;
    611. 			rb_set_black(p);
    612. 			rb_set_black(r);
    613. 		}// 6. 被删除的节点X为黑色，其兄弟节点Y为红色，则Y的左孩子与右孩子比黑色。删除节点X，在根据P进行左旋，
    614. 		 // 再将Y染黑，L染红
    615.  		else if(y != NULL && rb_is_red(y) && l != NULL && r != NULL && rb_is_black(l) && rb_is_black(r) && rb_is_black(x)){
    616.  			p->left = NULL;
    617. 			delete x;
    618. 			leftRotate(root, p); // 根据p左旋
    619. 			rb_set_black(y);
    620.  			rb_set_red(l);
    621. 		}	
    622. 	}// 再判断删除的叶子节点为父节点的右孩子情况 
    623. 	else{
    624. 		y = p->left; // x的兄弟节点
    625. 		if(y != NULL){
    626. 			l = y->left;
    627. 			r = y->right; 	
    628. 		}	
    629. 		// 1. 删除节点为红色，不管是父节点的左孩子还是右孩子，则直接删除
    630. 		if(rb_is_red(x)){
    631. 			p->right = NULL;
    632. 			delete x;
    633. 		}// 2.删除的节点x为黑色，且其兄弟节点Y为叶节点且为黑色，则将x删除，p变为黑色，Y变为红色
    634. 		else if(y == NULL || (rb_is_black(x) && rb_is_black(y) && l == NULL && r == NULL)){
    635. 			p->right = NULL;
    636. 			delete x;
    637. 			rb_set_black(p);
    638. 			if(y != NULL){
    639. 				rb_set_red(y);
    640. 			}
    641. 		}// 3.节点X为父节点的右节点，节点X与Y为黑色，且节点X的兄弟节点Y只包含右孩子R且为红色，则删除节点X后，
    642. 		 // 需要先根据Y左旋，再据P右旋，将R变为P的颜色，再将P染黑
    643. 		else if(y != NULL && rb_is_black(x) && rb_is_black(y) && r != NULL && l == NULL && rb_is_red(r)){
    644. 			p->right = NULL;
    645. 			delete x;
    646. 			leftRotate(root, y); // 根据y左旋
    647. 			rightRotate(root, p); // 根据p右旋
    648. 			r->color = p->color; // 将R变为P的颜色
    649. 			rb_set_black(p); // 将P染黑
    650. 		}// 4.节点X为父节点的右节点，节点X与Y为黑色，且节点X的兄弟节点Y，只包含左孩子L且为红色，则删除节点X后，
    651. 		// 根据P右旋，将Y变为P的颜色，再将P和L染黑
    652. 		else if(y != NULL && rb_is_black(x) && rb_is_black(y) && r == NULL && l != NULL && rb_is_red(l)){
    653. 			p->right = NULL;
    654. 			delete x;
    655. 			rightRotate(root, p); // 根据p右旋
    656. 			y->color = p->color;
    657. 			rb_set_black(p); // 将P染黑
    658. 			rb_set_black(l); // 将P染黑 
    659. 		}// 5.节点X为父节点的右节点，节点X和其兄弟节点Y都为黑色，Y的左孩子与右孩子都为红色，将节点X删除，
    660. 		 // 再根据P进行右旋，再将Y变为P的颜色，P和L变黑
    661. 		else if(y != NULL && rb_is_black(x) && rb_is_black(y) && r != NULL && l != NULL && rb_is_red(l) && rb_is_red(r)){
    662. 			p->right = NULL;
    663. 			delete x;
    664. 			rightRotate(root, p); // 根据p右旋
    665. 			y->color = p->color;
    666. 			rb_set_black(p); // 将P染黑
    667. 			rb_set_black(l); // 将P染黑 
    668. 		}// 6.节点X为父节点的右孩子，被删除的节点X为黑色，其兄弟节点Y为红色，则Y的左孩子与右孩子比为黑色。
    669. 		 // 删除节点X，在根据P进行右旋，再将Y染黑，R染红
    670. 		else if(y != NULL && rb_is_black(x) && rb_is_red(y) && r != NULL && l != NULL && rb_is_black(l) && rb_is_black(r)){
    671. 			p->right = NULL;
    672. 			delete x;
    673. 			rightRotate(root, p); // 根据p右旋
    674. 			rb_set_black(y); // 将y染黑
    675. 			rb_set_red(r); // 将r染红 
    676. 		}
    677. 	} 
    678. }
    679. // 删除节点（key为节点键值）
    680. template<class T> 
    681. void RBTree<T>::remove(T key){
    682. 	RBTNode<T>* node;
    683. 	// 查找key对应的节点node，找到的话就删除该节点
    684. 	if((node = search(mRoot, key)) != NULL){
    685. 		removeFixUp(mRoot, node, NULL);
    686. 	} 
    687. }
    688. /**
    689. * 销毁红黑树 
    690. */
    691. template<class T>
    692. void RBTree<T>::destroy(RBTNode<T>* &tree){
    693. 	if(tree == NULL){
    694. 		return;
    695. 	}
    696. 	destroy(tree->left);
    697. 	destroy(tree->right);
    698. 	delete tree;
    699. 	tree = NULL;
    700. }
    701. template<class T>
    702. void RBTree<T>::destroy(){
    703. 	destroy(mRoot);
    704. }
    705. /**
    706. * 打印二叉查找树
    707.  key 节点的键值
    708.  direction    0 表示该节点是根节点
    709.  			  -1 表示该节点是它的父节点的左孩子
    710. 			  1  表示该节点是它父节点的右孩子 
    711. */
    712. template<class T>
    713. void RBTree<T>::print(RBTNode<T>* &tree, T key, int direction){
    714. 	if(tree != NULL){
    715. 		if(direction == 0){ // tree是根节点 
    716. 			cout << setw(2) << tree->key << "(B) is root" << endl;
    717. 		}else{
    718. 			cout << setw(2) << tree->key << (rb_is_red(tree) ? "(R)":"(B)") << " is " << setw(2) << key
    719. 			<< " 's " << setw(12) << (direction == 1 ? "right child":"left child") << endl;
    720. 		}
    721. 		print(tree->left, tree->key, -1);
    722. 		print(tree->right, tree->key, 1);
    723. 	}	
    724. }
    725. template<class T>
    726. void RBTree<T>::print(){
    727. 	if(mRoot != NULL){
    728. 		print(mRoot, mRoot->key, 0);
    729. 	}
    730. }
    731. int main(){
    732. 	cout << "hello1111" << endl; 
    733. 	int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
    734. 	int check_insert = 0; // “插入”动作的检测开关（0，关闭；1，打开）
    735. 	int check_remove = 0; // “删除”动作的检测开关（0，关闭；1，打开）
    736. 	int i;
    737. 	int len = (sizeof(a))/sizeof(a[0]); 
    738. 	RBTree<int>* tree = new RBTree<int>();
    739. 	cout << "====原始数据：";
    740. 	for(i = 0; i < len; i++){
    741. 		cout << a[i] << " ";
    742. 	}
    743. 	cout << endl;
    744. 	for(i = 0; i < len; i++){
    745. 		tree->insert(a[i]);
    746. 		// 设置check_insert=1，测试“添加函数”
    747. 		if(check_insert){
    748. 			cout << "==添加节点：" << a[i] << endl;
    749. 			cout << "==树的详细信息：" << endl;
    750. 			tree->print();
    751. 			cout << endl;
    752. 		} 
    753. 	}
    754. 	cout << "==前序遍历：";
    755. 	tree->preOrder();
    756. 	cout << endl;
    757. 	cout << "==中序遍历：";
    758. 	tree->inOrder();
    759. 	cout << endl;
    760. 	cout << "==后序遍历：";
    761. 	tree->postOrder();
    762. 	cout << endl; 
    763. 	cout << "==最小值：" << tree->minimum() << endl;
    764. 	cout << "==最大值：" << tree->maximum() << endl;
    765. 	cout << "==树的详细信息：" << endl;
    766. 	tree->print();
    767. 	cout << endl;
    768. 	// 设置check_remove = 1，测试“删除函数”
    769. 	check_remove = 1;
    770. 	if(check_remove){
    771. 		for(i = 0; i < len; i++){
    772. 			tree->remove(a[i]);
    773. 			cout << "==删除节点：" << a[i] << endl;
    774. 			cout << "==树的详细信息：" << endl;
    775. 			tree->print();
    776. 			cout << endl;
    777. 		}
    778. 	} 
    779. 	// 销毁红黑树
    780. 	tree->destroy(); 
    781. 	return 0;
    782. }

    在删除操作那儿，后续还要再改动下

  • 相关阅读:
    io_uring 之 liburing 的简单使用
    【PG】PostgreSQL高可用方案repmgr管理之配置文件
    城市-上市公司数字经济数据（2011-2019年）
    amazon账号注册用什么软件？
    Vue中如何进行滚动加载与无限滚动
    深度学习——BRNN和DRNN
    Stream Collectors.groupingBy的四种用法 解决分组统计（计数、求和、平均数等）、范围统计、分组合并、分组结果自定义映射等问题
    HCE OS------操作系统基础操作
    Thymeleaf常见属性
    pip安装Cartopy小白版
  • 原文地址：https://blog.csdn.net/hdsHDS6/article/details/125494544