/* tree_rb.c    red black balanced trees with delete       */
/*              uses special root structure for size, etc. */
/*              specific to key==name, and phone           */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

  struct node;  /* Just introduce type name for a tree node */
  typedef struct node * node_ptr;  /* define a pointer type */
  typedef char name_type[3];       /* just for demo         */
  typedef char phone_type[3];
  
  struct node  /* now, really define the type NODE */
  {
    node_ptr parent;  /* this points to parent      */
    node_ptr left;    /* this points to predecessor */
    node_ptr right;   /* this points to successor   */
    char color;       /* color of node, 'r' or 'b'  */
    name_type name;   /* data, the "sort" key       */
    phone_type phone; /* more tag along data        */
  };
  
  struct root  /* special root node pointed to by user */
  {
    node_ptr first;   /* left most, smallest node     */
    node_ptr last;    /* right most, largest node     */
    node_ptr root;    /* points to real root of tree  */
    node_ptr nil;     /* points to a dummy, nil, node */
    int size;         /* number of items in tree      */
  };
  typedef struct root * root_ptr; /* user root type */

  /* function prototypes for user callable routines */
  void initialize(root_ptr * T);
  void output2(root_ptr T);
  void output(root_ptr T);
  void insert(root_ptr * T, name_type name, phone_type phone);
  void find(root_ptr T, name_type name, phone_type * my_phone);
  node_ptr find_ptr(root_ptr T, name_type name);
  node_ptr successor(root_ptr T, node_ptr x);
  node_ptr predecessor(root_ptr T, node_ptr x);
  void delete_ptr(root_ptr * T, node_ptr * z);
  void delete(root_ptr * T, name_type name);

  void initialize(root_ptr * T)
  {
    (*T) = (root_ptr)malloc(sizeof(struct root));
    (*T)->nil = (node_ptr)malloc(sizeof(struct node));
    (*T)->first = 0;
    (*T)->last = 0;
    (*T)->root = (*T)->nil;
    (*T)->size = 0;
    (*T)->nil->color = 'b';
    (*T)->nil->left = 0;
    (*T)->nil->right = 0;
    (*T)->nil->parent = 0;
    strcpy((*T)->nil->name,"ni");
    strcpy((*T)->nil->phone,"l ");
  }  /* end initialize */
  
  static int depth = -1; /* indentation depth */
 
  static void indent(void) /* called by output for spaces */
  {
    int i;
    for(i=0; i<depth; i++) printf("   ");
  }
 
  static void output1(root_ptr T, node_ptr P)
                             /* a recursive output routine */
  {
    depth++;   /* count depth "down" upon entry */
    if (P != 0 && P != T->nil)
    {
      output1(T, P->left); /* smallest out first */
      indent();
      printf("%s %s %c\n", P->name, P->phone, P->color);
      output1(T, P->right);
    }
    depth--;  /* count depth "up" upon exit */
  } /* end output1 */

  void output2(root_ptr T)
  {
    node_ptr P;
    int i;
	
    if(T->size > 0)
    {
      P = T->first;
      for(i=1; i<=T->size; i++)
      {
        printf("%d.\t %s %s\n", i, P->name, P->phone);
		P = successor(T, P);
      }
    }
  } /* end output2 */
 
  void output(root_ptr T) /* driver of output */
  {
    node_ptr P;
	
    if(T == 0) return; /* tree not even initialized */
    P = T->root;
    if(P == 0 || P == T->nil) return; /* empty tree */
    output1(T, P); /* recursive output */
    /* output2(T);    successor output */
  } /* end output */
  
  static void left_rotate(root_ptr * T, node_ptr * x)
  {
    node_ptr y;  /* temporary */
    node_ptr xx; /* temporary */
	
    xx = (*x);
    y = xx->right;
    xx->right = y->left;
    if(y->left != 0 && y->left != (*T)->nil) (y->left)->parent = xx;
    y->parent = xx->parent;
    if(xx == ((*T)->root))
      (*T)->root = y;
    else if(xx == (xx->parent)->left)
      (xx->parent)->left = y;
    else
      (xx->parent)->right = y;
	  
    y->left = xx;
    xx->parent = y;
  } /* end left_rotate */

  static void right_rotate(root_ptr * T, node_ptr * x)
  {
    node_ptr y;  /* temporary */
    node_ptr xx; /* temporary */

    xx = (*x);
    y = xx->left;
    xx->left = y->right;
    if((y->right) != 0 && (y->right) != ((*T)->nil))
	                              (y->right)->parent = xx;
    y->parent = xx->parent;
    if(xx == ((*T)->root))
      (*T)->root = y;
    else if(xx == (xx->parent)->right)
      (xx->parent)->right = y;
    else
      (xx->parent)->left = y;
	  
    y->right = xx;
    xx->parent = y;
  } /* end right_rotate */

  static int tree_insert(root_ptr * T, node_ptr * z)
  {
    node_ptr y = 0;
    node_ptr x = (*T)->root;
    int never_left = 1;
    int never_right = 1;
    
    while(x != 0 && x != (*T)->nil)
    {
      y = x;
      if(strcmp((*z)->name, x->name) < 0)
      {
        x = x->left;
	never_left = 0;
      }
      else if(strcmp((*z)->name, x->name) > 0)
      {
        x = x->right;
	never_right = 0;
      }
      else /* already entered, just change phone number */
      {
        strcpy(x->phone, (*z)->phone);  
        return 1; /* no fixup required */
      }
    }
    
    (*z)->parent = y;
	
    if(y == 0 || y == (*T)->nil)
    {
      (*T)->root = (*z);
      (*T)->first = (*z);
      (*T)->last = (*z);
    }
    else if(strcmp((*z)->name, y->name) < 0)
    {
      y->left = (*z);
      if(never_right) (*T)->first = (*z);
    }
    else
    {
      y->right = (*z);
      if(never_left) (*T)->last = (*z);
    }
    return 0;
  } /* end tree_insert */
  
  static void rb_insert(root_ptr * T, node_ptr * x)
  {
    node_ptr y;   /* temporary */
    node_ptr P;   /* root node */
	
    if(tree_insert(T, x)) return;
                          /* return if just phone updated */
    (*T)->size = (*T)->size + 1;
    P = (*T)->root;
    (*x)->color = 'r';
    while(((*x) != P) && (((*x)->parent) != P) && 
          (((*x)->parent)->color == 'r'))
    {
      if((*x)->parent == (((*x)->parent)->parent)->left)
      {
        y = (((*x)->parent)->parent)->right;
        if(y != 0 && y != (*T)->nil && y->color == 'r')
        {
          ((*x)->parent)->color = 'b';
          y->color = 'b';
          (((*x)->parent)->parent)->color='r';
          (*x) = ((*x)->parent)->parent;
        }
        else
        {
          if((*x) == ((*x)->parent)->right)
          {
            (*x) = (*x)->parent;
            left_rotate(T, x);
          }
          ((*x)->parent)->color = 'b';
          (((*x)->parent)->parent)->color = 'r';
          right_rotate(T, &(((*x)->parent)->parent));
        }
      }
      else /* same as above with left and right interchanged */
      {
        y = (((*x)->parent)->parent)->left;
        if(y != 0 && y != (*T)->nil && y->color == 'r')
        {
          ((*x)->parent)->color = 'b';
          (((*x)->parent)->parent)->color = 'r';
          y->color = 'b';
          (*x) = ((*x)->parent)->parent;
        }
        else
        {
          if((*x) == ((*x)->parent)->left)
          {
            (*x) = (*x)->parent;
            right_rotate(T, x);
          }
          ((*x)->parent)->color = 'b';
          (((*x)->parent)->parent)->color = 'r';
          left_rotate(T, &(((*x)->parent)->parent));
        }
      }
    }
    ((*T)->root)->color = 'b';
  } /* end rb_insert */

  void insert(root_ptr * T, name_type name, phone_type phone)
  {
    static node_ptr x;
   
    if((*T) == 0) /* need to initialize tree */
    initialize(T);
	  
    x = (node_ptr)malloc(sizeof(struct node));
    x->left = (*T)->nil;  /* special node needed by delete */
    x->right = (*T)->nil;
    x->parent = 0;
    x->color = 'b';
    strcpy(x->name, name);
    strcpy(x->phone, phone);
    rb_insert(T, &x);
  } /* end insert */
 
  void find(root_ptr T, name_type name, phone_type * my_phone)
  {
    phone_type phone;
    node_ptr P = T->root;    /* initial node pointer */
	
    strcpy(phone, "**"); /* "**" default for NO FIND */
    
    while (P != 0 && P != T->nil)  /* this is the search loop */
    {
      if(strcmp(name, P->name) < 0) /* (name < P->name) */
        P = P->left;  /* go looking left */
      else if(strcmp(name, P->name) > 0) /* (name > P->name) */
        P = P->right; /* go looking right */
      else            /* found name */
      {
       strcpy(phone, P->phone); /* phone = P->phone */
       break;   /* exit loop */
      }
    } /* falls through for "no find", "exits" for find */
    
    strcpy(*my_phone, phone);
  } /* end find */
 
 
  node_ptr find_ptr(root_ptr T, name_type name)
  {
    node_ptr P = T->root;    /* initial node pointer */
    
    while (P != 0 && P != T->nil)  /* this is the search loop */
    {
      if(strcmp(name, P->name) < 0) /* (name < P->name) */
        P = P->left;  /* go looking left */
      else if(strcmp(name, P->name) > 0) /* (name > P->name) */
        P = P->right; /* go looking right */
      else            /* found name */
       break;   /* found P, exit loop */

    } /* falls through for "no find", "exits" for find */
    if(P == T->nil) P = 0;
    return P;
  } /* end find_ptr */

  node_ptr successor(root_ptr T, node_ptr x)
  {
    node_ptr y = 0;  /* result, previous place OK */
    node_ptr next;   /* next place to look        */
    node_ptr yy;     /* temporary                 */
	
    if(x == 0 || x == T->nil) return y;
	
    /* #1 right != 0, then follow left != 0    */    
    if(x->right != 0 && x->right != T->nil)
    {
      y = x->right;
      while(y->left != 0 && y->left != T->nil)
      {
	y = y->left;
      }
    }
    /* #2 you are left node of parent          */
    else if(x != T->root && x == x->parent->left)
    {
      y = x->parent;
    }
    /* #3 you are right node of parent follow  */
    /*    till left node of parent             */
    else if(x != T->root && x == x->parent->right)
    {
      yy = x->parent;
      while(yy != T->root && yy != yy->parent->left &&
                             yy == yy->parent->right)
      {
        yy = yy->parent;
      }
      if(yy != T->root && yy == yy->parent->left)
	  y = yy->parent;
    }
	
    return y; /* may be unchanged from 0 */
  } /* end successor */
  
  node_ptr predecessor(root_ptr T, node_ptr x)
  {
    node_ptr y = 0;  /* result, previous place OK */
    node_ptr next;   /* next place to look        */
    node_ptr yy;     /* temporary                 */
	
    if(x == 0 || x == T->nil) return y;
	
    /* #1 left != 0, then follow right != 0    */    
    if(x->left != 0 && x->left != T->nil)
    {
      y = x->left;
      while(y->right != 0 && y->right != T->nil)
      {
        y = y->right;
      }
    }
    /* #2 you are right node of parent          */
    else if(x != T->root && x == x->parent->right)
    {
      y = x->parent;
    }
    /* #3 you are left node of parent follow    */
    /*    till right node of parent             */
    else if(x != T->root && x == x->parent->left)
    {
      yy = x->parent;
      while(yy != T->root && yy != yy->parent->right &&
                             yy == yy->parent->left)
      {
        yy = yy->parent;
      }
      if(yy != T->root && yy == yy->parent->right)
          y = yy->parent;
    }

    return y; /* may be unchanged from 0 */
  } /* end predecessor */

  static void rb_delete_fixup(root_ptr * T, node_ptr * x)
  {
    static node_ptr w;
	
    while(((*x) != (*T)->root) && ((*x)->color == 'b'))
    {
      if((*x) == (*x)->parent->left)
      {
        w = (*x)->parent->right;
    	if(w->color == 'r')
	{
	  w->color = 'b';                  /* case 1 */
	  (*x)->parent->color = 'r';       /* case 1 */
	  left_rotate(T, &((*x)->parent)); /* case 1 */
	  w = (*x)->parent->right;         /* case 1 */
	}
	if(w->left->color == 'b' && w->right->color == 'b')
	{
	  w->color = 'r';                  /* case 2 */
	  (*x) = (*x)->parent;             /* case 2 */
	}
	else if(w->right->color == 'b')
	{
	  w->left->color = 'b';            /* case 3 */
	  w->color = 'r';                  /* case 3 */
          right_rotate(T, &w);             /* case 3 */
	  w = (*x)->parent->right;         /* case 3 */
	}
	w->color = (*x)->parent->color;    /* case 4 */
	(*x)->parent->color = 'b';         /* case 4 */
	w->right->color = 'b';             /* case 4 */
	left_rotate(T, &((*x)->parent));   /* case 4 */
	(*x) = (*T)->root;                 /* case 4 */
      }
      else
      {
        /* same as above with 'right' and 'left' exchanged */
        w = (*x)->parent->left;
	if(w->color == 'r')
	{
	  w->color = 'b';                  /* case 1 */
          (*x)->parent->color = 'r';       /* case 1 */
	  right_rotate(T, &((*x)->parent));/* case 1 */
	  w = (*x)->parent->left;          /* case 1 */
	}
	if(w->right->color == 'b' && w->left->color == 'b')
	{
	  w->color = 'r';                  /* case 2 */
	  (*x) = (*x)->parent;             /* case 2 */
	}
	else if(w->left->color == 'b')
	{
	  w->right->color = 'b';           /* case 3 */
	  w->color = 'r';                  /* case 3 */
	  left_rotate(T, &w);              /* case 3 */
	  w = (*x)->parent->left;          /* case 3 */
	}
	w->color = (*x)->parent->color;    /* case 4 */
	(*x)->parent->color = 'b';         /* case 4 */
	w->left->color = 'b';              /* case 4 */
	right_rotate(T, &((*x)->parent));  /* case 4 */
	(*x) = (*T)->root;		           /* case 4 */
      }
    }
    (*x)->color = 'b';
  } /* end rb_delete_fixup */
  
  void delete_ptr(root_ptr * T, node_ptr * z)
  {
    static node_ptr x;
    static node_ptr y;
	
    if((*z) == (*T)->first) (*T)->first = successor(*T, *z);
    if((*z) == (*T)->last)  (*T)->last  = predecessor(*T, *z);
    (*T)->size = (*T)->size -1;
	
    if((*z)->left == (*T)->nil || (*z)->right == (*T)->nil)
      y = (*z);
    else
      y = successor(*T, *z);

    if(y->left != (*T)->nil)
      x = y->left;
    else
      x = y->right;
  
    x->parent = y->parent;
    if(y->parent == (*T)->nil)
      (*T)->root = x;
    else if(y == y->parent->left)
            y->parent->left = x;
         else
	    y->parent->right = x;
	
    if(y != (*z))
    {
      strcpy((*z)->name, y->name);
      strcpy((*z)->phone, y->phone);
    }
    if(y->color == 'b') rb_delete_fixup(T, &x);
  } /* end delete_ptr */
  
  void delete(root_ptr * T, name_type name)
  {
    static node_ptr z;
	
    z = find_ptr(*T, name);
    if(z == 0) return;
    delete_ptr(T, &z);
  }  /* end delete */
  
int main() /* demonstrate functions insert, output and find */
{
  root_ptr root_p = 0;    /* initially null       */
  name_type my_name;      /* temporary            */
  phone_type my_phone;    /* temporary            */
  node_ptr x;             /* returned by find_ptr */
  node_ptr y;             /* for succ and pred    */
  
  printf("tree_rb.c running \n");
  
  /* build a tree using the  'insert'  function */
  /* print tree using  'output'  function       */
  /* test 'find' and 'find_ptr' and root->      */
  
  insert(&root_p, "D ", "4 "); /* initial node at root */
    /* first tier, built in order to balance tree */
    insert(&root_p, "B ", "2 ");
    insert(&root_p, "F ", "6 ");
 
      /* second tier, more careful ordering */
      insert(&root_p, "A ", "1 ");
      insert(&root_p, "C ", "3 ");
      insert(&root_p, "E ", "5 ");
      insert(&root_p, "G ", "7 ");
 
  output(root_p);    /* look at tree produced. The order of the tree  */
                     /* build was carefully planned to get a balanced */
                     /* binary tree                                   */
  printf("output2 just linear printout\n");
  output2(root_p);
  
  printf("tree size= %d\n", root_p->size);
  if(root_p->first != 0) printf("->first = %s\n", root_p->first->name);
  if(root_p->last  != 0) printf("->last  = %s\n", root_p->last->name);
  
  strcpy(my_name, "E ");
  strcpy(my_phone, "99"); /* just be sure it is set */

  find(root_p, my_name, &my_phone);  /* test 'find' function */
  printf("%s has a phone number %s\n", my_name, my_phone);

  find(root_p, "D ", &my_phone);     /* test FIND function on root */
  printf("D  has a phone number %s\n", my_phone);

  find(root_p, "XX", &my_phone);     /* test FIND function on name */
                                       /* not in directory */
  printf("XX has a phone number %s\n", my_phone);
  
  x = find_ptr(root_p, "G ");
  if(x != 0) printf("find_ptr G has phone %s\n", x->phone);

  x = find_ptr(root_p, "D ");
  if(x != 0) printf("find_ptr D has phone %s\n", x->phone);
  
  x = find_ptr(root_p, "XX");
  if(x == 0) printf("find_ptr correct, no find XX\n");
  if(x != 0) printf("find_ptr bad, found %s%s\n", x->name, x->phone);

  y = successor(root_p, find_ptr(root_p, "A "));
  if(y != 0) printf("successor(A)= %s\n", y->name);
  if(y == 0) printf("successor(A) failed\n");

  y = successor(root_p, find_ptr(root_p, "B "));
  if(y != 0) printf("successor(B)= %s\n", y->name);
  if(y == 0) printf("successor(B) failed\n");

  y = successor(root_p, find_ptr(root_p, "C "));
  if(y != 0) printf("successor(C)= %s\n", y->name);
  if(y == 0) printf("successor(C) failed\n");

  y = successor(root_p, find_ptr(root_p, "D "));
  if(y != 0) printf("successor(D)= %s\n", y->name);
  if(y == 0) printf("successor(D) failed\n");

  y = successor(root_p, find_ptr(root_p, "E "));
  if(y != 0) printf("successor(E)= %s\n", y->name);
  if(y == 0) printf("successor(E) failed\n");

  y = successor(root_p, find_ptr(root_p, "F "));
  if(y != 0) printf("successor(F)= %s\n", y->name);
  if(y == 0) printf("successor(F) failed\n");

  y = successor(root_p, find_ptr(root_p, "G "));
  if(y != 0) printf("successor(G)= %s, failed\n", y->name);
  if(y == 0) printf("successor(G) passed, none\n");
  
  y = predecessor(root_p, find_ptr(root_p, "G "));
  if(y != 0) printf("predecessor(G)= %s\n", y->name);
  if(y == 0) printf("predecessor(G) failed\n");
  
  y = predecessor(root_p, find_ptr(root_p, "F "));
  if(y != 0) printf("predecessor(F)= %s\n", y->name);
  if(y == 0) printf("predecessor(F) failed\n");
  
  y = predecessor(root_p, find_ptr(root_p, "E "));
  if(y != 0) printf("predecessor(E)= %s\n", y->name);
  if(y == 0) printf("predecessor(E) failed\n");
  
  y = predecessor(root_p, find_ptr(root_p, "D "));
  if(y != 0) printf("predecessor(D)= %s\n", y->name);
  if(y == 0) printf("predecessor(D) failed\n");
  
  y = predecessor(root_p, find_ptr(root_p, "C "));
  if(y != 0) printf("predecessor(C)= %s\n", y->name);
  if(y == 0) printf("predecessor(C) failed\n");
  
  y = predecessor(root_p, find_ptr(root_p, "B "));
  if(y != 0) printf("predecessor(B)= %s\n", y->name);
  if(y == 0) printf("predecessor(B) failed\n");
  
  y = predecessor(root_p, find_ptr(root_p, "A "));
  if(y != 0) printf("predecessor(A)= %s, failed\n", y->name);
  if(y == 0) printf("predecessor(A) passed, none\n");
  
  printf("delete leaf node G\n");
  delete(&root_p, "G ");
  output(root_p);
  
  printf("delete intermediate node B\n");
  delete(&root_p, "B ");
  output(root_p);
  
  printf("delete root node D\n");
  delete(&root_p, "D ");
  output(root_p);
  
  printf("tree size= %d\n", root_p->size);
  if(root_p->first != 0) printf("->first = %s\n", root_p->first->name);
  if(root_p->last  != 0) printf("->last  = %s\n", root_p->last->name);
  
  printf("phase one finished\n");
  {
    root_ptr root2 = 0;
    name_type name2 = "  ";
    phone_type phone2 = "  ";
    char ch;

    initialize(&root2);
    for(ch='Z'; ch>='A'; ch--)
    {
      name2[0] = ch;
      phone2[0] = ch;
      insert(&root2, name2, phone2);
    }
    printf("\n inserted Z-A \n");
    output(root2); /* partial result, included later */

    for(ch='a'; ch<='z'; ch++)
    {
      name2[0] = ch;
      phone2[0] = ch;
      insert(&root2, name2, phone2);
    }
    printf("\n and inserted a-z \n");
    output(root2);
    printf("tree size= %d\n", root2->size);
  }
  
  printf("tree_rb finished\n");
  return 0;
} /* end main */

/* output of execution is:
tree_rb.c running 
      A  1  r
   B  2  b
      C  3  r
D  4  b
      E  5  r
   F  6  b
      G  7  r
output2 just linear printout
1.	 A  1 
2.	 B  2 
3.	 C  3 
4.	 D  4 
5.	 E  5 
6.	 F  6 
7.	 G  7 
tree size= 7
->first = A 
->last  = G 
E  has a phone number 5 
D  has a phone number 4 
XX has a phone number **
find_ptr G has phone 7 
find_ptr D has phone 4 
find_ptr correct, no find XX
successor(A)= B 
successor(B)= C 
successor(C)= D 
successor(D)= E 
successor(E)= F 
successor(F)= G 
successor(G) passed, none
predecessor(G)= F 
predecessor(F)= E 
predecessor(E)= D 
predecessor(D)= C 
predecessor(C)= B 
predecessor(B)= A 
predecessor(A) passed, none
delete leaf node G
      A  1  r
   B  2  b
      C  3  r
D  4  b
      E  5  r
   F  6  b
delete intermediate node B
      A  1  r
   C  3  b
D  4  b
      E  5  r
   F  6  b
delete root node D
      A  1  r
   C  3  b
E  5  b
   F  6  b
tree size= 4
->first = A 
->last  = F 
phase one finished

 inserted Z-A 
                  A  A  r
               B  B  b
            C  C  r
               D  D  b
         E  E  b
            F  F  b
      G  G  r
            H  H  b
         I  I  b
            J  J  b
   K  K  b
            L  L  b
         M  M  b
            N  N  b
      O  O  r
            P  P  b
         Q  Q  b
            R  R  b
S  S  b
         T  T  b
      U  U  b
         V  V  b
   W  W  b
         X  X  b
      Y  Y  b
         Z  Z  b

 and inserted a-z 
                     A  A  r
                  B  B  b
               C  C  r
                  D  D  b
            E  E  b
               F  F  b
         G  G  r
               H  H  b
            I  I  b
               J  J  b
      K  K  b
               L  L  b
            M  M  b
               N  N  b
         O  O  r
               P  P  b
            Q  Q  b
               R  R  b
   S  S  r
            T  T  b
         U  U  b
            V  V  b
      W  W  b
            X  X  b
         Y  Y  b
            Z  Z  b
a  a  b
            b  b  b
         c  c  b
            d  d  b
      e  e  b
            f  f  b
         g  g  b
            h  h  b
   i  i  r
            j  j  b
         k  k  b
            l  l  b
      m  m  b
               n  n  b
            o  o  b
               p  p  b
         q  q  r
                  r  r  b
               s  s  r
                  t  t  b
            u  u  b
                  v  v  b
               w  w  r
                     x  x  r
                  y  y  b
                     z  z  r
tree size= 52
tree_rb finished
*/