fork download
copy 
  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. struct node
  4. {
  5.     int data;
  6.     int emptybit;        //empty bit 1 means node is empty
  7.     char colour;
  8.     struct node* parent;
  9.     struct node* left_child;
  10.     struct node* right_child;
  11. };
  12. struct node* root_node;
  13. //visit function
  14. void visit(struct node* x)
  15. {
  16.     if(x!=NULL){
  17.         visit(x->left_child);
  18.         if(x->parent==NULL){
  19.              printf("%d %c NIL\n",x->data,x->colour);
  20.         }
  21.         else{
  22.            printf("%d %c %d\n",x->data,x->colour,x->parent->data);
  23.         }
  24.         visit(x->right_child);
  25.     }
  26.     return;
  27. }
  28. // pre_fix_tour function will do the the tour of tree
  29. void pre_fix_tour(struct node* x)
  30. {
  31.     if(x==NULL)
  32.     printf("empty tree");
  33.     else 
  34.     visit(x);
  35.     return;
  36. }
  37. //uncle function will return the pointer to uncle of the node 
  38. struct node* uncle(struct node* x)
  39. {
  40.     if(x->parent->data<x->parent->parent->data){
  41.         return x->parent->parent->right_child;
  42.     }
  43.     else {
  44.         return x->parent->parent->left_child;
  45.     }
  46. }
  47. //grandparent function will return the pointer to grandparent of node 
  48. struct node* grandparent(struct node *x)
  49. {
  50.     return  x->parent->parent;
  51. }
  52. //leftR will rotate the tree to the left about the given node
  53. void leftR(struct node* x)
  54. {
  55.   struct node* z;
  56.   z=x->parent;
  57.   if(z->parent==NULL){
  58.       z->right_child=x->left_child;
  59.       if(x->left_child!=NULL){
  60.       x->left_child->parent=z;
  61.       }
  62.       x->parent=NULL;
  63.       root_node=x;
  64.        //printf("%d ",root_node->data);
  65.       z->parent=x;
  66.       x->left_child=z;
  67.   }
  68.   else{
  69.       z->right_child=x->left_child;
  70.       if(x->left_child!=NULL){
  71.       x->left_child->parent=z;
  72.       }
  73.       x->parent=z->parent;
  74.       if(z->parent->data>z->data){    //z is a left child
  75.       z->parent->left_child=x;
  76.       }
  77.       else
  78.       z->parent->right_child=x;
  79.       x->left_child=z;
  80.       z->parent=x;
  81.   }
  82.   return;
  83. } 
  84. //rightR will rotate the tree to right
  85. void rightR(struct node* x)
  86. {
  87.   struct node* z;
  88.   z=x->parent;
  89.   if(z->parent==NULL){
  90.       z->left_child=x->right_child;
  91.       if(x->right_child!=NULL){
  92.       x->right_child->parent=z;
  93.       }
  94.       x->parent=NULL;
  95.       root_node=x;
  96.        //printf("%d ",root_node->data);
  97.       z->parent=x;
  98.       x->right_child=z;
  99.   }
  100.   else{
  101.       z->left_child=x->right_child;
  102.       if(x->right_child!=NULL){
  103.       x->right_child->parent=z;
  104.       }
  105.       x->parent=z->parent;
  106.       if(z->parent->data>z->data){    //z is a left child
  107.       z->parent->left_child=x;
  108.       }
  109.       x->right_child=z;
  110.       z->parent=x;
  111.   }
  112.   return;
  113. }
  114. //make_far_child function will make the near child a far child
  115. void make_far_child(struct node*x)
  116. {
  117.     if(x->parent->data<x->parent->parent->data){
  118.         leftR(x);
  119.     }
  120.     else{
  121.         rightR( x);
  122.     }
  123.     return;
  124. }
  125. //near_child function will check if the given node is near
  126. int near_child(struct node* x)
  127. {
  128.    if(x->parent->data<x->parent->parent->data){
  129.        if(x->data>=x->parent->data)
  130.        return 1;
  131.        else
  132.        return 0;
  133.    }
  134.    else{
  135.        if(x->data<x->parent->data)
  136.        return 1;
  137.        else
  138.        return 0;
  139.    }
  140. }
  141. //modify function will re balance the tree
  142. void modify(struct node* x)
  143. {
  144.     if(x->parent==NULL ){
  145.       return;
  146.     }
  147.     else{
  148.         if(grandparent(x)==NULL){
  149.             if(x->parent->colour=='R'){
  150.                x->colour='B';
  151.             }
  152.         }
  153.         else{
  154.             if(x->parent->colour=='B'){
  155.                if(uncle(x)==NULL){
  156.                    if(x->parent->data<grandparent(x)->data){
  157.                    rightR(x->parent);
  158.                    }
  159.                    else
  160.                    leftR(x->parent);
  161.                }
  162.             }
  163.             else if(x->parent->colour=='R'){ 
  164.                 if(uncle(x)==NULL)
  165.                 {
  166.                     if(x->parent->data>=grandparent(x)->data){
  167.                         leftR(x->parent);
  168.                         if(x->parent->colour=='R'){
  169.                             x->parent->colour='B';
  170.                             x->parent->left_child->colour='R';
  171.                         }
  172.                     }
  173.                     else{
  174.                         rightR(x->parent);
  175.                         if(x->parent->colour=='R'){
  176.                             x->parent->colour='B';
  177.                             x->parent->right_child->colour='R';
  178.                         }
  179.                     }
  180.                 }
  181.                 else if(uncle(x)->colour=='R'){   //case 1
  182.                     x->parent->colour='B';
  183.                     uncle(x)->colour='B';
  184.                     grandparent(x)->colour='R';
  185.                     modify(grandparent(x));
  186.                 }
  187.                 else{
  188.                     if(near_child(x)){         //case2
  189.                       make_far_child(x);
  190.                       if(x->data>x->left_child->data){
  191.                          modify(x->left_child);
  192.                       }
  193.                       else 
  194.                         modify(x->right_child);
  195.                     } 
  196.                     else{                    //case 3
  197.                       if(x->parent->data>x->data){
  198.                          x->parent->colour='B';
  199.                          grandparent(x)->colour='R';
  200.                          rightR(x->parent);
  201.                        }
  202.                       else{
  203.                          x->parent->colour='B';
  204.                          grandparent(x)->colour='R';
  205.                          leftR(x->parent);
  206.                       }
  207.                     }
  208.                 }
  209.             }
  210.         }
  211.     }
  212.     return;
  213. }
  214. //inert function takes argument a pointer to node 
  215. void insert(struct node* x,int a)
  216. {
  217.     if(x->emptybit==1){
  218.         x->data=a;
  219.         x->emptybit=0;
  220.         x->colour='R';
  221.         //printf("%d ",x->data);
  222.         modify(x);
  223.     }
  224.     else{
  225.         if((x->data)>a){
  226.             if(x->left_child==NULL){
  227.                 x->left_child=(struct node*)malloc(sizeof(struct node));
  228.                 x->left_child->parent=x;
  229.                 x->left_child->emptybit=1;
  230.                 insert(x->left_child,a);
  231.             } 
  232.             else{
  233.                 insert(x->left_child,a);
  234.             }
  235.         }
  236.         else{
  237.              if(x->right_child==NULL){
  238.                 x->right_child=(struct node*)malloc(sizeof(struct node));
  239.                 x->right_child->parent=x;
  240.                 x->right_child->emptybit=1;
  241.                 insert(x->right_child,a);
  242.             } 
  243.             else{
  244.                 insert(x->right_child,a);
  245.             }
  246.         }
  247.     }
  248.     return;
  249. }
  250. // main function
  251. int main()
  252. {
  253.     int i,n;
  254.     int a[100];
  255.     struct node RBtree;
  256.     scanf("%d",&n);
  257.     for(i=0;i<n;i++){
  258.         scanf("%d",&a[i]);
  259.     }
  260.     // all the elements to be inserted in the tree are stored in array a
  261.     RBtree.data=a[0];
  262.     RBtree.emptybit=0;
  263.     RBtree.colour= 'R';
  264.     RBtree.parent=NULL;
  265.     RBtree.left_child=NULL;
  266.     RBtree.right_child=NULL;
  267.     //declaration of RBtree
  268.     root_node=&RBtree;
  269.     for(i=1;i<n;i++){
  270.        insert(root_node,a[i]);
  271.      }
  272.     root_node->colour='B';
  273.      pre_fix_tour(root_node);
  274.     return 0;
  275. }
Success #stdin #stdout 0s 9432KB
comments (?)
stdin
copy 
5 6 7 8 59 9
stdout
copy 
6 B 7
7 B NIL
8 B 59
9 R 8
59 R 7
https://ideone.com/oeqzCB
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!