13.1 Data Types [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

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:

490. <PBST node structure 490> =
/* A binary search tree with parent pointers node. */
struct pbst_node 
  { struct pbst_node *pbst_link[2]; /* Subtrees. */ struct pbst_node *pbst_parent; /* Parent. */ void *pbst_data; /* Pointer to data. */ };

This code is included in 488.

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.