#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;        }