Re: Splay trees

[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