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: <77200043@p.cs.uiuc.edu>
Date: 27 Aug 89 21:21:00 GMT
References: <1074@taurus.BITNET>
Lines: 35
Nf-ID: #R:taurus.BITNET:1074:p.cs.uiuc.edu:77200043:000:1684
Nf-From: p.cs.uiuc.edu!gillies    Aug 27 16:21:00 1989


Re: Hascall from Cornell criticizes the high overhead in Splay Trees
    blames problem on theoretical computer scientists.

First off the time per comparison is constant, whether you do one, or
a billion.  It only takes O(n) comparisons for Splay to achieve O(n
log n) performance.  The high overhead comes about because *every*
search involves doing rotation on the tree.  In fact, the sought-after
object is rotated all the way to the root of the tree (Splay is a
"move to front" heuristic for trees).

The basenote writer wanted something more efficient in time & space
than AVL trees.  That is a Tall Order.  He called AVL "inefficient in
time & space", and didn't give any reasons.  I tend to find today's
automobiles inefficient in time & space, too.

Splay trees are so simple to implement, they also save *code space*.
I wrote a splay package to find ways to speed up splay(), and
successfully designed two new splays.

I agree that 20 microseconds/comparison is pretty slow, and it should
be more like 1-2 microseconds a comparison, but this package is not
absolutely as fast as possible.  In fact, you could
  (0) unroll the rotations (estimate: 65k comparisons/sec)
  (1) Implement top-down splay (estimate: 100k comparisons/sec)
  (2) Implement my splay, top-down (maybe 110k/sec)

Unlike an AVL tree, 100k comparisons becomes 100k lookups, if you're
looking up the same thing repeatedly.  So Splay can blow the doors off
AVL trees if there is much locality of reference, or insertion /
deletion.

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