fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct node{
  5. 	int Data;
  6. 	int colour; //0 for red and 1 for black
  7. 	struct node* Parent;
  8. 	struct node* rightChild;
  9. 	struct node* leftChild;};
  10.  
  11. struct node* Root;
  12.  
  13. struct node* insert(int value){
  14. 	struct node* p = (struct node*)malloc(sizeof(struct node));
  15.  
  16. 	p->Data = value;
  17. 	p->colour = 0;
  18. 	p->rightChild = NULL;
  19. 	p->leftChild = NULL;
  20. 	p->Parent = NULL;
  21.  
  22. 	struct node* Tracer = (struct node*)malloc(sizeof(struct node));
  23. 	Tracer = Root;
  24. 	struct node* Y = (struct node*)malloc(sizeof(struct node));
  25.  
  26. 	if (Root==NULL){
  27. 		p->Parent = NULL;
  28. 		Root = p;
  29. 	}
  30. 	else{
  31. 		while(Tracer!=NULL){
  32. 		   Y = Tracer;
  33. 	       if (Tracer->Data >= p->Data)
  34. 	           Tracer = Tracer->leftChild;
  35. 	       else
  36. 	           Tracer = Tracer->rightChild;}
  37.  
  38. 	    p->Parent = Y;
  39. 	    if (Y->Data >= p->Data)
  40. 	       Y->leftChild = p;
  41. 	    else
  42. 	       Y->rightChild = p;
  43. 	}
  44. 	return p;
  45.  
  46. 	}
  47.  
  48.  
  49. void leftrotate(struct node*X){
  50. 	struct node* P = X->Parent;
  51. 	struct node* C = X->rightChild;
  52.  
  53. 	C->Parent = P;
  54. 	if (P==NULL)
  55. 		Root=C;
  56. 	else{
  57. 		if( P->leftChild ==X)
  58. 		   P->leftChild = C;
  59. 		else
  60. 		   P->rightChild = C;
  61. 	}
  62.  
  63. 	X->rightChild = C->leftChild;
  64. 	if (C->leftChild!=NULL){
  65. 		C->leftChild->Parent = X;
  66. 	}
  67. 	X->Parent = C;
  68. 	C->leftChild = X;
  69.  
  70. }
  71.  
  72.  
  73. void rightrotate(struct node*X){
  74. 	struct node* P= X->Parent;
  75. 	struct node* C= X->leftChild;
  76.  
  77. 	C->Parent = P;
  78.  
  79. 	if (P==NULL)
  80. 		Root =C;
  81. 	else{
  82. 		if (P->leftChild ==X)
  83. 		    P->leftChild = C;
  84. 		else
  85. 		    P->rightChild = C;}
  86.  
  87.     X->leftChild = C->rightChild;
  88.     if (C->rightChild != NULL){
  89.     	C->rightChild->Parent = X;
  90.     }
  91.     X->Parent = C;
  92.     C->rightChild = X;
  93.  
  94. }
  95.  
  96.  
  97.  
  98.  
  99. void Fixup(struct node*X){
  100.  
  101. 	struct node* P;// = (struct node*)malloc(sizeof(struct node));
  102. 	P = X->Parent;
  103.  
  104. 	while(P!=NULL && P->colour==0 && X->colour==0){
  105. 		if(P->Parent==NULL)
  106. 			break;
  107. 	    else if (P->Parent->leftChild ==P){
  108. 	     		//if(P->Parent->rightChild==NULL)
  109.  
  110. 	     		if(P->Parent->rightChild!=NULL && P->Parent->rightChild->colour ==0){
  111. 	     			P->colour = 1;
  112. 	     			P->Parent->colour = 0;
  113. 	     			P->Parent->rightChild->colour = 1;
  114. 	     			X = P->Parent;
  115. 	     		//P = X->Parent;
  116. 	     	 	}
  117.  
  118. 	     	else{
  119. 			 	if (P->rightChild ==X){
  120. 	     			X = P;
  121. 	     	    	leftrotate(X);
  122. 	     	    	P = X->Parent;
  123. 	     		}
  124.  
  125. 	     	//if( P->leftChild==X){
  126. 	     		P->colour = 1;
  127. 	     		P->Parent->colour = 0;
  128. 	     		rightrotate(P->Parent);
  129. 	     	}
  130. 	     }
  131.  
  132. 	     else{
  133. 	     	if(P->Parent->leftChild!=NULL && P->Parent->leftChild->colour ==0){
  134. 	     		P->colour = 1;
  135. 	     		P->Parent->colour = 0;
  136. 	     		P->Parent->leftChild->colour = 1;
  137. 	     		X = P->Parent;
  138. 	     		P = X->Parent;
  139. 	     	}
  140.  
  141. 	     	else{
  142. 			 	if (P->leftChild ==X){
  143. 	     			X = P;
  144. 	     	    	rightrotate(X);
  145. 	     	    	P = X->Parent;
  146. 	     		}
  147.  
  148. 	     	//if( P->rightChild==X){
  149. 	     		P->colour = 1;
  150. 	     		P->Parent->colour = 0;
  151. 	     		leftrotate(P->Parent);
  152. 	    	}
  153.  
  154. 	    }
  155.  
  156. 	}
  157. 	Root->colour = 1;
  158. 	}
  159.  
  160.  
  161. void Visit(struct node* X){
  162. 	if (X!=NULL){
  163. 		Visit(X->leftChild);
  164. 		if (X->colour ==0){
  165. 			if (X->Parent!= NULL)
  166. 			    printf("%d\t R\t %d \n",X->Data, X->Parent->Data);
  167. 			else
  168. 			    printf("%d\t R\t NIL \n",X->Data);		}
  169. 	    else{
  170. 	    	if (X->Parent!=NULL)
  171. 	    	    printf("%d\t B\t %d \n",X->Data, X->Parent->Data);
  172. 	        else
  173. 	            printf("%d\t B\t NIL \n",X->Data);	    }
  174.  
  175. 		Visit(X->rightChild);
  176. 	}
  177.  
  178. }
  179.  
  180.  
  181. int main(void) {
  182. 	// Building red black tree
  183.  
  184. 	int n;
  185. 	scanf("%d",&n);
  186.  
  187. 	int index;
  188. 	int temp;
  189.  
  190. 	Root = (struct node*)malloc(sizeof(struct node));
  191. 	struct node* X = (struct node*)malloc(sizeof(struct node));
  192. 	Root = NULL;
  193. 	for (index=1;index<=n;index++){
  194. 		scanf("%d",&temp);
  195.  
  196. 		X = insert(temp);
  197. 		Fixup(X);
  198.  
  199. 		}
  200.  
  201. 	if (Root==NULL){
  202. 		printf("empty tree");
  203. 	}	
  204. 	else
  205. 	    Visit(Root);
  206.  
  207.  
  208. 	return 0;
  209. }
  210.  
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/cOeCPK
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!