Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!s.cs.uiuc.edu!mccaugh
From: mccaugh@s.cs.uiuc.edu
Newsgroups: comp.lang.c
Subject: Re: a tree question
Message-ID: <207600033@s.cs.uiuc.edu>
Date: 25 Aug 89 06:58:00 GMT
References: <1074@taurus.BITNET>
Lines: 11
Nf-ID: #R:taurus.BITNET:1074:s.cs.uiuc.edu:207600033:000:474
Nf-From: s.cs.uiuc.edu!mccaugh    Aug 25 01:58:00 1989


Responding to: gillies@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?