a tree question

[mccaugh at s.cs.uiuc.edu]

Responding to: 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.
> 
 But if there is such a high overhead, how do you gain such efficiency?