src/splaytree.c

   1 /*
   2            An implementation of top-down splaying with sizes
   3              D. Sleator <sleator@cs.cmu.edu>, January 1994.
   4
   5   This extends top-down-splay.c to maintain a size field in each node.
   6   This is the number of nodes in the subtree rooted there.  This makes
   7   it possible to efficiently compute the rank of a key.  (The rank is
   8   the number of nodes to the left of the given key.)  It it also
   9   possible to quickly find the node of a given rank.  Both of these
  10   operations are illustrated in the code below.  The remainder of this
  11   introduction is taken from top-down-splay.c.
  12
  13   "Splay trees", or "self-adjusting search trees" are a simple and
  14   efficient data structure for storing an ordered set.  The data
  15   structure consists of a binary tree, with no additional fields.  It
  16   allows searching, insertion, deletion, deletemin, deletemax,
  17   splitting, joining, and many other operations, all with amortized
  18   logarithmic performance.  Since the trees adapt to the sequence of
  19   requests, their performance on real access patterns is typically even
  20   better.  Splay trees are described in a number of texts and papers
  21   [1,2,3,4].
  22
  23   The code here is adapted from simple top-down splay, at the bottom of
  24   page 669 of [2].  It can be obtained via anonymous ftp from
  25   spade.pc.cs.cmu.edu in directory /usr/sleator/public.
  26
  27   The chief modification here is that the splay operation works even if the
  28   item being splayed is not in the tree, and even if the tree root of the
  29   tree is NULL.  So the line:
  30
  31                               t = splay(i, t);
  32
  33   causes it to search for item with key i in the tree rooted at t.  If it's
  34   there, it is splayed to the root.  If it isn't there, then the node put
  35   at the root is the last one before NULL that would have been reached in a
  36   normal binary search for i.  (It's a neighbor of i in the tree.)  This
  37   allows many other operations to be easily implemented, as shown below.
  38
  39   [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
  40        Harper Collins, 1991, pp 243-251.
  41   [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
  42        JACM Volume 32, No 3, July 1985, pp 652-686.
  43   [3] "Data Structure and Algorithm Analysis", Mark Weiss,
  44        Benjamin Cummins, 1992, pp 119-130.
  45   [4] "Data Structures, Algorithms, and Performance", Derick Wood,
  46        Addison-Wesley, 1993, pp 367-375
  47 */
  48
  49 #include "splaytree.h"
  50 #include <stdlib.h>
  51 #include <assert.h>
  52
  53 #define compare(i,j) ((i)-(j))
  54 /* This is the comparison.                                       */
  55 /* Returns <0 if i<j, =0 if i=j, and >0 if i>j                   */
  56
  57 #define node_size splaytree_size
  58
  59 /* Splay using the key i (which may or may not be in the tree.)
  60  * The starting root is t, and the tree used is defined by rat
  61  * size fields are maintained */
  62 splay_tree * splaytree_splay (splay_tree *t, int i) {
  63     splay_tree N, *l, *r, *y;
  64     int comp, l_size, r_size;
  65
  66     if (t == NULL) return t;
  67     N.left = N.right = NULL;
  68     l = r = &N;
  69     l_size = r_size = 0;
  70
  71     for (;;) {
  72         comp = compare(i, t->key);
  73         if (comp < 0) {
  74             if (t->left == NULL) break;
  75             if (compare(i, t->left->key) < 0) {
  76                 y = t->left;                           /* rotate right */
  77                 t->left = y->right;
  78                 y->right = t;
  79                 t->size = node_size(t->left) + node_size(t->right) + 1;
  80                 t = y;
  81                 if (t->left == NULL) break;
  82             }
  83             r->left = t;                               /* link right */
  84             r = t;
  85             t = t->left;
  86             r_size += 1+node_size(r->right);
  87         } else if (comp > 0) {
  88             if (t->right == NULL) break;
  89             if (compare(i, t->right->key) > 0) {
  90                 y = t->right;                          /* rotate left */
  91                 t->right = y->left;
  92                 y->left = t;
  93                 t->size = node_size(t->left) + node_size(t->right) + 1;
  94                 t = y;
  95                 if (t->right == NULL) break;
  96             }
  97             l->right = t;                              /* link left */
  98             l = t;
  99             t = t->right;
 100             l_size += 1+node_size(l->left);
 101         } else {
 102             break;
 103         }
 104     }
 105     l_size += node_size(t->left);  /* Now l_size and r_size are the sizes of */
 106     r_size += node_size(t->right); /* the left and right trees we just built.*/
 107     t->size = l_size + r_size + 1;
 108
 109     l->right = r->left = NULL;
 110
 111     /* The following two loops correct the size fields of the right path  */
 112     /* from the left child of the root and the right path from the left   */
 113     /* child of the root.                                                 */
 114     for (y = N.right; y != NULL; y = y->right) {
 115         y->size = l_size;
 116         l_size -= 1+node_size(y->left);
 117     }
 118     for (y = N.left; y != NULL; y = y->left) {
 119         y->size = r_size;
 120         r_size -= 1+node_size(y->right);
 121     }
 122
 123     l->right = t->left;                                /* assemble */
 124     r->left = t->right;
 125     t->left = N.right;
 126     t->right = N.left;
 127
 128     return t;
 129 }
 130
 131 splay_tree * splaytree_insert(splay_tree * t, int i, void *data) {
 132 /* Insert key i into the tree t, if it is not already there. */
 133 /* Return a pointer to the resulting tree.                   */
 134     splay_tree * new;
 135
 136     if (t != NULL) {
 137         t = splaytree_splay(t, i);
 138         if (compare(i, t->key)==0) {
 139             return t;  /* it's already there */
 140         }
 141     }
 142     new = (splay_tree *) malloc (sizeof (splay_tree));
 143     assert(new);
 144     if (t == NULL) {
 145         new->left = new->right = NULL;
 146     } else if (compare(i, t->key) < 0) {
 147         new->left = t->left;
 148         new->right = t;
 149         t->left = NULL;
 150         t->size = 1+node_size(t->right);
 151     } else {
 152         new->right = t->right;
 153         new->left = t;
 154         t->right = NULL;
 155         t->size = 1+node_size(t->left);
 156     }
 157     new->key = i;
 158     new->data = data;
 159     new->size = 1 + node_size(new->left) + node_size(new->right);
 160     return new;
 161 }
 162
 163 splay_tree * splaytree_delete(splay_tree *t, int i) {
 164 /* Deletes i from the tree if it's there.               */
 165 /* Return a pointer to the resulting tree.              */
 166     splay_tree * x;
 167     int tsize;
 168
 169     if (t==NULL) return NULL;
 170     tsize = t->size;
 171     t = splaytree_splay(t, i);
 172     if (compare(i, t->key) == 0) {               /* found it */
 173         if (t->left == NULL) {
 174             x = t->right;
 175         } else {
 176             x = splaytree_splay(t->left, i);
 177             x->right = t->right;
 178         }
 179         free(t);
 180         if (x != NULL) {
 181             x->size = tsize-1;
 182         }
 183         return x;
 184     } else {
 185         return t;                         /* It wasn't there */
 186     }
 187 }
 188
 189 #if 0
 190 static splay_tree *find_rank(int r, splay_tree *t) {
 191 /* Returns a pointer to the node in the tree with the given rank.  */
 192 /* Returns NULL if there is no such node.                          */
 193 /* Does not change the tree.  To guarantee logarithmic behavior,   */
 194 /* the node found here should be splayed to the root.              */
 195     int lsize;
 196     if ((r < 0) || (r >= node_size(t))) return NULL;
 197     for (;;) {
 198         lsize = node_size(t->left);
 199         if (r < lsize) {
 200             t = t->left;
 201         } else if (r > lsize) {
 202             r = r - lsize -1;
 203             t = t->right;
 204         } else {
 205             return t;
 206         }
 207     }
 208 }
 209 #endif