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

GNU libavl 2.0.1

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

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).


*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]

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