Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!p.cs.uiuc.edu!gillies
From: gillies@p.cs.uiuc.edu
Newsgroups: comp.lang.c
Subject: Re: a tree question
Message-ID: <77200038@p.cs.uiuc.edu>
Date: 25 Aug 89 17:00:00 GMT
References: <1074@taurus.BITNET>
Lines: 21
Nf-ID: #R:taurus.BITNET:1074:p.cs.uiuc.edu:77200038:000:935
Nf-From: p.cs.uiuc.edu!gillies    Aug 25 12:00:00 1989


> Written  1:58 am  Aug 25, 1989 by mccaugh@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@cs.uiuc.edu   UUCP: {uunet,harvard}!uiucdcs!gillies