Red Black Tree

本文参考算法导论书籍以及一些博客，实现了红黑树的插入删除算法。

简介

红黑树这个算法，以后可能会再次遇到，我就在此记录一下。这个算法使用的C语言实现的。

红黑树的原理讲解

我是通过参考枫叶博主关于对红黑树讲解，以及算法导论这本书大致了解了红黑树的实现细节。具体参见红黑树删除操作。

红黑树的C实现

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

typedef enum Color
{
        RED = 0,
        BLACK = 1
}Color;

typedef struct Node
{
        int value;
        Color color;
        struct Node * parent;
        struct Node * left;
        struct Node * right;
}Node, *Tree;

Node * nil = NULL;        // is a leaf node
char color[2][6] = { {"RED"}, {"BLACK"} } ;

void left_rotate( Tree * T, Node * x )  // x's right subtree will be x's new parent
{
        if( x->right != nil )
        {
                Node * y = x->right;

                x->right = y->left;

                if( y->left != nil )      // is not a leaf
                {
                        y->left->parent = x;
                }

                y->parent = x->parent;

                if( x->parent == nil )   // x is root
                {
                        *T = y;
                }
                else
                {
                        if( x == x->parent->left )
                        {
                                x->parent->left = y;
                        }
                        else
                        {
                                x->parent->right = y;
                        }
                }

                y->left = x;
                x->parent = y;
        }
        else
        {
                printf("can not execute left rotate: right child is nil !\n");
        }
}

void right_rotate( Tree * T, Node * x )  // x's left subtree will be x's new parent
{
        if( x->left != nil )
        {
                Node * y = x->left;

                x->left = y->right;

                if( y->right != nil )
                {
                        y->right->parent = x;
                }

                y->parent = x->parent;

                if( x->parent == nil )
                {
                        *T = y;
                }
                else
                {
                        if( x == x->parent->left )
                        {
                                x->parent->left = y;
                        }
                        else
                        {
                                x->parent->right = y;
                        }

                }

                y->right = x;
                x->parent = y;
        }
        else
        {
                printf("can not execute right rotate : left child is nil !\n");
        }
}

void insert_fix_up( Tree * T, Node * z )
{
        Node * y;

        while( z->parent->color == RED )
        {
                if( z->parent->parent->left == z->parent )       // z's parent is a left subtree
                {
                        y = z->parent->parent->right;

                        if( y->color == RED )                    // case 1
                        {
                                y->color = BLACK;
                                z->parent->color = BLACK;
                                z->parent->parent->color = RED;
                                z = z->parent->parent;
                        }
                        else if( z == z->parent->right )         // case 2
                        {
                                z = z->parent;

                                left_rotate( T, z );
                        }
                        else                                    // case 3
                        {
                                z->parent->color = BLACK;
                                z->parent->parent->color = RED;

                                right_rotate( T, z->parent->parent );
                        }
                }
                else
                {
                        y = z->parent->parent->left;

                        if( y->color == RED )                    // case 1
                        {
                                y->color = BLACK;
                                z->parent->color = BLACK;
                                z->parent->parent->color = RED;
                                z = z->parent->parent;
                        }
                        else if( z == z->parent->left )         // case 2
                        {
                                z = z->parent;

                                right_rotate( T, z );
                        }
                        else                                    // case 3
                        {
                                z->parent->color = BLACK;
                                z->parent->parent->color = RED;

                                left_rotate( T, z->parent->parent );
                        }
                }
        }

        (*T)->color = BLACK;
}

void insert_node( Tree * T, int value )
{
        if( (*T) == NULL )                                //
        {
                (*T) = ( Tree )malloc( sizeof(Node) );
                nil = (Node *)malloc( sizeof(Node) );

                nil->color = BLACK;     // nil init NULL as a globle var ...

                (*T)->left = nil;
                (*T)->right = nil;
                (*T)->parent = nil;
                (*T)->value = value;
                (*T)->color = BLACK;
        }
        else
        {
                Node * x = *T;
                Node * parent = nil;     // save x's parent

                while( x != nil )
                {
                        parent = x;

                        if( value < x->value )
                        {
                                x = x->left;
                        }
                        else if( value > x->value )
                        {
                                x = x->right;
                        }
                        else
                        {
                                printf("value = %d node has existed !\n", value );

                                return ;
                        }
                }

                x = ( Node * )malloc(sizeof(Node));

                x->color = RED;
                x->left = nil;
                x->right = nil;
                x->parent = parent;
                x->value = value;

                if( value < parent->value )
                {
                        parent->left = x;
                }
                else
                {
                        parent->right = x;
                }

                insert_fix_up( T, x );
        }
}

void delete_fix_up( Tree * T, Node * x )
{
        while( x != *T && x->color == BLACK )   // only fix up black node
        {
                if( x == x->parent->left )
                {
                        Node * w = x->parent->right;

                        if( w->color == RED )                   // case 1
                        {
                                w->color = BLACK;
                                x->parent->color = RED;

                                left_rotate( T, x->parent );

                                w = x->parent->right;
                        }

                        if( w->left->color == BLACK && w->right->color == BLACK )  // case 2
                        {
                                w->color = RED;
                                x = x->parent;
                        }

                        else if( w->right->color == BLACK )      // case 3
                        {
                                w->left->color = BLACK;
                                w->color = RED;

                                right_rotate( T, w );

                                w = x->parent->right;
                        }

                        else                                    // case4
                        {
                                w->color = x->parent->color;
                                x->parent->color = BLACK;
                                w->right->color = BLACK;

                                left_rotate( T, x->parent );

                                x = *T;
                        }
                }

                else
                {
                        Node * w = x->parent->left;

                        if( w->color == RED )                   // case 1
                        {
                                w->color = BLACK;
                                x->parent->color = RED;

                                right_rotate( T, x->parent );

                                w = x->parent->left;
                        }

                        if( w->left->color == BLACK && w->right->color == BLACK )  // case 2
                        {
                                w->color = RED;
                                x = x->parent;
                        }

                        else if( w->left->color == BLACK )      // case 3
                        {
                                w->right->color = BLACK;
                                w->color = RED;

                                left_rotate( T, w );

                                w = x->parent->left;
                        }

                        else                                    // case4
                        {
                                w->color = x->parent->color;
                                x->parent->color = BLACK;
                                w->left->color = BLACK;

                                right_rotate( T, x->parent );

                                x = *T;
                        }
                }
        }

        x->color = BLACK;
}

Node * get_node( Tree T, int value )
{
        while( T != NULL && T != nil )
        {
                if( value == T->value ) return T;

                if( value > T->value )
                {
                        T = T->right;
                }
                else
                {
                        T = T->left;
                }
        }

        printf("Not find this node < value : %d >\n", value );

        return NULL;
}

Node * successor( Tree T, Node * x )
{
        if( x->right != nil )           // find the successor from the right subtree
        {
                Node * q = x->right;
                Node * p = x->right;

                while( p->left != nil )
                {
                        q = p->left;
                        p = p->left;
                }

                return q;
        }
        else
        {
                Node * parent = x->parent;

                while( parent != nil && x->value > parent->value )
                {
                        x = x->parent;
                        parent = parent->parent;
                }

                return parent;
        }
}

void delete_node( Tree * T, Node * z )
{
        Node * y;         //  we delete this node
        Node * x;         //  the child of deleted node

        if( z->left == nil || z->right == nil )
        {
                y = z;
        }
        else
        {
                y = successor( *T, z );       // y don't have right child
        }

        if( y->left != nil )
        {
                x = y->left;
        }
        else
        {
                x = y->right;
        }

        x->parent = y->parent;

        if( y->parent == nil )
        {
                *T = x;
        }
        else
        {
                if( y == y->parent->left )
                {
                        y->parent->left = x;
                }
                else
                {
                        y->parent->right = x;
                }
        }

        if( y != z )
        {
                z->value = y->value;
        }

        if( y->color == BLACK ) delete_fix_up( T, x );

        free( y );
}

void mid_traversal( Tree T ) {
        if( T != NULL && T != nil ) {
                mid_traversal( T->left );

                printf("value: %d color: %s\n", T->value, color[T->color] );

                mid_traversal( T->right );
        }
}

int main() {
        Tree t = NULL;

        insert_node( &t, 41 );
        insert_node( &t, 38 );
        insert_node( &t, 31 );
        insert_node( &t, 12 );
        insert_node( &t, 19 );
        insert_node( &t, 8 );

        printf("\n-------------orignal tree ------------\n");
        mid_traversal( t );

        printf("\n-------delete value = 8 node----------\n");
        delete_node( &t, get_node( t, 8 ) );
        mid_traversal( t );

        printf("\n-------delete value = 12 node----------\n");
        delete_node( &t, get_node( t, 12 ) );
        mid_traversal( t );

        printf("\n-------delete value = 19 node----------\n");
        delete_node( &t, get_node( t, 19 ) );
        mid_traversal( t );

        printf("\n-------delete value = 31 node----------\n");
        delete_node( &t, get_node( t, 31 ) );
        mid_traversal( t );


        printf("\n-------delete value = 38 node----------\n");
        delete_node( &t, get_node( t, 38 ) );
        mid_traversal( t );

        printf("\n-------delete value = 41 node----------\n");
        delete_node( &t, get_node( t, 41 ) );
        mid_traversal( t );

        return 0;
}

运行效果

最后

这个算法写的比较仓促，没有考虑优化方面的事情。这个算法是参考这位博主,虽然他写的中有一些错误，但给我提供许多思路。再次感谢以上两位博主。