a tree question

[gillies at m.cs.uiuc.edu]

One of the easiest trees to implement is the Splay tree, but there is
a high overhead (on a 1.5 MIPS Mac II, I could only achieve 55,000
comparisons [not *searches*] per second [searching numbers]).  But an
entire implementation is less than 60 lines of C code.  Splay trees
accomplish insert, delete, join, lookup, all in amortized O(log n)
time.

Send e-mail if you're interested.  The main reference is Tarjan &
Sleator, Siam J. on Computing, 1984 [sometime].

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