Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!gillies
From: gillies@m.cs.uiuc.edu
Newsgroups: comp.lang.c
Subject: Re: a tree question
Message-ID: <4700041@m.cs.uiuc.edu>
Date: 23 Aug 89 01:52:00 GMT
References: <1074@taurus.BITNET>
Lines: 14
Nf-ID: #R:taurus.BITNET:1074:m.cs.uiuc.edu:4700041:000:637
Nf-From: m.cs.uiuc.edu!gillies    Aug 22 20:52:00 1989


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@cs.uiuc.edu   UUCP: {uunet,harvard}!uiucdcs!gillies