redblack.c

weis的数据结构的实现方法很经典很强大

#include "redblack.h"
#include <stdlib.h>
#include "fatal.h"


/* START: fig12_14.txt */
        typedef enum ColorType { Red, Black } ColorType;

        struct RedBlackNode
        {
            ElementType  Element;
            RedBlackTree Left;
            RedBlackTree Right;
            ColorType    Color;
        };

        static Position NullNode = NULL;  /* Needs initialization */

        /* Initialization procedure */
        RedBlackTree
        Initialize( void )
        {
            RedBlackTree T;

            if( NullNode == NULL )
            {
                NullNode = malloc( sizeof( struct RedBlackNode ) );
                if( NullNode == NULL )
                    FatalError( "Out of space!!!" );
                NullNode->Left = NullNode->Right = NullNode;
                NullNode->Color = Black;
                NullNode->Element = 12345;
            }

            /* Create the header node */
            T = malloc( sizeof( struct RedBlackNode ) );
            if( T == NULL )
                FatalError( "Out of space!!!" );
            T->Element = NegInfinity;
            T->Left = T->Right = NullNode;
            T->Color = Black;

            return T;
        }
/* END */

        void
        Output( ElementType Element )
        {
            printf( "%d\n", Element );
        }

/* START: fig12_13.txt */
        /* Print the tree, watch out for NullNode, */
        /* and skip header */

        static void
        DoPrint( RedBlackTree T )
        {
            if( T != NullNode )
            {
                DoPrint( T->Left );
                Output( T->Element );
                DoPrint( T->Right );
            }
        }

        void
        PrintTree( RedBlackTree T )
        {
            DoPrint( T->Right );
        }
/* END */

        static RedBlackTree
        MakeEmptyRec( RedBlackTree T )
        {
            if( T != NullNode )
            {
                MakeEmptyRec( T->Left );
                MakeEmptyRec( T->Right );
                free( T );
            }
            return NullNode;
        }

        RedBlackTree
        MakeEmpty( RedBlackTree T )
        {
            T->Right = MakeEmptyRec( T->Right );
            return T;
        }

        Position
        Find( ElementType X, RedBlackTree T )
        {
            if( T == NullNode )
                return NullNode;
            if( X < T->Element )
                return Find( X, T->Left );
            else
            if( X > T->Element )
                return Find( X, T->Right );
            else
                return T;
        }

        Position
        FindMin( RedBlackTree T )
        {
            T = T->Right;
            while( T->Left != NullNode )
                T = T->Left;

            return T;
        }

        Position
        FindMax( RedBlackTree T )
        {
            while( T->Right != NullNode )
                T = T->Right;

            return T;
        }

        /* This function can be called only if K2 has a left child */
        /* Perform a rotate between a node (K2) and its left child */
        /* Update heights, then return new root */

        static Position
        SingleRotateWithLeft( Position K2 )
        {
            Position K1;

            K1 = K2->Left;
            K2->Left = K1->Right;
            K1->Right = K2;

            return K1;  /* New root */
        }

        /* This function can be called only if K1 has a right child */
        /* Perform a rotate between a node (K1) and its right child */
        /* Update heights, then return new root */

        static Position
        SingleRotateWithRight( Position K1 )
        {
            Position K2;

            K2 = K1->Right;
            K1->Right = K2->Left;
            K2->Left = K1;

            return K2;  /* New root */
        }

/* START: fig12_15.txt */
        /* Perform a rotation at node X */
        /* (whose parent is passed as a parameter) */
        /* The child is deduced by examining Item */

        static Position
        Rotate( ElementType Item, Position Parent )
        {

            if( Item < Parent->Element )
                return Parent->Left = Item < Parent->Left->Element ?
                    SingleRotateWithLeft( Parent->Left ) :
                    SingleRotateWithRight( Parent->Left );
            else
                return Parent->Right = Item < Parent->Right->Element ?
                    SingleRotateWithLeft( Parent->Right ) :
                    SingleRotateWithRight( Parent->Right );
        }
/* END */

/* START: fig12_16.txt */
        static Position X, P, GP, GGP;

        static
        void HandleReorient( ElementType Item, RedBlackTree T )
        {
            X->Color = Red;        /* Do the color flip */
            X->Left->Color = Black;
            X->Right->Color = Black;

            if( P->Color == Red )  /* Have to rotate */
            {
                GP->Color = Red;
                if( (Item < GP->Element) != (Item < P->Element) )
                    P = Rotate( Item, GP );  /* Start double rotate */
                X = Rotate( Item, GGP );
                X->Color = Black;
            }
            T->Right->Color = Black;  /* Make root black */
        }

        RedBlackTree
        Insert( ElementType Item, RedBlackTree T )
        {
            X = P = GP = T;
            NullNode->Element = Item;
            while( X->Element != Item )  /* Descend down the tree */
            {
                GGP = GP; GP = P; P = X;
                if( Item < X->Element )
                    X = X->Left;
                else
                    X = X->Right;
                if( X->Left->Color == Red && X->Right->Color == Red )
                    HandleReorient( Item, T );
            }

            if( X != NullNode )
                return NullNode;  /* Duplicate */

            X = malloc( sizeof( struct RedBlackNode ) );
            if( X == NULL )
                FatalError( "Out of space!!!" );
            X->Element = Item;
            X->Left = X->Right = NullNode;

            if( Item < P->Element )  /* Attach to its parent */
                P->Left = X;
            else
                P->Right = X;
            HandleReorient( Item, T ); /* Color it red; maybe rotate */

            return T;
        }
/* END */

        RedBlackTree
        Remove( ElementType Item, RedBlackTree T )
        {
            printf( "Remove is unimplemented\n" );
            if( Item )
                return T;
            return T;
        }

        ElementType
        Retrieve( Position P )
        {
            return P->Element;
        }