[comp.theory] C code for splay trees

aliao@eagle.wesleyan.edu (09/27/90)

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

kingsley@hpwrce.HP.COM (Kingsley Morse) (09/28/90)

Does anyone know how much cpu is needed to build a splay tree, and how much
cpu is needed to search a splay tree? For example, assume the splay tree 
has P patterns (or "records"), each pattern has D dimensions (or "keys"), 
and each record belongs to one of C classes (or "bins). Then the computational 
complexity of building a tree MAY be something like:

      cpu(build) = (PlnP)*(x**C)*D

and the computational complexity of searching a tree MIGHT be 

     cpu(search) = (lnP)*(x**C)

I've used "x" to denote a data dependent constant. 

If you're interested in this line of thought, you may want to participate in
the "Classification Clearinghouse" posting in sci.math.stat. 


                                                    Kingsley