rbtree.cpp

这是一个用c语言实现了实现区间数相关操作的程序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int KEY;
#define length 5
enum NODECOLOR
{
    BLACK ,
    RED  
};

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

PRBTree RB_InsertNode(PRBTree root, KEY key);
PRBTree        RB_InsertNode_Fixup(PRBTree root, PRBTree z);
void        Left_Rotate(PRBTree A, PRBTree& root);
void        Right_Rotate(PRBTree A, PRBTree& root);
void       Show_rbt(PRBTree T);
void        Show_Node(PRBTree node);
//////////////////////////////////////////////////////////////////////////
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;
    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;
}
///////////////////////////////////////////////////////////////
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;
   
    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;
}
///////////////////////////////////////////////////////////
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;
    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->parent = y;
    if (NULL == y)
    {
        root = z;
    }
    else
    {
        if (z->key < y->key)
            y->left = z;
        else
            y->right = z;
    }
   
    z->left = z->right = NULL;
    z->color = RED;

    return RB_InsertNode_Fixup(root, z);
}

////////////////////////////////////////////////////////////
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
{
    PRBTree y;
    while (root != z && RED == z->parent->color)        
    {
        if (z->parent == z->parent->parent->left)        
        {
            y = z->parent->parent->right;                        
            if (NULL != y && RED == y->color)                
            {
                z->parent->color = BLACK;                        
                y->color = BLACK;                                        
                z->parent->parent->color = RED;                
                z = z->parent->parent;                                
            }
            else                                                                        
            {
                if (z == z->parent->right)                        
                {
                    z = z->parent;
                    Left_Rotate(z, root);
                }
                z->parent->color = BLACK;                       
                z->parent->parent->color = RED;                
                Right_Rotate(z->parent->parent, root);
            }
        }
        else                                                                                
        {
            y = z->parent->parent->left;                        
            if (NULL != y && RED == y->color)                
            {
                z->parent->color = BLACK;                        
                y->color = BLACK;                                        
                z->parent->parent->color = RED;                
                z = z->parent->parent;                                
            }               
            else                                                                        
            {
                if (z == z->parent->left)                       
                {
                    z = z->parent;
                    Right_Rotate(z, root);
                }
                z->parent->color = BLACK;                       
                z->parent->parent->color = RED;                
                Left_Rotate(z->parent->parent, root);
            }
        }
    } 

    root->color = BLACK;
    return root;
}

////////////////////////////////////////////////////////////////////
void Show_Node(PRBTree node)
{
    char* color[] = {"BLACK", "RED"};
    printf("Key = %d, color = %s", node->key, color[node->color]);
    if (NULL != node->parent)
        printf(", parent = %d", node->parent->key);
    if (NULL != node->left)
        printf(", left = %d", node->left->key);
    if (NULL != node->right)
        printf(", right = %d", node->right->key);
    printf("\n");
}
void Show_rbt(PRBTree T)
{
    if (NULL != T)
    {
        if (NULL != T->left)
            Show_rbt(T->left);
        Show_Node(T);
        if (NULL != T->right)
            Show_rbt(T->right);
    }
}
////////////////////////////////////////////////////////
int main(int argc, char *argv[])// 测试主函数 
{
   
    int array[length]={32,21,36,35,32};
    PRBTree root = NULL;
    //srand(time(NULL));
    int i;
   // for (i = 0; i < length; i++)
   // {
   //     array[i] = rand() % 100;
   // }
    for (i = 0; i < 5; i++)
    {
        root = RB_InsertNode(root, array[i]);
    }
    Show_rbt(root);	
    while(1); 
    return 0;
  
}