#include sptree.h void spdelete(n, q) SPBLK *n; SPTREE *q; SPBLK *spdeq(n) SPBLK *n; int spempty(q) SPTREE *q; SPBLK *spenq(n, q) SPBLK *n; SPTREE *q; SPBLK *spenqafter(n, n1, q) SPBLK *n, *n1; SPTREE *q; SPBLK *spenqbefore(n, n1, q) SPBLK *n, *n1; SPTREE *q; SPBLK *spenqprior(n, q) SPBLK *n; SPTREE *q; SPBLK *spfhead(q) SPTREE *q; SPBLK *spfnext(n) SPBLK *n; SPBLK *spfprev(n) SPBLK *n; SPBLK *spftail(q) SPTREE *q; SPBLK *sphead(q) SPTREE *q; SPTREE *spinit(); SPBLK *spinstall(key, data, datb, q) char *key, *data, *datb; SPTREE *q; void splay(n, q) SPBLK *n; SPTREE *q; SPBLK *splookup(key, q) char *key; SPTREE *q; SPBLK *spnext(n, q) SPBLK *n; SPTREE *q; SPBLK *spprev(n, q) SPBLK *n; SPTREE *q; void sprscan(f, n, q) int (*f)(); SPBLK *n; SPTREE *q; void spscan(f, n, q) int (*f)(); SPBLK *n; SPTREE *q; char *spstats(q) SPTREE *q;
The SPTREE structure declared in sptree.h should only be handled indirectly. A pointer to an SPTREE is returned by spinit and should be handed blindly to other access functions.
The nodes in a splay tree are defined by the following structure, declared in sptree.h.
typedef struct _spblk SPBLK;
typedef struct _spblk
{
.
.
.
char *key;
char *data;
char *datb;
};
You should only refer to the key, data and datb members.
The key is interpreted as a pointer to a null terminated string, and ordering is determined by calls to the usual strcmp routine.
No meaning is associated with the auxiliary members data or datb, and you are free to stuff them with whatever good conscience and a legal cast will allow.
Spdelete deletes the node n from the tree q. The resulting tree is splayed around a new root, which is the successor to n.
Spdeq removes and returns the head node from the sub-tree rooted at node n.
Spempty returns non-zero if the tree q has no members.
Spenq inserts node n into tree q after all other nodes with the same key. When this is done, n will be the root of the tree.
Spenqafter inserts node n as the immediate sucessor of node n1 in tree q. In so doing, n1 becomes the root of the tree with n as its right son.
Spenqbefore inserts node n as the immediate predecessor of node n1 in tree q. In doing so, n1 becomes the root of the tree with n as its left son.
Spenqprior inserts node n into the tree q before all other nodes with the same key; after this is done, n will be the root of the tree.
Spfhead returns a pointer to the head element in the tree q, but does not splay it to the root.
Spfnext returns a pointer to the immediate successor of node n without doing any reorganization.
Spfprev returns a pointer to the immediate predecessor of node n without doing any reoganization.
Spftail returns a reference to the last node in the tree q without doing any reorganization.
Sphead returns a pointer to the head event in the tree q. The returned node is made the root of the tree, as if q had been splayed around n.
Spinit creates a new splay tree using a malloc-like routine named emalloc that must be supplied by the user.
Spinstall inserts an entry with the key value pointed to by key with the auxiliary values data and datb into the tree q. If a node with the key value already exists, its auxiliarly values are replaced. If the node does not already exist, a new one is allocated with malloc-like function named emalloc that must be supplied by the user.
Splay reorganizes the tree so that node n becomes the root of the tree in q. Results are unpredicatable if n is not in q to start with. Q is split from n up to the old root, with all nodes to the left of n ending up in the left sub-tree, and all nodes to the right of n ending up in the right sub-tree. The left branch of the right sub-tree and the right branch of the left sub-tree are shortened in the process.
Splookup searches for a node containing the key value pointed to by key in the tree q. A found node is splayed to the root and returned. If the key is not found, the function returns NULL and no reorganization is done.
Spnext returns a pointer to the successor of n in q. The successor becomes the root of the tree.
Spprev returns the predecessor of n in q. The predecessor becomes the root.
Sprscan applies the function f starting at node n to the members of the tree q in reverse order. If n is NULL, then the scan starts at the tail of the tree. The tree is not reorganized during the reverse scan. The function is called with one argument, a pointer to an SPBLK. Its return value is ignored.
Spscan applies the function f starting at node n in tree q and all successive nodes, in order. If n is NULL, then the scan starts at the head of the tree. The tree is not reorganized during the scan. The function is called with one argument, a pointer to an SPBLK. Its return value is ignored.
Spstats returns a string of statistics on the activities in the tree q. It shows how many times splookup was called, and how many comparisons were needed per call, the number of nodes that have been added with spenq and the number of comparisons needed per call, and finally, the number of splay operations performed, and the number of loops done in each splay. These statistics give an indication of the average effective depth of the tree for various operations. The function returns a pointer to a static buffer that is overwritten with each call.
Self Adjusting Binary Trees, by D. D. Sleator and R. E. Tarjan, Proc. ACM SIGACT Symposium on Theory of Computing (Boston, Apr 1983) 235-245.
More operations on priority queues were added to help support discrete event simulation. See, for example Chapter 14 of
Introduction to Simula 67, by Gunther Lamprecht, Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
and Chapter 9 of
Simula Begin, by Graham M. Birtwistle, et al, Studentlitteratur, Lund, 1979.
Splay trees are compared with other data structures in
An Empirical Comparison of Priority-Queue and Event-Set Implementations, by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311.