Quick Example of Red Black Tree.

In previous articles, FreeBSD AVL tree is ported to Linux and a usage example is presented.
Linux uses red-black tree instead of AVL.  Just searching for rbtree.h in Linux kernel returned so many components such as ext4.  But, rbtree can't be used in user space in kernel source form.  Luckily there is user-space ported rbtree in here.

That code contains a test code.  Here, I post one more example.  My example is the same test written in AVL test code (here).

By the way, using these codes have advantage of efficiency.
Enjoy.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include "rbtree.h"
#include "rbtree_test.h"


void printTree(RBRootType *root)
{
 int count = 0;
 Person *data, *rootdata;
 RBNodeType *cur;

 rootdata = container_of( root->rb_node, Person, node);
 printf("Root node: %s\n", rootdata->name);
 
 cur = rb_first(root);
 while (cur) {
  data = container_of( cur, Person, node);
  printf("%d : %s(%s)\n", count, data->name, data->phone);
  cur = rb_next(cur);
  count++;
 }
 printf("Total nodes in tree: %d\n", count);
 printf("---------------------------------------------------------------------\n");

}

Person* searchPerson(RBRootType *root, char *name)
{
 RBNodeType *curnode = root->rb_node;
 while (curnode) {
  Person *data = container_of(curnode, Person, node);
  int result;

  result = strcmp(name, data->name);

  if (result < 0)
   curnode = curnode->rb_left;
  else if (result > 0)
   curnode = curnode->rb_right;
  else
   return data;
 }
 return NULL;
}

int insertPerson(RBRootType *root, Person *data)
{
 RBNodeType **new = &(root->rb_node), *parent = NULL;
 while (*new) {
  Person *cur = container_of(*new, Person, node);
  int result = strcmp(data->name, cur->name);
  
  parent = *new;
  if (result < 0)
   new = &((*new)->rb_left);
  else if (result > 0)
   new = &((*new)->rb_right);
  else 
   return 0;
 }
 
 // New node
 rb_link_node(&(data->node), parent, new);
 rb_insert_color(&(data->node), root);

 return 1;
}


int main(int argc, char **argv)
{
 RBRootType mytree = RB_ROOT;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 insertPerson(&mytree, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 insertPerson(&mytree, &b);
 
 
 Person *srch = NULL;
 printTree(&mytree);
 
 if ( (srch = searchPerson(&mytree, "Micheal Smith")) != NULL ) 
  printf("Micheal found: %s\n", srch->phone);
 else
  printf("Micheal not found.\n");

 if ( (srch = searchPerson(&mytree, "Jack Stuart")) != NULL ) 
  printf("Jack found: %s\n", srch->phone);
 else
  printf("Jack not found.\n");
 printf("--------------------------------------------------\n");
 
 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 insertPerson(&mytree, &c);

 //traverse!!  root must be Jack.
 printTree(&mytree);

 
 return 0;
}