13.1 Data Types

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.