treap.c

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


        struct TreapNode
        {
            ElementType Element;
            Treap       Left;
            Treap       Right;
            int         Priority;
        };

        Position NullNode = NULL;  /* Needs initialization */

/* START: fig12_39.txt */
        Treap
        Initialize( void )
        {
            if( NullNode == NULL )
            {
                NullNode = malloc( sizeof( struct TreapNode ) );
                if( NullNode == NULL )
                    FatalError( "Out of space!!!" );
                NullNode->Left = NullNode->Right = NullNode;
                NullNode->Priority = Infinity;
            }
            return NullNode;
        }
/* END */

        /* Use ANSI C random number generator for simplicity */

        int
        Random( void )
        {
            return rand( ) -  1;
        }

        Treap
        MakeEmpty( Treap T )
        {
            if( T != NullNode )
            {
                MakeEmpty( T->Left );
                MakeEmpty( T->Right );
                free( T );
            }
            return NullNode;
        }

        void
        PrintTree( Treap T )
        {
            if( T != NullNode )
            {
                PrintTree( T->Left );
                printf( "%d ", T->Element );
                PrintTree( T->Right );
            }
        }

        Position
        Find( ElementType X, Treap 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( Treap T )
        {
            if( T == NullNode )
                return NullNode;
            else
            if( T->Left == NullNode )
                return T;
            else
                return FindMin( T->Left );
        }

        Position
        FindMax( Treap T )
        {
            if( T != NullNode )
                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_40.txt */
        Treap
        Insert( ElementType Item, Treap T )
        {
            if( T == NullNode )
            {
                /* Create and return a one-node tree */
                T = malloc( sizeof( struct TreapNode ) );
                if( T == NULL )
                    FatalError( "Out of space!!!" );
                else
                {
                    T->Element = Item; T->Priority = Random( );
                    T->Left = T->Right = NullNode;
                }
            }
            else
            if( Item < T->Element )
            {
                T->Left = Insert( Item, T->Left );
                if( T->Left->Priority < T->Priority )
                    T = SingleRotateWithLeft( T );
            }
            else
            if( Item > T->Element )
            {
                T->Right = Insert( Item, T->Right );
                if( T->Right->Priority < T->Priority )
                    T = SingleRotateWithRight( T );
            }

            /* Otherwise it's a duplicate; do nothing */

            return T;
        }
/* END */

/* START: fig12_41.txt */
        Treap
        Remove( ElementType Item, Treap T )
        {
            if( T != NullNode )
            {
                if( Item < T->Element )
                    T->Left = Remove( Item, T->Left );
                else
                if( Item > T->Element )
                    T->Right = Remove( Item, T->Right );
                else
                {
                    /* Match found */
                    if( T->Left->Priority < T->Right->Priority )
                        T = SingleRotateWithLeft( T );
                    else
                        T = SingleRotateWithRight( T );

                    if( T != NullNode )    /* Continue on down */
                        T = Remove( Item, T );
                    else
                    {
                        /* At a leaf */
                        free( T->Left );
                        T->Left = NullNode;
                    }
                }
            }
            return T;
        }
/* END */

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