Back to index

plt-scheme  4.2.1
splay.c
Go to the documentation of this file.
00001 /* 
00002    Provides OR requires:
00003     Tree (with left and right Tree fields)
00004     Splay_Item
00005     Set_Splay_Item
00006    Provides, can can be renamed via macros (to support
00007                     multiplue uses of the file):
00008     splay
00009     splay_insert
00010     splay_delete
00011 */
00012 /*
00013                 An implementation of top-down splaying
00014                     D. Sleator <sleator@cs.cmu.edu>
00015                             March 1992
00016 
00017   "Splay trees", or "self-adjusting search trees" are a simple and
00018   efficient data structure for storing an ordered set.  The data
00019   structure consists of a binary tree, without parent pointers, and no
00020   additional fields.  It allows searching, insertion, deletion,
00021   deletemin, deletemax, splitting, joining, and many other operations,
00022   all with amortized logarithmic performance.  Since the trees adapt to
00023   the sequence of requests, their performance on real access patterns is
00024   typically even better.  Splay trees are described in a number of texts
00025   and papers [1,2,3,4,5].
00026 
00027   The code here is adapted from simple top-down splay, at the bottom of
00028   page 669 of [3].  It can be obtained via anonymous ftp from
00029   spade.pc.cs.cmu.edu in directory /usr/sleator/public.
00030 
00031   The chief modification here is that the splay operation works even if the
00032   item being splayed is not in the tree, and even if the tree root of the
00033   tree is NULL.  So the line:
00034 
00035                               t = splay(i, t);
00036 
00037   causes it to search for item with key i in the tree rooted at t.  If it's
00038   there, it is splayed to the root.  If it isn't there, then the node put
00039   at the root is the last one before NULL that would have been reached in a
00040   normal binary search for i.  (It's a neighbor of i in the tree.)  This
00041   allows many other operations to be easily implemented, as shown below.
00042 
00043   [1] "Fundamentals of data structures in C", Horowitz, Sahni,
00044        and Anderson-Freed, Computer Science Press, pp 542-547.
00045   [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
00046        Harper Collins, 1991, pp 243-251.
00047   [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
00048        JACM Volume 32, No 3, July 1985, pp 652-686.
00049   [4] "Data Structure and Algorithm Analysis", Mark Weiss,
00050        Benjamin Cummins, 1992, pp 119-130.
00051   [5] "Data Structures, Algorithms, and Performance", Derick Wood,
00052        Addison-Wesley, 1993, pp 367-375.
00053 */
00054 
00055 #ifndef Tree
00056 typedef struct tree_node Tree;
00057 struct tree_node {
00058     Tree * left, * right;
00059     unsigned long item;
00060     void *data;
00061 };
00062 # define Splay_Item(t) t->item
00063 # define Set_Splay_Item(t, v) t->item = v
00064 #endif
00065 
00066 static Tree * splay (unsigned long i, Tree * t) {
00067 /* Simple top down splay, not requiring i to be in the tree t.  */
00068 /* What it does is described above.                             */
00069     Tree N, *l, *r, *y;
00070     if (t == NULL) return t;
00071     N.left = N.right = NULL;
00072     l = r = &N;
00073 
00074     for (;;) {
00075        if (i < Splay_Item(t)) {
00076            if (t->left == NULL) break;
00077            if (i < Splay_Item(t->left)) {
00078               y = t->left;                           /* rotate right */
00079               t->left = y->right;
00080               y->right = t;
00081               t = y;
00082               if (t->left == NULL) break;
00083            }
00084            r->left = t;                               /* link right */
00085            r = t;
00086            t = t->left;
00087        } else if (i > Splay_Item(t)) {
00088            if (t->right == NULL) break;
00089            if (i > Splay_Item(t->right)) {
00090               y = t->right;                          /* rotate left */
00091               t->right = y->left;
00092               y->left = t;
00093               t = y;
00094               if (t->right == NULL) break;
00095            }
00096            l->right = t;                              /* link left */
00097            l = t;
00098            t = t->right;
00099        } else {
00100            break;
00101        }
00102     }
00103     l->right = t->left;                                /* assemble */
00104     r->left = t->right;
00105     t->left = N.right;
00106     t->right = N.left;
00107     return t;
00108 }
00109 
00110 static Tree * splay_insert(unsigned long i, Tree * new, Tree * t) {
00111 /* Insert i into the tree t, unless it's already there.    */
00112 /* Return a pointer to the resulting tree.                 */
00113     Set_Splay_Item(new, i);
00114     if (t == NULL) {
00115        new->left = new->right = NULL;
00116        return new;
00117     }
00118     t = splay(i,t);
00119     if (i < Splay_Item(t)) {
00120        new->left = t->left;
00121        new->right = t;
00122        t->left = NULL;
00123        return new;
00124     } else if (i > Splay_Item(t)) {
00125        new->right = t->right;
00126        new->left = t;
00127        t->right = NULL;
00128        return new;
00129     } else { /* We get here if it's already in the tree */
00130              /* Don't add it again                      */
00131        return t;
00132     }
00133 }
00134 
00135 #ifndef OMIT_SPLAY_DELETE
00136 
00137 static Tree * splay_delete(unsigned long i, Tree * t) {
00138 /* Deletes i from the tree if it's there.               */
00139 /* Return a pointer to the resulting tree.              */
00140     Tree * x;
00141     if (t==NULL) return NULL;
00142     t = splay(i,t);
00143     if (i == Splay_Item(t)) {               /* found it */
00144        if (t->left == NULL) {
00145            x = t->right;
00146        } else {
00147            x = splay(i, t->left);
00148            x->right = t->right;
00149        }
00150        return x;
00151     }
00152     return t;                         /* It wasn't there */
00153 }
00154 
00155 #endif