Re: Splay trees

[Jeff Garzik <jgarzik pobox com>]

On Mon, 22 Mar 1999, Simon K}gedal wrote:
> On Sat, Mar 20, 1999 at 09:52:03PM -0500, Jeff Garzik wrote:
> > On Sat, 20 Mar 1999, Josh MacDonald wrote:
> > > Would it be possible to merge the implementation of Splay trees with
> > > the other balanced tree implementation in glib, since they share so
> > > much?  I think this should not be accepted until then.
> > 
> > That would be nice, as I would like to add red-black trees to Glib.
> 
> Wouldn't it be more important to optimize the current AVL
> implementation a bit?  I haven't compared times, but I think you can
> save a lot by doing things iteratively instead of recursively.  OTOH,
> people who really want effecient balanced trees can use libavl (
> http://www.msu.edu/user/pfaffben/avl/ ) instead.

My main motivation for adding red-black trees to Glib was that my
benchmarks of standard ops: in-order insert, random insert, lookup,
etc. seemed to be faster than Glib's implementation of AVL trees.
(this is without looking at the AVL code to see if it is slow or weird)

Can AVL trees be replaced by splay trees?  I like the adaptive qualities
of the splay trees.

	Jeff