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
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to splaytree.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / lighttpd / src