www.delorie.com/gnu/docs/avl/libavl_131.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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]


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003