Re: Splay trees

[Jeff Garzik <jgarzik pobox com>]

On Sun, 21 Mar 1999, Josh MacDonald wrote:
> Quoting Jeff Garzik (jgarzik@pobox.com):
> > 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.
> 
> Its been a while since I studied these data structures, but I don't
> remember any real differences between red/black trees and AVL trees.
> Why do you want to add red/black trees?

The rbtree implementation I have benchmarks faster than Glib trees, so
I was lazy and hadn't looked at Glib trees in depth.  :)  (I would, of
course, before submitting a patch.)  Taking a closer look at Glib's
trees, the data structures are indeed pretty much the same.

libavl looks pretty nice.  It looks like a definite speed improvement
to Glib's trees if the libavl implementation is used.  The threaded
vs. unthreaded is nice, and the libavl function to convert
unthreaded->threaded could be used in the _freeze/_thaw functions.

	Jeff