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