Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C++ Programming

Problem with RedBlackTree


I cannot get quite well with the "Insert " method in the RedBlackTree,
could anybody give me a complete implementation of it?

Thanks!

hi dude:

here's list of C red black tree implementation.
skip the comment if you are not Chinese:)

/**//*-----------------------------------------------------------
  RB-Tree            
      :
  1) <<Introduction to algorithm>>
  2) <<STL    >>
  3) sgi-stl stl_tree.h      
  4) http://epaperpress.com/sortsearch/index.html
  5) http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html

        (http://www.cppblog.com/converse/)

          :
  1)              
  2)        
  3)       (           )    
  4)           ,                  
  5)         ,                    

  -------------------------------------------------------------*/

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

typedef int KEY;

enum NODECOLOR
{
    BLACK        = 0,
    RED          = 1

};

typedef struct RBTree
{
    struct                RBTree *parent;
    struct                RBTree *left, *right;
    KEY                        key;
    NODECOLOR   color;

}RBTree, *PRBTree;

PRBTree RB_InsertNode(PRBTree root, KEY key);
PRBTree        RB_InsertNode_Fixup(PRBTree root, PRBTree z);

PRBTree RB_DeleteNode(PRBTree root, KEY key);
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree z);

PRBTree        Find_Node(PRBTree root, KEY key);
void        Left_Rotate(PRBTree A, PRBTree& root);
void        Right_Rotate(PRBTree A, PRBTree& root);
void        Mid_Visit(PRBTree T);
void        Mid_DeleteTree(PRBTree T);
void        Print_Node(PRBTree node);

/**//*-----------------------------------------------------------
  |   A              B
  |  / \    ==>     / \
  | a   B           A  y
  |    / \         / \
  |    b  y        a  b
  -----------------------------------------------------------*/
void Left_Rotate(PRBTree A, PRBTree& root)
{
    PRBTree B;
    B = A->right;

    if (NULL == B)
        return;

    A->right  = B->left;
    if (NULL != B->left)
        B->left->parent = A;
    B->parent = A->parent;
    //              A->parent = NULL  
    if (A == root)
    {
        root = B;
    }
    else if (A == A->parent->left)
    {
        A->parent->left = B;
    }
    else
    {
        A->parent->right = B;
    }
    B->left          = A;
    A->parent = B;

}

/**//*-----------------------------------------------------------
  |    A              B
  |   / \            / \
  |  B   y   ==>    a   A
  | / \                / \
  |a   b              b   y
  -----------------------------------------------------------*/
void Right_Rotate(PRBTree A, PRBTree& root)
{
    PRBTree B;
    B = A->left;

    if (NULL == B)
        return;

    A->left   = B->right;
    if (NULL != B->right)
        B->right->parent = A;
    B->parent = A->parent;
    //              A->parent = NULL  
    if (A == root)
    {
        root = B;
    }
    else if (A == A->parent->left)
    {
        A->parent->left = B;
    }
    else
    {
        A->parent->right = B;
    }
    A->parent = B;
    B->right  = A;

}

/**//*-----------------------------------------------------------
  |            :  key        
  |            :   root,      key
  |            :          ,    NULL
  -------------------------------------------------------------*/
PRBTree Find_Node(PRBTree root, KEY key)
{
    PRBTree x;

    //   key   node
    x = root;
    do
    {
        if (key == x->key)
            break;
        if (key < x->key)
        {
            if (NULL != x->left)
                x = x->left;
            else
                break;
        }
        else
        {
            if (NULL != x->right)
                x = x->right;
            else
                break;
        }
    } while (NULL != x);

    return x;

}

/**//*-----------------------------------------------------------
  |            :     key
  |            :   root,         key
  |            :   root
  -------------------------------------------------------------*/
PRBTree RB_InsertNode(PRBTree root, KEY key)
{
    PRBTree x, y;

    PRBTree z;
    if (NULL == (z = (PRBTree)malloc(sizeof(RBTree))))
    {
        printf("Memory alloc error\n");
        return NULL;
    }
    z->key = key;

    //   z    
    x = root, y = NULL;
    while (NULL != x)
    {
        y = x;
        if (z->key < x->key)
        {
            if (NULL != x->left)
            {
                x = x->left;
            }
            else
            {
                break;
            }
        }
        else
        {
            if (NULL != x->right)
            {
                x = x->right;
            }
            else
            {
                break;
            }
        }
    }

    //  z      
    z->parent = y;
    if (NULL == y)
    {
        root = z;
    }
    else
    {
        if (z->key < y->key)
            y->left = z;
        else
            y->right = z;
    }
    //   z            red             red
    z->left = z->right = NULL;
    z->color = RED;

    //        
    return RB_InsertNode_Fixup(root, z);

}

/**//*-----------------------------------------------------------
  |            :   key        
  |            :   root,     z
  |            :   root
  -------------------------------------------------------------*/
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
{
    PRBTree y;
    while (root != z && RED == z->parent->color)        //  z          
  red
    {
        if (z->parent == z->parent->parent->left)        //            

        {
            y = z->parent->parent->right;                        // y z

            if (NULL != y && RED == y->color)                //        
   red
            {
                z->parent->color = BLACK;                        //   z
       B
                y->color =
BLACK;                                        //   z        B
                z->parent->parent->color = RED;                //   z  
      B
                z = z->parent-

>parent;                                //   z      

            }

else                                                                        //
              b
            {
                if (z == z->parent->right)                        //  

                {
                    z = z->parent;
                    Left_Rotate(z, root);
                }
                z->parent->color = BLACK;                        //    
     B
                z->parent->parent->color = RED;                //      
    R
                Right_Rotate(z->parent->parent, root);
            }
        }

else                                                                                //

        {
            y = z->parent->parent->left;                        // y z

            if (NULL != y && RED == y->color)                //   y    
red
            {
                z->parent->color = BLACK;                        //    
      B
                y->color =
BLACK;                                        //           B
                z->parent->parent->color = RED;                //      
    R
                z = z->parent-

>parent;                                //   z      

            }

else                                                                        //
y        B
            {
                if (z == z->parent->left)                        //    

                {
                    z = z->parent;
                    Right_Rotate(z, root);
                }
                z->parent->color = BLACK;                        //    
      B
                z->parent->parent->color = RED;                //      
     RED
                Left_Rotate(z->parent->parent, root);
            }
        }
    } // while(RED == z->parent->color)

    //           B
    root->color = BLACK;

    return root;

}

/**//*-----------------------------------------------------------
  |            :     key
  |            :   root,         key
  |            :   root
  -------------------------------------------------------------*/
PRBTree RB_DeleteNode(PRBTree root, KEY key)
{
    PRBTree x, y, z, x_parent;

    z = Find_Node(root, key);
    if (NULL == z)
        return root;

    //  z         ,y == z
    //   ,y   z    
    if (NULL == z->left || NULL == z->right)
        y = z;
    else
    {
        y = z->right;
        while (NULL != y->left)
            y = y->left;
    }

    // x y   ,   NULL
    if (NULL != y->left)
        x = y->left;
    else
        x = y->right;

    //   x     y
    if (NULL != x)
        x->parent = y->parent;
    if (NULL == y->parent)
        root = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    //  y key   z ,  y        
    if (y != z)
    {
        z->key = y->key;
    }

    //   y     B,        
    if (BLACK == y->color && NULL != x)
        RB_DeleteNode_Fixup(root, x);

    free(y);

    return root;

}

/**//*-----------------------------------------------------------
  |            :   key        
  |            :   root,         x
  |            :   root
  -------------------------------------------------------------*/
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x)
{
    PRBTree w;

    while (x != root && BLACK == x->color)
    {
        if (x == x->parent-

>left)                                                                //

  x    
        {
            w = x->parent-
>right;                                                                //

w x    

            if (NULL == w)
                continue;

            if (RED == w-

>color)                                                                //

  w      
            {
                w->color = BLACK;
                x->parent->color = RED;
                Left_Rotate(x->parent, root);
                w = x->parent->right;
            }
            if (NULL != w->left         && BLACK == w->left->color &&
                    NULL != w->right && BLACK == w->right->color)
            {
                w->color = RED;
...

read more »

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc