Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!eagle.wesleyan.edu!aliao
From: aliao@eagle.wesleyan.edu
Newsgroups: comp.theory
Subject: C code for splay trees
Message-ID: <1990Sep26.223953.33593@eagle.wesleyan.edu>
Date: 27 Sep 90 03:39:53 GMT
Lines: 170

The following is my version of the splay tree implementation if
anyone is interested.  It is based on the description provided in
the 1985 JACM paper by Bob Tarjan And Dan Sleator.
The splay routines are called in the following manner:

	root=splay(arg,root);		/* Search */
	root=splayinsert(arg,root);	/* Insert */
	root=splaydelete(arg,root);	/* Delete */

/* Splay tree implementation
   Translated from the initial Pascal version by Andrew M. Liao
*/
struct node { char *data; struct node *left,*right; }; 
struct nrec { struct node *left,*right; };
#define false 0
#define true 1

struct node *rrot(root)
struct node *root;
{ struct node *temp,*temp1,*p;
  p=root;
  if (p!=NULL)
    { if (p->left!=NULL)
        { temp=p; temp1=p->left->right;
          p=temp->left; p->right=temp; temp->left=temp1;
        }
    }
  return(p);
}

struct node *lrot(root)
struct node *root;
{ struct node *temp,*temp1,*p;
  p=root;
  if (p!=NULL)
    { if (p->right!=NULL)
        { temp=p; temp1=p->right->left;
          p=temp->right; p->left=temp; temp->right=temp1;
        }
    }
  return(p);
}

struct node *lnkright(root,r)
struct node *root;
struct nrec *r;
{ struct node *temp,*p;
  p=root;
  if (p->left!=NULL)
    { temp=p->left; p->left=NULL;
      if (r->left==NULL)
        { r->left=p; r->right=p; }
      else
        { r->right->left=p; r->right=r->right->left; }
      p=temp;
    }
   return(p);
}

struct node *lnkleft(root,l)
struct node *root;
struct nrec *l;
{ struct node *temp,*p;
  p=root;
  if (p->right!=NULL)
    { temp=p->right; p->right=NULL;
      if (l->left==NULL)
        { l->left=p; l->right=p; }
      else
        { l->right->right=p; l->right=l->right->right; }
      p=temp;
    }
   return(p);
}

struct node *assemble(p,l,r)
struct node *p;
struct nrec *l,*r;
{ struct node *temp,*temp1;
  temp=p->left; temp1=p->right;
  if (l->left!=NULL)
    { p->left=l->left; l->right->right=temp; }
  if (r->left!=NULL)
    {  p->right=r->left; r->right->left=temp1;}
}

struct node *splay(x,root)
key x;
struct node *root;
{ struct nrec l,r;              /* Temp subtrees */
  struct node *p;
  int done;                     /* Process boolean */
  p=root;
  l.left=l.right=r.left=r.right=NULL;
  done=false;
  if (p!=NULL)
    { do
       {if (x<p->data)
          { if (p->left!=NULL)
              { if (x==p->left->data) p=lnkright(p,&r);
                else
                if (x<p->left->data) { p=rrot(p); p=lnkright(p,&r); }
                else
                if (x>p->left->data)
                  { p=lnkright(p,&r); p=lnkleft(p,&l); }
              } else done=true;
          }
        else
        if (x>p->data)
          { if (p->right!=NULL)
              { if (x==p->right->data) p=lnkleft(p,&l);
                else
                if (x>p->right->data) { p=lrot(p); p=lnkleft(p,&l); }
                else
                if (x<p->right->data)
                  { p=lnkleft(p,&l); p=lnkright(p,&r); }
              } else done=true;
          }
        }
      while ((p->data!=x) && !done);
      assemble(p,&l,&r);
    }
   return(p);
}

struct node *splayinsert(x,root)
key x;
struct node *root;
{ struct node *p;
  struct node foo;
  root=splay(x,root);
  if ((root==NULL) || (root->data!=x))
    { p=(struct node *) malloc(sizeof(foo));
      p->data=x; p->left=p->right=NULL;
      if ((root!=NULL) && (x<root->data))
        { p->right=root; p->left=root->left;
          root->left=NULL;
        }
      else
      if ((root!=NULL) && (x>root->data))
        { p->left=root; p->right=root->right;
          root->right=NULL;
        }
      root=p;
     }
  return(root);
}

/* NOTE: SPLAYDELETE is currently set up to deal with integer keys.
   if you want to deal with strings, you will have to build an
   appropriate character array all of whose bytes have the maximum
   ASCII value on you machine.   */ 
struct node *splaydelete(x,root)
key x;
struct node *root;
{ struct node *temp1,*temp2;
  key max=2147483647;

  root=splay(x,root);
  if ((root!=NULL) && (root->data==x))
    { temp1=root->left; temp2=root->right;
      if (temp1!=NULL)
        { temp1=splay(max,temp1);
          temp1->right=temp2;
        } else temp1=temp2;
      free((char *) root);
      root=temp1;
    }
  return(root);
}