Re: Splay trees

[Josh MacDonald <jmacd CS Berkeley EDU>]

Generally speaking, I like the sound of this propsal.

-josh

Quoting Soeren Sandmann (sandmann@daimi.au.dk):
> Jeff Garzik writes:
> 
> > 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.
> 
> One of the advantages to splay trees is that their nodes does not
> contain any balancing information. I think that if the implementations
> are merged, this should still be the case
> 
> There could be some advantages to merging the implementations. We
> could have generic routines for rotating for instance. But the
> rotating functions in the balanced trees does quite a bit more than
> the rotating code in the splay trees.
> 
> 
> To merge the implementations of all kinds of binary trees, we should
> perhaps have generic binary trees. These should not support anything
> but rotations. Perhaps it should be
> 
> struct _GBinaryTreeNode
> {
>   GBinaryTreeNode *left;
>   GBinaryTreeNode *right;
> };
> 
> The AVL trees could then define their nodes as
> 
> struct _GTtreeNode 
> {
>   GBinaryTreeNode;
>   gpointer key;
>   gpointer data;
>   int balance;
> };
> 
> and the splay trees just
> 
> struct _GSplayTreeNode
> {
>   GBinaryTreeNode;
>   gpointer key;
>   gpointer data;
> };
> 
> To rotate, an implementation could do 
> 
> g_binary_tree_rotate_left ((GBinaryTreeNode)(node));
> 
> Would that be the way to go? Or should the key and data be in
> _GBinaryTreeNode in stead?
> 
> I you think something like the above would be what we want, I am
> willing to implement it.
> 
> Søren Sandmann
> 
> 
> -- 
>          To unsubscribe: mail gtk-devel-list-request@redhat.com with 
>                        "unsubscribe" as the Subject.

-- 
-josh