fork(1) 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=x->rightChild;
  35. 	x->rightChild=y->leftChild;
  36. 	if(y->leftChild!=T->nil)
  37. 		y->leftChild->parent=x;
  38. 	else if (x==x->parent->leftChild)
  39. 		x->parent->leftChild=y;
  40. 	else 
  41. 		x->parent->rightChild=y;
  42.  
  43. 	y->leftChild=x;
  44. 	x->parent=y; 
  45. }
  46. void rightrotate(struct tree*T, struct tnode*x)
  47. {
  48. 	struct tnode * y;
  49. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  50. 	y=x->leftChild;
  51. 	x->leftChild=y->rightChild;
  52. 	if(y->rightChild!=T->nil)
  53. 		y->rightChild->parent=x;
  54. 	else if (x==x->parent->rightChild)
  55. 		x->parent->rightChild=y;
  56. 	else 
  57. 		x->parent->leftChild=y;
  58.  
  59. 	y->rightChild=x;
  60. 	x->parent=y; 
  61. }
  62. void rbinsertfixup(struct tree*T, struct tnode*z)
  63. {
  64. 	struct tnode*y;
  65. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  66.  
  67. 	while(z->parent->color=='R')
  68. 	{
  69. 		if(z->parent==z->parent->parent->leftChild)
  70. 		{
  71. 			y=z->parent->parent->rightChild;
  72. 			if(y->color=='R')
  73. 			{
  74. 				z->parent->color='B';
  75. 				y->color='B';
  76. 				z->parent->parent->color='R';
  77. 				z=z->parent->parent;
  78. 			}
  79. 			else if(z==z->parent->rightChild)
  80. 			{
  81. 			  z=z->parent;
  82. 			  leftrotate(T,z);
  83. 			}
  84. 			z->parent->color='B';
  85. 			z->parent->parent->color='R';
  86. 			rightrotate(T,z->parent->parent);
  87. 		}
  88. 		else
  89. 		{
  90. 			y=z->parent->parent->leftChild;
  91. 			if(y->color=='R')
  92. 			{
  93. 				z->parent->color='B';
  94. 				y->color='B';
  95. 				z->parent->parent->color='R';
  96. 				z=z->parent->parent;
  97. 			}
  98. 			else if(z==z->parent->leftChild)
  99. 			{
  100. 			  z=z->parent;
  101. 			  rightrotate(T,z);
  102. 			}
  103. 			z->parent->color='B';
  104. 			z->parent->parent->color='R';
  105. 			leftrotate(T,z->parent->parent);	
  106. 		}
  107. 	}
  108. 	T->root->color='B';
  109. }
  110. void insertion(struct tree *T, struct tnode *z)
  111. {
  112.  
  113. 	struct tnode * y;
  114. 	y=(struct tnode*)malloc(sizeof(struct tnode));
  115. 	struct tnode * x;
  116. 	x=(struct tnode*)malloc(sizeof(struct tnode));
  117. 	y=T->nil; 
  118. 	x=T->root;
  119. 	while(x!=T->nil)
  120. 	{
  121. 		y=x;
  122. 		if(z->data < x->data)
  123. 		x=x->leftChild;
  124. 		else 
  125. 		x=x->rightChild;
  126. 	}
  127. 	z->parent=y;
  128. 	if(y==T->nil)
  129. 	T->root=z;
  130. 	else if (z->data< y->data)
  131. 	y->leftChild=z;
  132. 	else
  133. 	y->rightChild=z;
  134.  
  135. 	z->leftChild=T->nil;
  136. 	z->rightChild=T->nil;
  137. 	z->color='R';
  138. 	rbinsertfixup(T,z);
  139.  
  140. }
  141.  
  142. void visit(struct tnode* x)
  143. {
  144. 	if(x!=NULL)
  145. 	{
  146. 		visit(x->leftChild);
  147. 		if(x->parent!=NULL)
  148. 		printf("%d %c %d \n", x->data, x->color, x->parent->data);
  149. 		else
  150. 		printf("%d %c NIL \n", x->data, x->color);
  151.  
  152.  
  153. 	}
  154. }
  155. void pre_fix_tour (struct tree* T)
  156. {
  157. 	if(T->root==NULL)
  158. 	printf("empty tree");
  159. 	else
  160. 	visit(T->root);
  161.  
  162. }
  163.  
  164.  
  165. int main()
  166. {
  167. 	int a[]={5,4,1,6,10,11};
  168. 	int i;
  169. 	struct tnode* node;
  170. 	struct tree *treen;
  171. 	treen=(struct tree*)malloc(sizeof(struct tree));
  172. 	treen->nil=NULL;
  173. 	treen->root=NULL;
  174. 	for(i=0;i<6;i++)
  175. 	{
  176. 		node=createnode(a[i]);
  177. 		insertion(treen, node);
  178. 	}
  179.  
  180. pre_fix_tour(treen);
  181.  
  182. 	return 0;
  183.  
  184.  
  185.  
  186. }
Runtime error #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vHL8qi
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!