/* Sample Splaying Routines from Earlier Edition of Weiss (not tested) */

/* Type Declarations for Splay Trees */

   typedef struct splay_node *splay_ptr;

   struct splay_node
   {
      element_type element;
      splay_ptr left;
      splay_ptr right;
      splay_ptr parent;
   };

   typedef splay_ptr SEARCH_TREE;

/* Basic Splay Routine */

   void
   splay( splay_ptry current )
   {
      splay_ptry father;

      father = current->parent;
      while( father != NULL )
      {
         if( father->parent == NULL)
            single_rotate( current );
         else
            double_rotate( current );
         father = current->parent;
      }
   }

/* Single Rotation */

   void
   single_rotate( splay_ptr x )
   {
      if( x->parent->left == x )
         zig_left( x );
      else
         zig_right( x );
   }

/* Single Rotation Between Root and its Left Child */

   void
   zig_left( splay_ptr x );
   {
      splay_ptr p, B;

      P = x->parent;
      B = x->right;

      x->right = p;          /* x's new right child is p */
      x->parent = NULL;      /* x will now be a root */
  
      if(B != NULL )
         B->parent = p;
      p->left = B;
      p->parent = x;
   }