Thread: rb tree Sentinel NIL

  1. #1
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40

    rb tree Sentinel NIL

    Hi, I'm trying to write a red black tree implementation that just holds an integer. I'm having trouble conceptualizing how to implement a sentinel NIL that will kind of keep me from trying to access things that aren't in my tree... I originally avoided this route, but have been told by classmates that it is the way to go. The problem I'm having is in setting it up so I don't have to pass it to every function. Here is what I've got right now for the sentinel part... it doesn't work though
    Code:
    main()
    {
      int flag=0, input;
      struct node* root=NULL;
      struct node* NIL;
    
      NIL=malloc(sizeof(struct node));
      NIL->parent=root;
      NIL->left=NIL;
      NIL->right=NIL;
      NIL->data=0;
      NIL->red=0;
    
      printf("\n\n This program stores allows you to store"
             "\n integers in or remove them from a red-black"
             "\n binary search tree. Please use it responsibly.\n\n");
    
      while(flag == 0)
      {
        rbtreemenu();
        getinput(&input);
        switch(input)
        {
          case 1:
            root=addnode(root);
            break;
          case 2:
            root=remnode(root);
            break;
          case -9:
            flag=1;
            break;
          default:
            printf("\n\n Please enter a valid option.\n");
            break;
        }
    
      }
      freenodes(root);
      exit(0);
    }
    
    //-------------------------------------------------------------------------------
    // This function adds a node to a binary search tree
    
    struct node* addnode(struct node* root)
    {
      int input;
      struct node* newnode, uncle;
      struct node* NIL;
    
      printf("\n\n Please enter an integer to add to the red-black tree.\n : ");
      getinput(&input);
    
      newnode=malloc(sizeof(struct node));
      newnode->data=input;
      newnode->red=1;
      newnode->left=NULL;
      newnode->right=NULL;
      newnode->parent=NULL;
    
      if(!root)
      { root=newnode;
        root->red=0;
        root->parent=NIL;
      }
      else
        root=rbinsert(root, newnode);
    
     //print the updated tree
      printf("\n Your red-black tree in order is :");
      printrbtree(root);
      printf("\n The root node is %d,%c", root->data, root->red);
      return root;
    }
    I was thinking I could just declare a new struct node pointer in each function and set it equal to root's parent, but I'm running into problems when root doesn't exist yet. Any ideas? I've had the stomach flu and have been living off of crackers and jello so maybe am not thinking all that clearly. Thanks.

    oops, might help to know what's in my struct huh?
    Code:
    struct node
    {
      int data;
      int red;
      struct node* left;
      struct node* right;
      struct node* parent;
    };
    The idea behind the sentinel NIL as I understand it is to avoid/deal with situations where things in the tree move around and you end up referencing somehting that isn't there, like something above the root. Also, it gives a way to assign the color of the leaves to black.
    Last edited by dinjas; 03-05-2005 at 12:02 AM.
    straight off the heap

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You need to pass a pointer to a pointer if there's a chance you need to change what the root pointer points to. That is to say:
    Code:
    void foo( struct node** n )
    {
        *n = malloc( sizeof( **n ) );
    }
    
    ...
    
    int main( void )
    {
        struct node *root = NULL;
    
        foo( &root );
    }
    Now 'root' will contain an allocated node when the function call ends. If you don't pass a pointer to that pointer, you can't change what it points at inside a function. If you try, the change is lost at the end of the function call:
    Code:
    void bar( struct node *n )
    {
        n = malloc( sizeof( *n ) );
    
        /* memory leak when the function ends */
    }
    
    int main( void )
    {
        struct node *root = NULL;
    
        bar( root );
    
        /* bar is still NULL */
    }
    I'm not sure if that's what you're trying to do here, but if in fact you're trying to change what the pointer points to inside a function, you need to do as I have done in the first example.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    Thanks, that's not really what I was after here, but will definitely save me a lot of trouble. I've been passing the pointer to functions, returning the pointer at the end of the function, and assigning the original pointer to the returned value. That's why some of my function calls look like
    Code:
    pointer=myfunc(pointer);
    I'm thinking of abandoning this sentinel NIL node idea on my red-black tree and just assigning all of the leaf pointers to NULL, and assuming that if something is NULL, then its color is black. Thanks again.

    dinjas
    straight off the heap

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM