rbt.c

rbt.c

contents ::

  app.c
  mylib.c
  mylib.h
  rbt.c
  rbt.h

#include <stdio.h>
#include <stdlib.h>
#include "rbt.h"
#include "mylib.h"

#define IS_BLACK(x) ((NULL == x) || (BLACK == x->colour))
#define IS_RED(x)   ((NULL != x) && (RED == x->colour))

typedef enum colour_e { RED, BLACK } colour_t;

struct rbtnode {
  char *key;
  colour_t colour;
  rbt left;
  rbt right;
};

rbt rbt_new(){
  return NULL;
}

char *rbt_search(rbt b, char *key){
  if(b == NULL) return NULL;
  /* strcmp(cs,ct) returns 0  if cs==ct
     strcmp(cs,ct) returns <0 if cs<ct
     strcmp(cs,ct) returns >0 if cs>ct
  */
  if(!strcmp(key, b->key)) return b->key;
  else if(strcmp(key, b->key)<0)
    return rbt_search(b->left, key);
  else
    return rbt_search(b->right, key);
}

rbt rbt_insert(rbt b, char *key){
  if(b == NULL){
    b = emalloc(sizeof *b);
    b->key = emalloc((strlen(key)+1) * sizeof (char));
    strcpy(b->key, key);
    b->colour = RED;
    b->left = NULL;
    b->right = NULL;
  } else if(strcmp(key, b->key)<0)
    b->left = rbt_insert(b->left, key);
  else if(strcmp(key, b->key)>0)
    b->right = rbt_insert(b->right, key);

  return b;
}

/* ADDED FOR LAB 19-20 */
static rbt right_rotate(rbt r){
  if(r != NULL && r->left != NULL){
    rbt temp = r;
    r = r->left;
    temp->left = r->right;
    r->right = temp;
  }
  return r;
}

static rbt left_rotate(rbt r){
  if(r != NULL && r->right != NULL){
    rbt temp = r;
    r = r->right;
    temp->right = r->left;
    r->left = temp;
  }
  return r;
}

static rbt rbt_fix(rbt r){
  if(r == NULL) return NULL;

  if(IS_RED(r->left) && (IS_RED(r->left->left) || IS_RED(r->left->right))){

    if(IS_RED(r->right)){

      r->colour = RED;
      r->left->colour = BLACK;
      r->right->colour = BLACK;

    } else {

      if(IS_RED(r->left->right)) r->left = left_rotate(r->left);

      r = right_rotate(r);
      r->colour = BLACK;
      r->right->colour = RED;

    }

  } else if(IS_RED(r->right)  && (IS_RED(r->right->left) || IS_RED(r->right->right))){

    if(IS_RED(r->left)){

      r->colour = RED;
      r->left->colour = BLACK;
      r->right->colour = BLACK;

    } else {

      if(IS_RED(r->right->left)) r->right = right_rotate(r->right);

      r = left_rotate(r);
      r->colour = BLACK;
      r->left->colour = RED;

    }

  }
  return r;
}

void black_height(rbt t, int bh, int h){
  h++;
  if(IS_BLACK(t))
    bh++;
  if(t == NULL){
    printf("black height :: %d,\t total height is :: %d\n", bh, h);
  } else {
    black_height(t->left, bh, h);
    black_height(t->right, bh, h);
  }
}
/* END OF ADDED CODE FOR LABS 19-20    */
/* HOW COULD THESE LAST TWO LAB TIMES? */
/* I appear to have made a booboo */

void rbt_inorder(rbt b, void f(char *s)){
  if(b == NULL) return;
  rbt_inorder(b->left, f);
  f(b->key);
  rbt_inorder(b->right, f);
}

void rbt_preorder(rbt b, void f(char *s)){
  if(b == NULL) return;
  /* REMOVED FOR LAB 19-20  f(b->key); */
  printf("%c :: %s\n", (IS_BLACK(b))? 'B' : 'R', b->key);
  rbt_preorder(b->left, f);
  rbt_preorder(b->right, f);
}

void rbt_postorder(rbt b, void f(char *s)){
  if(b == NULL) return;
  rbt_postorder(b->left, f);
  rbt_postorder(b->right, f);
  f(b->key);
}

rbt rbt_delete(rbt b, char *key){
  if(b == NULL) return NULL;             /* Key does not exist */
  if(strcmp(key, b->key)<0)
    b->left = rbt_delete(b->left, key);  /* Key may be in the left subtree */
  else if(strcmp(key, b->key)>0)
    b->right = rbt_delete(b->right, key);/* Key may be in the right subtree */
  else { /* We have found it, now erradicate it! */
    rbt temp = NULL;
    if(b->left!=NULL && b->right!=NULL){
      temp = b->right;
      while(temp->left!=NULL)
         temp = temp->left;
      free(b->key);
      b->key = emalloc((strlen(temp->key)+1) * sizeof (char));
      strcpy(b->key, temp->key);
      b->right = rbt_delete(b->right, key);
    } else {
      if(b->left!=NULL)
         temp = b->left;
      else
         temp = b->right;
      free(b->key);
      free(b);
      b = temp;
    }
  }
  return b;
}

James Little