fork download
copy 
  1. # include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4.  
  5. struct node {
  6. 	int data;
  7. 	struct node *left, *right, *p;
  8. 	char color;
  9. };
  10.  
  11. typedef struct node *ptr;
  12. struct node rbt;
  13. ptr rbtptr = &rbt;
  14.  
  15. void leftrotate(ptr *root, ptr x) 
  16. {
  17. 	ptr y = x->right;
  18. 	x->right = y->left;
  19. 	if (y->left != rbtptr)
  20. 	{
  21. 		y->left->p = x;
  22. 	}
  23. 	y->p = x->p;
  24. 	if (x->p == rbtptr)
  25. 	{
  26. 		*root = y;
  27. 	}
  28. 	else if (x->p->left == x)
  29. 		x->p->left = y;
  30. 	else
  31. 		x->p->right = y;
  32. 	y->left = x;
  33. 	x->p = y;
  34. }
  35.  
  36. void rightrotate(ptr *root, ptr y) {
  37. 	ptr x = y->left;
  38. 	y->left = x->right;
  39. 	if (x->right != rbtptr)
  40. 	{
  41. 		x->right->p = y;
  42. 	}
  43. 	x->p = y->p;
  44. 	if (y->p == rbtptr)
  45. 	{
  46. 		*root = x;
  47. 	}
  48. 	else {
  49. 		if (y->p->left == y)
  50. 		{
  51. 			y->p->left = x;
  52. 		}
  53. 		else
  54. 		{
  55. 			y->p->right = x;
  56. 		}
  57. 	x->right = y;
  58. 	y->p = x;
  59. }
  60. }
  61. void re_balance(ptr *root, ptr z)
  62. {
  63. 	while (z->p->color == 'R') {
  64. 		if (z->p == z->p->p->left) {
  65. 			ptr y = z->p->p->right;
  66. 			if (y->color == 'R') {
  67. 				z->p->color = 'B';
  68. 				y->color = 'B';
  69. 				z->p->p->color = 'R';
  70. 				z = z->p->p;
  71. 			}
  72. 			else {
  73. 				if (z == z->p->right) {
  74. 					z = z->p;
  75. 					leftrotate(root,z);
  76. 				}
  77. 				z->p->color = 'B';
  78. 				z->p->p->color = 'R';
  79. 				rightrotate(root,z->p->p);
  80. 			}
  81. 		}
  82. 		else {
  83. 			ptr y = z->p->p->left;
  84. 			if (y->color == 'R') {
  85. 				z->p->color = 'B';
  86. 				y->color = 'B';
  87. 				z->p->p->color = 'R';
  88. 				z = z->p->p;
  89. 			}
  90. 			else {
  91. 				if (z == z->p->left) {
  92. 					z = z->p;
  93. 					rightrotate(root,z);
  94. 				}
  95. 				z->p->color = 'B';
  96. 				z->p->p->color = 'R';
  97. 				leftrotate(root,z->p->p);
  98. 			}
  99. 		}
  100. 	}
  101. 	(*root) -> color = 'B';
  102. }	
  103.  
  104. void insert_node(ptr *root, int z) {
  105. 	ptr Z = (ptr) malloc(sizeof(struct node));
  106. 	Z->data = z;
  107. 	ptr y = rbtptr;
  108. 	ptr x = *root;
  109. 	while (x != rbtptr) {
  110. 		y = x;
  111. 		if (Z->data < x->data)
  112. 			x = x->left;
  113. 		else
  114. 			x = x->right;
  115. 	}
  116. 	Z->p = y;
  117. 	if (y == rbtptr)
  118. 		*root = Z;
  119. 	else if (Z->data < y->data)
  120. 		y->left = Z;
  121. 	else
  122. 		y->right = Z;
  123. 	Z->left = rbtptr;
  124. 	Z->right = rbtptr;
  125. 	Z->color = 'R';
  126. 	re_balance(root,Z);
  127. }
  128.  
  129. void visit(ptr root)
  130. {
  131.  
  132.     if( root != rbtptr){
  133.         visit(root->left) ;
  134.         if(root->p == rbtptr){
  135.         	printf("%d %c NIL\n", (root)->data , (root)->color);
  136.         }
  137.         else{
  138.         	printf("%d %c %d\n", (root)->data , (root)->color , (root)->p->data);
  139.         }        
  140.         visit((root)->right) ;
  141.     }
  142.     return ;
  143. }
  144.  
  145. void pre_fix_tour(ptr root)
  146. {
  147.     if (root == rbtptr)
  148.     {
  149.     	printf("empty tree");
  150.         return ;
  151.     }
  152.     else visit(root) ;
  153.     return ;
  154. }
  155.  
  156.  
  157. int main()
  158. {
  159.  
  160. 	int n,i,val;
  161. 	scanf("%d",&n);
  162.  
  163. 	rbt.left = rbt.right = rbt.p = rbtptr;
  164. 	rbtptr->color = 'B';
  165. 	ptr rbtree = rbtptr;
  166.  
  167. 	for (i=0; i<n; ++i)
  168. 	{
  169. 			scanf("%d", &val);
  170. 			insert_node(&rbtree, val);
  171. 	}
  172.  	pre_fix_tour(rbtree);
  173.  
  174. 	return 0;
  175. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
5 4 1 6 10 11
stdout
copy 
1 B 4
4 B NIL
6 R 10
10 B 4
11 R 10
https://ideone.com/tVVubp
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!