fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct node
  5. {
  6. 	struct node *left;
  7. 	char color;
  8. 	struct node *right;
  9. 	struct node *p;
  10. 	int data;
  11. }node;
  12. node *root = NULL;
  13.  
  14. struct node *newNode(int key)
  15. {
  16.     struct node *temp =  (struct node *)malloc(sizeof(struct node));
  17.     temp->data = key;
  18.     temp->left = temp->right = NULL;
  19.     temp->color='R';
  20.     return temp;
  21. }
  22.  
  23.  void left_rotate( node *x ) {
  24.     node *y;
  25.     y = x->right;
  26.     x->right = y->left;
  27.     if ( y->left != NULL )
  28.         y->left->p = x;
  29.     y->p = x->p;
  30.  
  31.     if ( x->p == NULL ) root = y;
  32.     else
  33.         if ( x == (x->p)->left )
  34.              x->p->left = y;
  35.         else
  36.  
  37.             x->p->right = y;
  38.     y->left = x;
  39.     x->p = y;
  40.     return;
  41.     }
  42.  
  43. void right_rotate( node *x ) {
  44.     node *y;
  45.     y = x->left;
  46.     x->left = y->right;
  47.     if ( y->right != NULL )
  48.         y->right->p = x;
  49. 		y->p = x->p;
  50.     if ( x->p == NULL ) root = y;
  51.     else
  52.         if ( x == (x->p)->right )
  53.   			x->p->right = y;
  54.         else
  55.           	  x->p->left = y;
  56.           	 y->right = x;
  57.     		x->p = y;
  58.     		return;
  59.     }
  60.  
  61.  
  62.  
  63. void rbinsert (int val) {
  64. 	node *z=newNode(val);
  65.     node *x = root;
  66.     node *y;
  67.  while (x != NULL)
  68.  	{
  69.  		y = x;
  70.  		if (z->data < x->data)
  71.  			x = x->left;
  72.  		else x = x->right;
  73.  	}
  74.  
  75.  z->p = y;
  76.  if (y == NULL)
  77.  	root = z;
  78.  else if (z->data < y->data)
  79.  	y->left = z;
  80.  else y->right = z;
  81.  z->left = NULL;
  82.  z->right = NULL;
  83.  z->color = 'R';
  84.  rb_fix(z) ;
  85.  return;
  86. }
  87.  
  88.  
  89.  void rb_fix(int val)
  90.  {
  91.  	node *z=newNode(val);
  92.  	node*y;
  93.  	while (z->p->color = 'R')
  94.  	{
  95.       if (z->p == z->p->p->left)
  96.       	{
  97.       		y=z->p->p->right;
  98.       		if(y->color=='R')
  99.       		{
  100.       			z->p->color='B';
  101.       			y->color='B';
  102.       			z->p->p->color='R';
  103.       			z=z->p->p;
  104.       		}
  105.       		else
  106.       		{ 
  107.       			if (z==z->p->right)
  108.       			{
  109.       				z=z->p;
  110.       				left_rotate(z);
  111.       			}
  112.       		z->p->color='B';
  113.       		z->p->p->color='R';
  114.       		right_rotate(z->p->p);
  115.       		}	
  116.       		else
  117.       		{
  118.       				y=z->p->p->left;
  119.       		if(y->color=='R')
  120.       		{
  121.       			z->p->color='B';
  122.       			y->color='B';
  123.       			z->p->p->color='R';
  124.       			z=z->p->p;
  125.       		}
  126.       		else
  127.       		{ 
  128.       			if (z==z->p->left)
  129.       			{
  130.       				z=z->p;
  131.       				right_rotate(z);
  132.       			}
  133.       		z->p->color='B';
  134.       		z->p->p->color='R';
  135.       		left_rotate(z->p->p);
  136.       		}	
  137.       		}
  138.  	}
  139.  	root->color='B';
  140.  }
  141.  
  142. void prefixtour(node *p)
  143. {
  144. 	if (p==NULL)
  145. 		{
  146. 		printf("empty tree");
  147. 		return ;
  148. 	}
  149.  
  150. 	else
  151. 		visit(p);
  152. 	return ;
  153. }
  154.  
  155. void visit( node *x)
  156. {
  157. 	if(x!=NULL)
  158. 	{
  159.  
  160. 		visit(x->left);
  161. 		if(x->p==NULL)
  162. 		printf( "%d %c NIL\n",x->data,x->color);
  163. 		else
  164. 		printf( "%d %c %d\n",x->data,x->color,x->p->data);
  165. 		visit(x->right);
  166. 	}
  167. 	return;
  168. }
  169.  
  170. int main()
  171. {
  172. 	int n;
  173. 	scanf("%d",&n);
  174. 	int i,key;
  175. 	for(i=0;i<n;i++)
  176. 	{
  177.     	scanf("%d",&key);
  178.     	rbinsert(key);
  179. 	}
  180. 	prefixtour(root);
  181. return 0;
  182.  
  183. }
  184.  
  185.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function ‘rbinsert’:
prog.c:84:2: warning: implicit declaration of function ‘rb_fix’ [-Wimplicit-function-declaration]
  rb_fix(z) ;
  ^~~~~~
prog.c: At top level:
prog.c:89:7: warning: conflicting types for ‘rb_fix’
  void rb_fix(int val)
       ^~~~~~
prog.c:84:2: note: previous implicit declaration of ‘rb_fix’ was here
  rb_fix(z) ;
  ^~~~~~
prog.c: In function ‘rb_fix’:
prog.c:93:3: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   while (z->p->color = 'R')
   ^~~~~
prog.c:116:9: error: expected ‘}’ before ‘else’
         else
         ^~~~
prog.c: In function ‘prefixtour’:
prog.c:151:3: warning: implicit declaration of function ‘visit’ [-Wimplicit-function-declaration]
   visit(p);
   ^~~~~
prog.c: At top level:
prog.c:155:6: warning: conflicting types for ‘visit’
 void visit( node *x)
      ^~~~~
prog.c:151:3: note: previous implicit declaration of ‘visit’ was here
   visit(p);
   ^~~~~
stdout
copy 
Standard output is empty
https://ideone.com/fhEqgb
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!