www.delorie.com/gnu/docs/avl/libavl_38.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
For efficiency, some of the BST routines use a stack of a fixed maximum height. This maximum height affects the maximum number of nodes that can be fully supported by libavl in any given tree, because a binary tree of height n contains at most 2**n - 1 nodes.
The BST_MAX_HEIGHT macro sets the maximum height of a BST. The default value of 32 allows for trees with up to \ASCII\ - 1, 2**32 - 1} = 4,294,967,295 nodes. On today's common 32-bit computers that support only 4 GB of memory at most, this is hardly a limit, because memory would be exhausted long before the tree became too big.
The BST routines that use fixed stacks also detect stack overflow and call a routine to "balance" or restructure the tree in order to reduce its height to the permissible range. The limit on the BST height is therefore not a severe restriction.
/* Maximum BST height. */ #ifndef BST_MAX_HEIGHT #define @cindex BST_MAX_HEIGHT macro BST_MAX_HEIGHT 32 #endif |
Exercises:
1. Suggest a reason why the BST_MAX_HEIGHT macro is defined conditionally. Are there any potential pitfalls? [answer]
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |