11.1 Data Types [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

Besides the members needed for any BST, an RTAVL node structure needs a tag to indicate whether the right link is a child pointer or a thread, and a balance factor to facilitate AVL balancing. Here's what we end up with:

419. <RTAVL node structure 419> =
/* Characterizes a link as a child pointer or a thread. */
enum rtavl_tag 
  { RTAVL_CHILD, /* Child pointer. */ RTAVL_THREAD /* Thread. */ }; /* A threaded binary search tree node. */ struct rtavl_node
  { struct rtavl_node *rtavl_link[2]; /* Subtrees. */ void *rtavl_data; /* Pointer to data. */ unsigned char rtavl_rtag; /* Tag field. */ signed char rtavl_balance; /* Balance factor. */ };

This code is included in 417.