home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pctchnqs / 1992 / number1 / splay.c < prev    next >
C/C++ Source or Header  |  1992-02-06  |  5KB  |  200 lines
  1. /* Splay tree implementation
  2.    Translated from the initial Pascal version by Andrew M. Liao
  3.  
  4. The splay routines are called in the following manner:
  5.  
  6.     root=splay(arg,root);           Search
  7.     root=splayinsert(arg,root);     Insert
  8.     root=splaydelete(arg,root);     Delete
  9. */
  10. #define TESTING        /* comment if not testing */
  11. #include <stdlib.h>
  12. #define key long
  13.  
  14. struct node { long data; struct node *left,*right; };
  15. struct nrec { struct node *left,*right; };
  16.  
  17. #define false 0
  18. #define true 1
  19.  
  20. struct node *rrot(root)
  21. struct node *root;
  22. { struct node *temp,*temp1,*p;
  23.   p=root;
  24.   if (p!=NULL)
  25.     { if (p->left!=NULL)
  26.     { temp=p; temp1=p->left->right;
  27.       p=temp->left; p->right=temp; temp->left=temp1;
  28.     }
  29.     }
  30.   return(p);
  31. }
  32.  
  33. struct node *lrot(root)
  34. struct node *root;
  35. { struct node *temp,*temp1,*p;
  36.   p=root;
  37.   if (p!=NULL)
  38.     { if (p->right!=NULL)
  39.     { temp=p; temp1=p->right->left;
  40.       p=temp->right; p->left=temp; temp->right=temp1;
  41.     }
  42.     }
  43.   return(p);
  44. }
  45.  
  46. struct node *lnkright(root,r)
  47. struct node *root;
  48. struct nrec *r;
  49. { struct node *temp,*p;
  50.   p=root;
  51.   if (p->left!=NULL)
  52.     { temp=p->left; p->left=NULL;
  53.       if (r->left==NULL)
  54.         { r->left=p; r->right=p; }
  55.       else
  56.         { r->right->left=p; r->right=r->right->left; }
  57.       p=temp;
  58.     }
  59.    return(p);
  60. }
  61.  
  62. struct node *lnkleft(root,l)
  63. struct node *root;
  64. struct nrec *l;
  65. { struct node *temp,*p;
  66.   p=root;
  67.   if (p->right!=NULL)
  68.     { temp=p->right; p->right=NULL;
  69.       if (l->left==NULL)
  70.         { l->left=p; l->right=p; }
  71.       else
  72.         { l->right->right=p; l->right=l->right->right; }
  73.       p=temp;
  74.     }
  75.    return(p);
  76. }
  77.  
  78. struct node *assemble(p,l,r)
  79. struct node *p;
  80. struct nrec *l,*r;
  81. { struct node *temp,*temp1;
  82.   temp=p->left; temp1=p->right;
  83.   if (l->left!=NULL)
  84.     { p->left=l->left; l->right->right=temp; }
  85.   if (r->left!=NULL)
  86.     {  p->right=r->left; r->right->left=temp1;}
  87. }
  88.  
  89. struct node *splay(x,root)
  90. key x;
  91. struct node *root;
  92. { struct nrec l,r;              /* Temp subtrees */
  93.   struct node *p;
  94.   int done;                     /* Process boolean */
  95.   p=root;
  96.   l.left=l.right=r.left=r.right=NULL;
  97.   done=false;
  98.   if (p!=NULL)
  99.     { do
  100.        {if (x<p->data)
  101.       { if (p->left!=NULL)
  102.           { if (x==p->left->data) p=lnkright(p,&r);
  103.         else
  104.         if (x<p->left->data)
  105.           { p=rrot(p); p=lnkright(p,&r); }
  106.         else
  107.         if (x>p->left->data)
  108.           { p=lnkright(p,&r); p=lnkleft(p,&l); }
  109.           } else done=true;
  110.       }
  111.     else
  112.     if (x>p->data)
  113.       { if (p->right!=NULL)
  114.           { if (x==p->right->data) p=lnkleft(p,&l);
  115.         else
  116.         if (x>p->right->data)
  117.           { p=lrot(p); p=lnkleft(p,&l); }
  118.         else
  119.         if (x<p->right->data)
  120.           { p=lnkleft(p,&l); p=lnkright(p,&r); }
  121.           } else done=true;
  122.       }
  123.     }
  124.       while ((p->data!=x) && !done);
  125.       assemble(p,&l,&r);
  126.     }
  127.    return(p);
  128. }
  129.  
  130. struct node *splayinsert(x,root)
  131. key x;
  132. struct node *root;
  133. { struct node *p;
  134.   struct node foo;
  135.   root=splay(x,root);
  136.   if ((root==NULL) || (root->data!=x))
  137.     { p=(struct node *) malloc(sizeof(foo));
  138.       p->data=x; p->left=p->right=NULL;
  139.       if ((root!=NULL) && (x<root->data))
  140.         { p->right=root; p->left=root->left;
  141.           root->left=NULL;
  142.         }
  143.       else
  144.       if ((root!=NULL) && (x>root->data))
  145.         { p->left=root; p->right=root->right;
  146.       root->right=NULL;
  147.     }
  148.       root=p;
  149.      }
  150.   return(root);
  151. }
  152.  
  153. /* NOTE: SPLAYDELETE is currently set up to deal with integer keys.
  154.    if you want to deal with strings, you will have to build an
  155.    appropriate character array all of whose bytes have the maximum
  156.    ASCII value on you machine.   */
  157. struct node *splaydelete(x,root)
  158. key x;
  159. struct node *root;
  160. { struct node *temp1,*temp2;
  161.   key max=2147483647;
  162.  
  163.   root=splay(x,root);
  164.   if ((root!=NULL) && (root->data==x))
  165.     { temp1=root->left; temp2=root->right;
  166.       if (temp1!=NULL)
  167.     { temp1=splay(max,temp1);
  168.       temp1->right=temp2;
  169.     } else temp1=temp2;
  170.       free((char *) root);
  171.       root=temp1;
  172.     }
  173.   return(root);
  174. }
  175.  
  176. #ifdef TESTING
  177. void main (void) {
  178.   int x;
  179.   key z;
  180.   struct node *root = NULL;
  181.  
  182.   puts ("fill tree");
  183.   root = splayinsert (-1L, root);
  184.   for (x=0; x<10; x++) {
  185.     z = random (10);
  186.     root = splayinsert (z, root);
  187.     printf ("%02ld  ", root->data);
  188.   }
  189.   puts ("\nsearch tree");
  190.  
  191.   for (x=0; x<100; x++) {
  192.     z = random (10);
  193.     root = splay (z, root);
  194.     printf ("Search for %02ld. %sfound.  Root = %02ld\n", z,
  195.        (root->data == z) ? "    " : "Not ", root->data);
  196.   }
  197.   puts ("\ndone");
  198. }
  199. #endif
  200.