1 /* 2 An implementation of top-down splaying with sizes 3 D. Sleator <[email protected]>, 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 "algo_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 210