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.