11.1 Data Types

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.