fork download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. #include<stdlib.h>
  4. struct tnode
  5. {
  6. 	int data; char color;
  7. 	struct tnode* parent; 
  8. 	struct tnode* rightChild;
  9. 	struct tnode* leftChild;
  10. };
  11. struct tree
  12. {
  13. 	struct tnode* root;
  14. 	struct tnode* nil;
  15. };
  16.  
  17.  
  18. struct tnode* createnode(int data)
  19. {
  20. 	struct tnode *newnode;
  21. 	newnode=(struct tnode*)malloc(sizeof(struct tnode));
  22. 	newnode->data=data;
  23. 	newnode->color='R';
  24. 	newnode->leftChild=NULL;
  25. //	newnode->parent=NULL;
  26. 	newnode->rightChild=NULL;
  27. 	return newnode;
  28. }
  29.  
  30. void leftrotate(struct tree*T, struct tnode*x)
  31. {
  32. 	struct tnode * y;
  33. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  34. 	y=T->nil; 
  35. 	if(x->rightChild==NULL)
  36. 	return;
  37.  
  38. 	y=x->rightChild;
  39. 	x->rightChild=y->leftChild;
  40. 	if(y->leftChild!=T->nil)
  41. 		y->leftChild->parent=x;
  42. 	y->parent=x->parent;
  43. 	if(x->parent==T->nil)
  44. 		T->root=y;
  45. 	else if (x==x->parent->leftChild)
  46. 		x->parent->leftChild=y;
  47. 	else 
  48. 		x->parent->rightChild=y;
  49.  
  50. 	y->leftChild=x;
  51. 	x->parent=y; 
  52. }
  53. void rightrotate(struct tree*T, struct tnode*x)
  54. {
  55. 	struct tnode * y;
  56. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  57. 	y=x->leftChild;
  58. 	x->leftChild=y->rightChild;
  59.  
  60. 	if(y->rightChild!=T->nil)
  61. 	y->rightChild->parent=x;
  62. 	y->parent = x->parent;
  63. 	if ( x->parent == T->nil)
  64. 	T->root = y;
  65. 	else if (x==x->parent->rightChild)
  66. 		x->parent->rightChild=y;
  67. 	else 
  68. 		x->parent->leftChild=y;
  69.  
  70. 	y->rightChild=x;
  71. 	x->parent=y; 
  72. }
  73. void rbinsertfixup(struct tree*T, struct tnode*z)
  74. {
  75. 	struct tnode*y;
  76. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  77. 	struct tnode*x;
  78. 	x=(struct tnode*)malloc(sizeof(struct tnode));
  79. 	if(T->root==z)
  80. 	{
  81. 		z->color='B';
  82. 		return;
  83. 	}
  84.  
  85. 	while(z->parent!=NULL && z->parent->color=='R')
  86. 	{
  87.  
  88. 		y=z->parent->parent;
  89. 		if(y->leftChild==z->parent)
  90. 		{
  91. 				if(y->rightChild!=NULL)
  92. 				{
  93. 				x=y->rightChild;
  94. 				if(x->color=='R')
  95. 					{
  96. 					z->parent->color='B';
  97. 					x->color='B';
  98. 					y->color='R';
  99. 					z=y;
  100. 					}
  101. 				}
  102. 				else 
  103. 				{
  104. 					if(z->parent->rightChild==z)
  105. 					{
  106. 						z=z->parent;
  107. 						leftrotate(T,z);
  108. 					}
  109. 					z->parent->color='B';
  110. 					y->color='R';
  111. 					rightrotate(T,y);
  112. 				}
  113. 		}
  114. 		else
  115. 		{
  116. 			if(y->leftChild!=NULL)
  117. 				{
  118. 				x=y->leftChild;
  119. 				if(x->color=='R')
  120. 					{
  121. 					z->parent->color='B';
  122. 					x->color='B';
  123. 					y->color='R';
  124. 					z=y;
  125. 					}
  126. 				}
  127. 				else 
  128. 				{
  129. 					if(z->parent->leftChild==z)
  130. 					{
  131. 						z=z->parent;
  132. 						rightrotate(T,z);
  133. 					}
  134. 					z->parent->color='B';
  135. 					y->color='R';
  136. 					leftrotate(T,y);
  137. 				}
  138. 		}
  139. 		T->root->color='B';
  140.   }
  141. }
  142.  
  143. void insertion(struct tree *T, struct tnode *z)
  144. {
  145.  
  146. 	struct tnode * y;
  147. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  148. 	struct tnode * x;
  149. 	x=(struct tnode*)malloc(sizeof(struct tnode));
  150. 	y=T->nil; 
  151. 	x=T->root;
  152. 	if(T->root==NULL)
  153. 	{
  154. 		T->root=z;
  155. 		z->parent=NULL;
  156. 	}
  157. 	else
  158. 	{
  159.  
  160. 	while(x!=T->nil)
  161. 	{
  162. 		y=x;
  163. 		if(z->data < x->data)
  164. 		x=x->leftChild;
  165. 		else 
  166. 		x=x->rightChild;
  167. 	}
  168. 	z->parent=y;
  169. 	if(y==T->nil)
  170. 	T->root=z;
  171. 	else if (z->data< y->data)
  172. 	y->leftChild=z;
  173. 	else
  174. 	y->rightChild=z;
  175.  
  176. //	z->leftChild=T->nil;
  177. ///	z->rightChild=T->nil;
  178. //	z->color='R';
  179. }
  180. 	if(z->parent!=NULL)
  181. 	{
  182. 		if(z->parent->parent==NULL)
  183. 		z->parent->color='B';
  184. 		else 
  185. 		rbinsertfixup(T,z);
  186. 	}
  187. 	T->root->color='B';
  188.  
  189. }
  190.  
  191. void visit(struct tnode* x)
  192. {
  193. 	if(x!=NULL)
  194. 	{
  195. 		visit(x->leftChild);
  196. 		if(x->parent!=NULL)
  197. 		printf("%d %c %d \n", x->data, x->color, x->parent->data);
  198. 		else
  199. 		printf("%d %c NIL \n", x->data, x->color);
  200.  
  201. 		visit(x->rightChild);
  202. 	}
  203. }
  204. void pre_fix_tour (struct tree* T)
  205. {
  206. 	if(T->root==NULL)
  207. 	printf("empty tree");
  208. 	else
  209. 	visit(T->root);
  210.  
  211. }
  212.  
  213.  
  214. int main()
  215. {
  216. 	//int a[]={5,4,1,6,10,11};
  217. 	int i; int n;
  218. 	scanf("%d", &n);
  219. 	int a[n];
  220. 	for(i=0;i<n;i++)
  221. 	scanf("%d ", &a[i]);
  222.  
  223. 	struct tnode* node;
  224. 	struct tree *treen;
  225. 	treen=(struct tree*)malloc(sizeof(struct tree));
  226. 	treen->nil=NULL;
  227. 	treen->root=NULL;
  228. 	for(i=0;i<n;i++)
  229. 	{
  230. 		node=createnode(a[i]);
  231. 		insertion(treen, node);
  232. 	}
  233.  
  234. pre_fix_tour(treen);
  235.  
  236. 	return 0;
  237.  
  238.  
  239.  
  240. }
Success #stdin #stdout 0s 9432KB
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/UEcfhp
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!