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

search

	Buy GNU books!

GNU libavl 2.0.1

5.2.2 Tree Structure

The struct bst_table structure ties together all of the data needed to keep track of a table implemented as a binary search tree:

/* Tree data structure. */ struct bst_table { struct bst_node *bst_root; /* Tree's root. */ bst_comparison_func *bst_compare; /* Comparison function. */ void *bst_param; /* Extra argument to bst_compare. */ struct libavl_allocator *bst_alloc; /* Memory allocator. */ size_t bst_count; /* Number of items in tree. */ unsigned long bst_generation; /* Generation number. */ };

This code is included in @refalso{24

Most of struct bst_table's members should be familiar. Member bst_root points to the root node of the BST. Together, bst_compare and bst_param specify how items are compared (see section 3.4 Item and Copy Functions). The members of bst_alloc specify how to allocate memory for the BST (see section 3.5 Memory Allocation). The number of items in the BST is stored in bst_count (see section 3.7 Count).

The final member, bst_generation, is a generation number. When a tree is created, it starts out at zero. After that, it is incremented every time the tree is modified in a way that might disturb a traverser. We'll talk more about the generation number later (see section 5.9.3 Better Iterative Traversal).

Exercises:

*1. Why is it a good idea to include bst_count in struct bst_table? Under what circumstances would it be better to omit it? [answer]