a tree question

[gillies at p.cs.uiuc.edu]

> Written  1:58 am  Aug 25, 1989 by mccaugh at s.cs.uiuc.edu in comp.lang.c
> Re: But if there is such a high overhead, how do you gain such efficiency?

Well, splays trees require *no* balancing information.  This saves on
space.  I said that I could acheive 55,000 *comparisons* per second.  In
other words, if the tree has 1000 elements, then log n ~= 10, so that
means only 5500 *searches* per second.

If you've ever implemented AVL trees, you realize what a pain it is.
Splay trees are extremely simple to implement, and have some unique
properties (they are finger trees:  Searches in 'the same
neighborhood' are extremely fast).  For more info, see [1].

[1] D.D. Sleator & R.E. Tarjan, Self-Adjusting Binary Search Trees,
JACM, July 1985, pp. 652-686


Don Gillies, Dept. of Computer Science, University of Illinois
1304 W. Springfield, Urbana, Ill 61801      
ARPA: gillies at cs.uiuc.edu   UUCP: {uunet,harvard}!uiucdcs!gillies