Re: Splay trees

[Soeren Sandmann <sandmann daimi au dk>]

Jeff Garzik writes:

>> 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)

GLib's implementation of AVL trees could be improved. As Simon says,
you can save a lot by doing thing iteratively instead of recursively.
the code.

Knuth, vol. 1 and 3 describes them. These are the versions used in
libavl.

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

I tested my implementation of the splay trees against GLib's AVL
trees. With random insertions, splay trees are about 25% slower. This
is to be expected since one then gain nothing from the adaptiveness of
splay trees.

For most practical applications, splay trees are at least as good as
AVL and red-black trees. I have no numbers to back this up, though.