summaryrefslogtreecommitdiff
path: root/src/splaytree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/splaytree.c')
-rw-r--r--src/splaytree.c210
1 files changed, 0 insertions, 210 deletions
diff --git a/src/splaytree.c b/src/splaytree.c
deleted file mode 100644
index 5d6a2b40..00000000
--- a/src/splaytree.c
+++ /dev/null
@@ -1,210 +0,0 @@
-/*
- An implementation of top-down splaying with sizes
- D. Sleator <sleator@cs.cmu.edu>, January 1994.
-
- This extends top-down-splay.c to maintain a size field in each node.
- This is the number of nodes in the subtree rooted there. This makes
- it possible to efficiently compute the rank of a key. (The rank is
- the number of nodes to the left of the given key.) It it also
- possible to quickly find the node of a given rank. Both of these
- operations are illustrated in the code below. The remainder of this
- introduction is taken from top-down-splay.c.
-
- "Splay trees", or "self-adjusting search trees" are a simple and
- efficient data structure for storing an ordered set. The data
- structure consists of a binary tree, with no additional fields. It
- allows searching, insertion, deletion, deletemin, deletemax,
- splitting, joining, and many other operations, all with amortized
- logarithmic performance. Since the trees adapt to the sequence of
- requests, their performance on real access patterns is typically even
- better. Splay trees are described in a number of texts and papers
- [1,2,3,4].
-
- The code here is adapted from simple top-down splay, at the bottom of
- page 669 of [2]. It can be obtained via anonymous ftp from
- spade.pc.cs.cmu.edu in directory /usr/sleator/public.
-
- The chief modification here is that the splay operation works even if the
- item being splayed is not in the tree, and even if the tree root of the
- tree is NULL. So the line:
-
- t = splay(i, t);
-
- causes it to search for item with key i in the tree rooted at t. If it's
- there, it is splayed to the root. If it isn't there, then the node put
- at the root is the last one before NULL that would have been reached in a
- normal binary search for i. (It's a neighbor of i in the tree.) This
- allows many other operations to be easily implemented, as shown below.
-
- [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
- Harper Collins, 1991, pp 243-251.
- [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
- JACM Volume 32, No 3, July 1985, pp 652-686.
- [3] "Data Structure and Algorithm Analysis", Mark Weiss,
- Benjamin Cummins, 1992, pp 119-130.
- [4] "Data Structures, Algorithms, and Performance", Derick Wood,
- Addison-Wesley, 1993, pp 367-375
-*/
-
-#include <stdlib.h>
-#include <assert.h>
-#include "splaytree.h"
-
-#define compare(i,j) ((i)-(j))
-/* This is the comparison. */
-/* Returns <0 if i<j, =0 if i=j, and >0 if i>j */
-
-#define node_size splaytree_size
-
-/* Splay using the key i (which may or may not be in the tree.)
- * The starting root is t, and the tree used is defined by rat
- * size fields are maintained */
-splay_tree * splaytree_splay (splay_tree *t, int i) {
- splay_tree N, *l, *r, *y;
- int comp, root_size, l_size, r_size;
-
- if (t == NULL) return t;
- N.left = N.right = NULL;
- l = r = &N;
- root_size = node_size(t);
- l_size = r_size = 0;
-
- for (;;) {
- comp = compare(i, t->key);
- if (comp < 0) {
- if (t->left == NULL) break;
- if (compare(i, t->left->key) < 0) {
- y = t->left; /* rotate right */
- t->left = y->right;
- y->right = t;
- t->size = node_size(t->left) + node_size(t->right) + 1;
- t = y;
- if (t->left == NULL) break;
- }
- r->left = t; /* link right */
- r = t;
- t = t->left;
- r_size += 1+node_size(r->right);
- } else if (comp > 0) {
- if (t->right == NULL) break;
- if (compare(i, t->right->key) > 0) {
- y = t->right; /* rotate left */
- t->right = y->left;
- y->left = t;
- t->size = node_size(t->left) + node_size(t->right) + 1;
- t = y;
- if (t->right == NULL) break;
- }
- l->right = t; /* link left */
- l = t;
- t = t->right;
- l_size += 1+node_size(l->left);
- } else {
- break;
- }
- }
- l_size += node_size(t->left); /* Now l_size and r_size are the sizes of */
- r_size += node_size(t->right); /* the left and right trees we just built.*/
- t->size = l_size + r_size + 1;
-
- l->right = r->left = NULL;
-
- /* The following two loops correct the size fields of the right path */
- /* from the left child of the root and the right path from the left */
- /* child of the root. */
- for (y = N.right; y != NULL; y = y->right) {
- y->size = l_size;
- l_size -= 1+node_size(y->left);
- }
- for (y = N.left; y != NULL; y = y->left) {
- y->size = r_size;
- r_size -= 1+node_size(y->right);
- }
-
- l->right = t->left; /* assemble */
- r->left = t->right;
- t->left = N.right;
- t->right = N.left;
-
- return t;
-}
-
-splay_tree * splaytree_insert(splay_tree * t, int i, void *data) {
-/* Insert key i into the tree t, if it is not already there. */
-/* Return a pointer to the resulting tree. */
- splay_tree * new;
-
- if (t != NULL) {
- t = splaytree_splay(t, i);
- if (compare(i, t->key)==0) {
- return t; /* it's already there */
- }
- }
- new = (splay_tree *) malloc (sizeof (splay_tree));
- assert(new);
- if (t == NULL) {
- new->left = new->right = NULL;
- } else if (compare(i, t->key) < 0) {
- new->left = t->left;
- new->right = t;
- t->left = NULL;
- t->size = 1+node_size(t->right);
- } else {
- new->right = t->right;
- new->left = t;
- t->right = NULL;
- t->size = 1+node_size(t->left);
- }
- new->key = i;
- new->data = data;
- new->size = 1 + node_size(new->left) + node_size(new->right);
- return new;
-}
-
-splay_tree * splaytree_delete(splay_tree *t, int i) {
-/* Deletes i from the tree if it's there. */
-/* Return a pointer to the resulting tree. */
- splay_tree * x;
- int tsize;
-
- if (t==NULL) return NULL;
- tsize = t->size;
- t = splaytree_splay(t, i);
- if (compare(i, t->key) == 0) { /* found it */
- if (t->left == NULL) {
- x = t->right;
- } else {
- x = splaytree_splay(t->left, i);
- x->right = t->right;
- }
- free(t);
- if (x != NULL) {
- x->size = tsize-1;
- }
- return x;
- } else {
- return t; /* It wasn't there */
- }
-}
-
-splay_tree *find_rank(int r, splay_tree *t) {
-/* Returns a pointer to the node in the tree with the given rank. */
-/* Returns NULL if there is no such node. */
-/* Does not change the tree. To guarantee logarithmic behavior, */
-/* the node found here should be splayed to the root. */
- int lsize;
- if ((r < 0) || (r >= node_size(t))) return NULL;
- for (;;) {
- lsize = node_size(t->left);
- if (r < lsize) {
- t = t->left;
- } else if (r > lsize) {
- r = r - lsize -1;
- t = t->right;
- } else {
- return t;
- }
- }
-}
-
-
View Lorry Controller Status