www.delorie.com/gnu/docs/avl/libavl_131.html

search

	Buy GNU books!

GNU libavl 2.0.1

8.2 Data Types

We need two extra fields in the node structure to keep track of whether each link is a child pointer or a thread. Each of these fields is called a tag (see tag). The revised struct tbst_node, along with enum tbst_tag for tags, looks like this:

/* Characterizes a link as a child pointer or a thread. */ enum tbst_tag { TBST_CHILD, /* Child pointer. */ TBST_THREAD /* Thread. */ }; /* A threaded binary search tree node. */ struct tbst_node { struct tbst_node *tbst_link[2]; /* Subtrees. */ void *tbst_data; /* Pointer to data. */ unsigned char tbst_tag[2]; /* Tag fields. */ };

This code is included in @refalso{247

Each element of tbst_tag[] is set to TBST_CHILD if the corresponding tbst_link[] element is a child pointer, or to TBST_THREAD if it is a thread. The other members of struct tbst_node should be familiar.

We also want a revised table structure, because traversers in threaded trees do not need a generation number:

/* Tree data structure. */ struct tbst_table { struct tbst_node *tbst_root; /* Tree's root. */ tbst_comparison_func *tbst_compare; /* Comparison function. */ void *tbst_param; /* Extra argument to tbst_compare. */ struct libavl_allocator *tbst_alloc; /* Memory allocator. */ size_t tbst_count; /* Number of items in tree. */ };

This code is included in @refalso{247

There is no need to define a maximum height for TBST trees because none of the TBST functions use a stack.

Exercises:

1. We defined enum tbst_tag for distinguishing threads from child pointers, but declared the actual tag members as unsigned char instead. Why? [answer]