Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
For PBSTs we reuse TBST table and traverser structures. In fact, the only data type that needs revision is the node structure. We take the basic form of a node and add a member pbst_parent to point to its parent node:
There is one special case: what should be the value of pbst_parent for a node that has no parent, that is, in the tree's root? There are two reasonable choices.
First, pbst_parent could be NULL in the root. This makes it easy to check whether a node is the tree's root. On the other hand, we often follow a parent pointer in order to change the link down from the parent, and NULL as the root node's pbst_parent requires a special case.
We can eliminate this special case if the root's pbst_parent is the tree's pseudo-root node, that is, (struct pbst_node *) &tree->pbst_root. The downside of this choice is that it becomes uglier, and perhaps slower, to check whether a node is the tree's root, because a comparison must be made against a non-constant expression instead of simply NULL.
In this book, we make the former choice, so pbst_parent is NULL in the tree's root node.
See also: [ Cormen 1990], section 11.4.
|webmaster donations bookstore||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|