fork download 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. struct node{
  5.     int key;
  6.     char color;
  7.     struct node *up;
  8.     struct node *left;
  9.     struct node *right;
  10. }*root;
  11.  
  12.  
  13. void in_order_tree_walk(struct node *X){
  14.     if(X!=NULL){
  15.         in_order_tree_walk(X->left);
  16.         printf("%d %c\n", X->key, X->color);
  17.         in_order_tree_walk(X->right);
  18.     }
  19. }
  20.  
  21. struct node* tree_search(struct node *X, int k){
  22.     if(X==NULL || k==X->key)
  23.         return X;
  24.     if(k<X->key)
  25.         return tree_search(X->left, k);
  26.     else
  27.         return tree_search(X->right, k);
  28. }
  29.  
  30. struct node* tmp_node(int k){
  31.     struct node *tmp = (struct node*)malloc(sizeof *root);
  32.     tmp->up = NULL;
  33.     tmp->left = NULL;
  34.     tmp->right = NULL;
  35.     tmp->key = k;
  36.     tmp->color = 'R';
  37.     return tmp;
  38. }
  39.  
  40. void tree_insert(struct node *T, struct node *Z){
  41.     if (T == NULL){
  42.         T = Z;
  43.         return;
  44.     }
  45.     else{
  46.         if (Z->key < T->key){
  47.         tree_insert(T->left, Z);
  48.         T->left->up = T;
  49.     }
  50.     else if (Z->key > T->key){
  51.         tree_insert(T->right,Z);
  52.         T->right->up = T;
  53.     }
  54.   }
  55. }
  56.  
  57. void left_rotate(struct node *X){
  58.     struct node *Y = X->right;
  59.     X->right = Y->left;
  60.     if(Y->left != NULL)
  61.         Y->left->up = X;
  62.     Y->up = X->up;
  63.     if(X->up == NULL)
  64.         root = Y;
  65.     else if( X == X->up->left)
  66.         X->up->left = Y;
  67.         else X->up->right = Y;
  68.     Y->left = X;
  69.     X->up = Y;
  70. }
  71.  
  72. void right_rotate(struct node *X){
  73.     struct node *Y = X->left;
  74.     X->left = Y->right;
  75.     if(Y->right != NULL)
  76.         Y->right->up = X;
  77.     Y->up = X->up;
  78.     if(X->up == NULL)
  79.         root = Y;
  80.     else if( X == X->up->left)
  81.         X->up->left = Y;
  82.     else X->up->right = Y;
  83.     Y->right = X;
  84.     X->up = Y;
  85. }
  86.  
  87. void RB_Insert(struct node *T, int k){
  88.     struct node *X = tmp_node(k);
  89.     tree_insert(T, X);
  90.     X->color = 'R';
  91.     while(X != root && X->up->color == 'R'){
  92.         if(X->up = X->up->up->left){
  93.             struct node *Y = X->up->up->right;
  94.             if(Y->color == 'R'){
  95.                 X->up->color = 'B';
  96.                 Y->color = 'B';
  97.                 X->up->up->color = 'R';
  98.                 X = X->up->up;
  99.             }
  100.             else{
  101.                 if (X == X->up->right){
  102.                 X = X->up;
  103.                 left_rotate(X);
  104.  
  105.                 }
  106.                 X->up->color = 'B';
  107.                 X->up->up->color = 'R';
  108.                 right_rotate(X->up->up);
  109.             }
  110.         }
  111.         else{
  112.             struct node *Y = X->up->up->left;
  113.             if(Y->color == 'R'){
  114.                 X->up->color = 'B';
  115.                 Y->color = 'B';
  116.                 X->up->up->color = 'R';
  117.                 X = X->up->up;
  118.             }
  119.             else{
  120.                 if (X == X->up->left){
  121.                 X = X->up;
  122.                 right_rotate(X);
  123.                 }
  124.                 X->up->color = 'B';
  125.                 X->up->up->color = 'R';
  126.                 left_rotate(X->up->up);
  127.             }
  128.         }
  129.     }
  130.     root->color = 'B';
  131. }
  132.  
  133. int main(){
  134.  
  135.     root = NULL; 
  136.     int T[] = {5,26,17,8,9,30,10,1,23};
  137.     int i;
  138.     for(i=0; i<9; i++){
  139.         printf("%d", T[i]);
  140.         RB_Insert(root, T[i]);
  141.     }
  142.     printf("\n");
  143.     in_order_tree_walk(root);
  144.  
  145.     return 0;
  146. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.c: In function ‘RB_Insert’:
prog.c:92:9: error: suggest parentheses around assignment used as truth value [-Werror=parentheses]
         if(X->up = X->up->up->left){
         ^~
cc1: all warnings being treated as errors
stdout 
Standard output is empty
https://ideone.com/NGGaL4
language:
C99 (gcc 8.3)
created:
8 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!