Re: Splay trees

[Jeff Garzik <jgarzik pobox com>]

On 21 Mar 1999, Soeren Sandmann wrote:
> 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;
> };

You probably want to keep the field order the same, for binary
compatibility.  Presuming that weird structure packing crap doesn't
occur, it might be better to use

	struct _GTreeNode
	{
	  gint balance;      /* height (left) - height (right) */
	  GBinaryTreeNode bt_node;
	  gpointer key;      /* key for this node */
	  gpointer value;    /* value stored at this node */
	};