用C++实现红黑树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef struct node
{
    int data;
    int color;
    struct node * parent;
    struct node * left;
    struct node * right;
}node_t, *node_tp;


static node_tp rb_tab_p = NULL;


void free_tab_s(node_tp node)
{
    if(!node)
        return;
    free_tab_s(node->left);
    free_tab_s(node->right);
    printf("\nfree data=%d", node->data);
    free(node);    
}

void free_tab(void)
{
    free_tab_s(rb_tab_p);
}



int node_depth(node_tp node, int * blance)
{
    int l,r;
    if(!node || !node->left || !node->right)
        return 0;
    l = node_depth(node->left, blance);
    r = node_depth(node->right,blance);

    if(l - r > 1 || l - r < -1)
    {
        printf("\n data=%d depth=%d", node->data, r - l);
        if(blance && *blance*(*blance) < (r - l)*(r-l))
            *blance = r - l;
    }
    return (l > r? l: r) + 1;
}

int travesal_mid_s(node_tp node)
{
    int l,r,depth = node_depth(node,NULL);
    if(!node || !node->left || !node->right)
        return 0;
    l = travesal_mid_s(node->left );
    printf(" %d(%d, %d) ", node->data, node->color, depth);
    r = travesal_mid_s(node->right);    
    return l + r + 1;
}

void travesal_mid(void)
{
    int count, depth, blance = 0;
    depth = node_depth(rb_tab_p, &blance);
    printf("\n---------tree is-------------\n");
    count = travesal_mid_s(rb_tab_p);
    printf("\n-----count=%d--depth=%d--blance=%d----------", count, depth, blance);
}

node_tp find_node(node_tp node, int data)
{
    if(!node || !node->left || !node->right)
        return node;
    else if(node->data > data)
        return find_node(node->left, data);
    else if(node->data < data)
        return find_node(node->right, data);
    else
        return node;
}

node_tp max_node(node_tp node)
{
    if(!node || !node->right || !node->right->right)
        return node;
    return max_node(node->right);
}

void init_node(node_tp node, int data, int color)
{
    if(!node)
        return;
    node->data = data;
    node->color = color;
    node->parent = node->left = node->right = NULL;
}

void left_rotate(node_tp node)
{
    node_tp p;
    int itmp;
    if(node && node->right)
    {
        if(node->right->color == -1 )
            node->right->right->color = -1;
        itmp = node->color;
        node->color = node->right->color;
        node->right->color = itmp;

        p = node->right;
        node->right = p->left;
        p->left = node;
    
        p->parent = node->parent;
        if(!p->parent)
            rb_tab_p = p;
        else
        {
            if(p->parent->left == node)
                p->parent->left = p;
            else
                p->parent->right = p;
        }
        node->parent = p;
        if(node->right)
            node->right->parent = node;
    }
}


void right_rotate(node_tp node)
{
    node_tp p;
    int itmp;
    if(node && node->left)
    {
        if(node->left->color == -1)
            node->left->left->color = -1;
                itmp = node->color;
                node->color = node->left->color;
                node->left->color = itmp;

        p = node->left;
        node->left = p->right;
        p->right = node;

        p->parent = node->parent;
        if(!p->parent)
            rb_tab_p = p;
        else
        {
            if(p->parent->left == node)
                p->parent->left = p;
            else
                p->parent->right = p;
        }
        node->parent = p;
        if(node->left)
            node->left->parent = node;
    }

}


void left_right_rotate(node_tp node)
{
    node_tp p;
    int itmp;
    if(node && node->left && node->left->right)
    {
                itmp = node->color;
                node->color = node->left->right->color;
                node->left->right->color = itmp;
        node->color = node->left->color;

        p = node->left->right;
        node->left->right = p->left;
        p->left = node->left;
        
        node->left = p->right;
        p->right = node;    

        p->parent = node->parent;
        if(!p->parent)
            rb_tab_p = p;
        else
        {
            if(p->parent->left == node)
                p->parent->left = p;
            else
                p->parent->right = p;
        }
        p->left->parent = p;
        p->right->parent = p;
        if(p->left->right)
            p->left->right->parent = p->left;
        if(p->right->left)
            p->right->left->parent = p->right;

    }
}

void right_left_rotate(node_tp node)
{
    node_tp p;
    int itmp;
    if(node && node->right && node->right->left)
    {
                itmp = node->color;
                node->color = node->right->left->color;
                node->right->left->color = itmp;
        node->color = node->right->color;

        p = node->right->left;
        node->right->left = p->right;
        p->right = node->right;

        node->right = p->left;
        p->left = node;

        p->parent = node->parent;
        if(!p->parent)
            rb_tab_p = p;
        else
        {
            if(p->parent->left == node)
                p->parent->left = p;
            else
                p->parent->right = p;
        }
        p->left->parent = p;
        p->right->parent = p;
        if(p->left->right)
            p->left->right->parent = p->left;
        if(p->right->left)
            p->right->left->parent = p->right;

    }
}

int insert_rotate_type(node_tp node)
{
    if(node && node->parent->right == node && node->parent->parent->right ==node->parent)
        return -1;
    else if(node && node->parent->left == node && node->parent->parent->left ==node->parent)
        return 1;
    else if(node && node->parent->right == node && node->parent->parent->left ==node->parent)
        return -2;
    else if(node && node->parent->left == node && node->parent->parent->right ==node->parent)
        return 2;
    else
        return 0;

}


void rb_rotate(node_tp node, int type)
{
    switch(type)
    {
        case -1:
            left_rotate(node);
            break;
        case 1:
            right_rotate(node);
            break;
        case -2:
            left_right_rotate(node);
            break;
        case 2:
            right_left_rotate(node);
            break;
        default:
            break;
    }
}

void insert_rb_rotate(node_tp node)
{
    printf("\n11");
    rb_rotate(node->parent->parent, insert_rotate_type(node));
}

void insert_color_adjust(node_tp node)
{
    node_tp p;
    if(!node)
        return;    
    else if(!node->parent)
    {
        node->color = -1;
        return;
    }

    if(node->color == 1 && node->parent->color == 1)
        {
              p = node->parent->parent;
              if(p->left->color == p->right->color)
               {
                       p->left->color = p->right->color = -1;
                       p->color = 1;
                       node = p;
            insert_color_adjust(node);
               }
        else
                 insert_rb_rotate(node);

    }
}


int insert_node_s(node_tp node, int data)
{
    node_tp cur_p, p;
    cur_p = find_node(node, data);
    if(cur_p && cur_p->left && cur_p->right)
        return -1;

    if(!cur_p)
    {
        cur_p = (node_tp)malloc(sizeof(node_t));
        assert(cur_p != NULL);
        init_node(cur_p, data, -1);
        rb_tab_p = cur_p;
    }    

    p = (node_tp)malloc(sizeof(node_t));
    assert(p != NULL);
    init_node(p, 0,-1);
    cur_p->left = p;
    p->parent = cur_p;

    p = (node_tp)malloc(sizeof(node_t));
    assert(p != NULL);
    init_node(p, 0,-1);
    cur_p->right = p;
    p->parent = cur_p;
    
    cur_p->data = data;
    cur_p->color = 1;
        
    insert_color_adjust(cur_p);
    return 0;    
}

int insert_node(int data)
{
    return insert_node_s(rb_tab_p, data);
}


int del_rotate_type(node_tp black_p)
{
    node_tp parent_p, brother_p;
    if(black_p && black_p->parent)
    {
            parent_p = black_p->parent;
                if(parent_p->left == black_p)
                    brother_p = parent_p->right;
            else
                    brother_p = parent_p->left;
    
    if(brother_p->color == 1 && brother_p == parent_p->right)
                   return -1;
        else if(brother_p->color == 1 && brother_p == parent_p->left)
                return 1;
        else if(brother_p->color == -1 && brother_p == parent_p->right &&  brother_p->right->color == 1)
                return -1;
        else if(brother_p->color == -1 && brother_p == parent_p->left &&  brother_p->left->color == 1)
                return 1;
        else if(brother_p->color == -1 && brother_p == parent_p->right && brother_p->left->color == 1 && brother_p->right->color == -1)
                return 2;
        else if(brother_p->color == -1 && brother_p == parent_p->left && brother_p->left->color == -1 && brother_p->right->color == 1)
                return -2;
    }
    return 0;
}

void del_rb_rotate(node_tp node)
{
     rb_rotate(node->parent, del_rotate_type(node));
}


void del_color_adjust(node_tp black_p)
{
    node_tp parent_p, brother_p;
    if(!black_p)
        return;
    else if(black_p == rb_tab_p || black_p->color == 1)
    {
        black_p->color = -1;
        return;
    }
    parent_p = black_p->parent;
    if(parent_p->left == black_p)
        brother_p = parent_p->right;
    else
        brother_p = parent_p->left;

    if(brother_p->color == -1 && brother_p->left->color == -1 && brother_p->right->color == -1)
    {
        brother_p->color = 1;
        black_p = black_p->parent;
    }
    else if(brother_p->color == 1)
    {
        del_rb_rotate(black_p);
    }
    else
    {
        del_rb_rotate(black_p);
        black_p = NULL;
    }
    del_color_adjust(black_p);
            
}

int del_node_s(node_tp node, int data)
{
    node_tp pre_p, cur_p, black_p = NULL;
    cur_p = find_node(node, data);
    if(!cur_p || !cur_p->left || !cur_p->right)
        return -1;
    
    if(!cur_p->left->left)
    {
        if(cur_p->color == -1)
            black_p = cur_p->right;

        if(!cur_p->parent)
        {
            rb_tab_p = cur_p->right;
            rb_tab_p->parent = NULL;
        }
        else
        {
            if(cur_p->parent->left == cur_p)
                cur_p->parent->left = cur_p->right;
            else
                cur_p->parent->right = cur_p->right;
            cur_p->right->parent = cur_p->parent;
        }
        printf("\nfree data=%d", cur_p->data);
        free(cur_p->left);
        free(cur_p);
        if(!rb_tab_p->left || !rb_tab_p->right)
        {
            free(rb_tab_p);
            rb_tab_p = NULL;
            black_p = NULL;
        }
    }
    else
    {
        pre_p = max_node(cur_p->left);
        if(pre_p->color == -1)    
            black_p = pre_p->left;
        cur_p->data = pre_p->data;

        if(pre_p->parent->left == pre_p)
            pre_p->parent->left = pre_p->left;
        else
            pre_p->parent->right = pre_p->left;
        pre_p->left->parent = pre_p->parent;
    
        printf("\nfree data=%d", pre_p->data);
        free(pre_p->right);
        free(pre_p);
    }
    
    del_color_adjust(black_p);
    return 0;

}

int del_node(int data)
{
    return del_node_s(rb_tab_p, data);
}

void input_data(void)
{

    char str[20];
    int data;
    int ret;
    int i;
    for(i = 0; i < 255; i++)
        insert_node(i);
    
    
    while(1)
    {

/*        printf("\n\nenter data=");
        scanf("%s", str);
        if(strncmp(str, "ok", 2) == 0)
            break;
        ret = sscanf(str, "%d", &data);
        if(ret == 1)
        {
            travesal_mid();
            ret = insert_node(data);
            if(ret == 0)
                printf("\ninsert %d successful", data);
            travesal_mid();
        }

*/

                travesal_mid();
                printf("\n\ndel data=");
                scanf("%s", str);
                if(strncmp(str, "ok", 2) == 0)
                        break;
                ret = sscanf(str, "%d", &data);
                if(ret == 1)
                {
                        ret = del_node(data);
                        if(ret == 0)
                                printf("\ndel %d successful", data);
                        travesal_mid();
                }


        
    }
    free_tab();

}

int main(int argc, char **argv)
{

    input_data();


    return 0;
}