fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct node
  5. {
  6. 	int data;
  7.     char colour;
  8. 	struct node* parent;
  9. 	struct node* leftChild;
  10. 	struct node* rightChild;
  11.  
  12. };
  13.  
  14.  struct node* root=NULL ;
  15. void leftRotate(struct node* root, struct node* l)  //left rotate
  16. {
  17.      struct node *y;
  18.      y = l->rightChild;  
  19.      l->rightChild = y->leftChild; 
  20.      if( y->leftChild != NULL)
  21.      {
  22.          y->leftChild->parent = l; 
  23.       }
  24.      y->parent = l->parent; 
  25.      if( l->parent == NULL)
  26.      {
  27.          root = y;
  28.      }
  29.      else if( l->data == l->parent->leftChild->data)
  30.      {
  31.          l->parent->leftChild = y; 
  32.      }
  33.      else
  34.          l->parent->rightChild = y;
  35.  
  36.      y->leftChild = l; 
  37.      l->parent = y; 
  38.  
  39.      return;
  40. }
  41.  
  42.  
  43. void rightRotate(struct node* root, struct node* r)  //right rotate
  44. {
  45.     struct node *x;
  46.     x = r->leftChild; 
  47.     r->leftChild = x->rightChild; 
  48.     if ( x->rightChild != NULL)
  49.     {
  50.         x->rightChild->parent = r;
  51.     }
  52.     x->parent = r->parent; 
  53.     if( r->parent == NULL)
  54.     {
  55.         root = x;
  56.     } 
  57.     else if( r->data == r->parent->leftChild->data)
  58.     {
  59.         r->parent->leftChild = x; 
  60.     }
  61.     else 
  62.     	r->parent->rightChild = x;
  63.  
  64.     x->rightChild = r; 
  65.     r->parent = x; 
  66.  
  67.      return;
  68. }
  69.  
  70. struct node* fix(struct node *root,struct node *f) //fixing new node inserted
  71. {
  72. struct node *y;
  73. if ((f->parent)&&(f->parent->colour=='B')) return root;
  74. while (f->parent && (f->parent->colour == 'R'))
  75. {
  76.     if (f->parent->data == f->parent->parent->leftChild->data)
  77.     {
  78.         y = f->parent->parent->rightChild;
  79.         if (y && (y->colour == 'R'))
  80.         {
  81.             f->parent->colour = 'B';
  82.             y->colour = 'B';
  83.             f->parent->parent->colour = 'R';
  84.             f = f->parent->parent;
  85.         }
  86.         else {
  87.         	if (f->data == f->parent->rightChild->data)
  88.         	{
  89.            		f = f->parent;
  90.             	leftRotate(root,f);
  91.             }
  92.             f->parent->colour = 'B';
  93.         	  f->parent->parent->colour = 'R';
  94.         	rightRotate(root,f->parent->parent);
  95.         }
  96.  
  97.     }
  98.     else
  99.      {
  100.         y = f->parent->parent->leftChild;
  101.         if ((y!=NULL) && (y->colour == 'R')){
  102.             f->parent->colour = 'B';
  103.             y->colour = 'B';
  104.             f->parent->parent->colour = 'R';
  105.             f = f->parent->parent;
  106.         }
  107.         else {
  108.  
  109.         	if (f->data == f->parent->leftChild->data){
  110.             	f = f->parent;
  111.             	rightRotate(root,f);
  112.             }
  113.             f->parent->colour = 'B';
  114.         	  f->parent->parent->colour = 'R';
  115.         	  leftRotate(root,f->parent->parent);
  116.         }
  117.  
  118.     }
  119. }
  120. root->colour = 'B';
  121. return root;
  122. }
  123.  
  124. struct node *newnode(struct node *root, int val)   //inserting new node
  125. {
  126.     struct node* p;
  127.     p = (struct node*)calloc(1,sizeof(struct node));
  128.     p->data=val;
  129.     p->colour='R';
  130.  
  131.     if (root==NULL)
  132.     {
  133.     	root=p;
  134.     	root->colour='B';
  135.         return root;
  136.     }
  137.     struct node*x=root;
  138.     struct node*y;
  139.     while (x!=NULL)
  140.     {
  141.     	y=x;
  142.     	if(p->data < x->data)
  143.     	{
  144.     		x=x->leftChild;
  145.     	}
  146.         else
  147.         	x=x->rightChild;
  148.     }
  149.     p->parent=y;
  150.     if(y==NULL)
  151.     {
  152.     	root=p;
  153.     }
  154.     else if(p->data < y->data)
  155.     {
  156.     	y->leftChild=p;
  157.     }
  158.     else
  159.     {
  160.     	y->rightChild=p;
  161.     }
  162.     fix (root,p);
  163.     return root;
  164. }
  165.  
  166. void visit(struct node* x)
  167. {
  168.     if (x != NULL) 
  169.     {
  170.         visit(x->leftChild);
  171.         printf("%d ",x->data);
  172.         printf("%c ",x->colour);
  173.         if(x->parent){
  174.        	    printf("%d\n",x->parent->data);
  175.        	}
  176.        	else printf("NIL\n");
  177.         visit(x->rightChild);
  178.     }
  179. }    
  180. void pre_fix_tour(struct node* root){
  181. 	if (root == NULL)
  182.       printf("empty tree");
  183.     else
  184.       visit(root);
  185. }
  186.  
  187. int main()
  188. {
  189. 	int n;
  190. 	scanf("%d",&n);
  191. 	int a[n],i;
  192.  
  193.  
  194.     for(i=0;i<=n-1;i++){
  195.     	scanf("%d",&a[i]);
  196. 	    root = newnode(root,a[i]);
  197.     }
  198. 	pre_fix_tour(root); 
  199. }
  200.  
  201.  
  202.  
Runtime error #stdin #stdout 0s 10320KB
comments (?)
stdin
copy 
5 4 1 6 10 11
stdout
copy 
Standard output is empty
https://ideone.com/2atrso
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!