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

GNU libavl 2.0.1

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

14.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:

/* 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 @refalso{486

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-&#62;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