Re: Problem with RedBlackTree

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-


            }
 
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-


            }
 
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-


  x
        {
            w = x->parent-


w x

            if (NULL == w)
                continue;

            if (RED == w-


  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;
                x = x->parent;
            }
            else
            {
                if (NULL != w->right && BLACK == w->right->color)
                {
                    w->left->color = BLACK;
                    w->color = RED;
                    Right_Rotate(w, root);
                    w = x->parent->right;
                }

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

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                Right_Rotate(x->parent, root);
                x = root;
            }
        }
    }

    x->color = BLACK;

    return root;
}

void Print_Node(PRBTree node)
{
    char* color[] = {"BLACK", "RED"};
    printf("Key = %d,\tcolor = %s", node->key, color[node->color]);
    if (NULL != node->parent)
        printf(",\tparent = %d", node->parent->key);
    if (NULL != node->left)
        printf(",\tleft = %d", node->left->key);
    if (NULL != node->right)
        printf(",\tright = %d", node->right->key);
    printf("\n");
}

//
void Mid_Visit(PRBTree T)
{
    if (NULL != T)
    {
        if (NULL != T->left)
            Mid_Visit(T->left);
        Print_Node(T);
        if (NULL != T->right)
            Mid_Visit(T->right);
    }
}

//
void Mid_DeleteTree(PRBTree T)
{
    if (NULL != T)
    {
        if (NULL != T->left)
            Mid_DeleteTree(T->left);
        PRBTree temp = T->right;
        free(T);
        T = NULL;
        if (NULL != temp)
            Mid_DeleteTree(temp);
    }
}

void Create_New_Array(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        array[i] = rand() % 256;
    }
}

int main(int argc, char *argv[])
{
    //int array[10] = {80, 116, 81, 205, 82, 68, 151, 20, 109, 100};
    int array[10];
    srand(time(NULL));
    Create_New_Array(array, 10);
    PRBTree root = NULL;
    int i;
    for (i = 0; i < 10; i++)
    {
        root = RB_InsertNode(root, array[i]);
    }

    Mid_Visit(root);

    //
    int index = rand() % 10;
    printf("delete node %d\n", array[index]);
    root = RB_DeleteNode(root, array[index]);
    Mid_Visit(root);

    //
    Mid_DeleteTree(root);

    return 0;
}

On Jun 6, 11:34 am, Evil_man <Evilcheng...@gmail.com> wrote: