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

GNU libavl 2.0.1

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

14. BSTs with Parent Pointers

The preceding six chapters introduced two different forms of threaded trees, which simplified traversal by eliminating the need for a stack. There is another way to accomplish the same purpose: add to each node a parent pointer (see parent pointer), a link from the node to its parent. A binary search tree so augmented is called a BST with parent pointers, or PBST for short.(15) In this chapter, we show how to add parent pointers to binary trees. The next two chapters will add them to AVL trees and red-black trees.

Parent pointers and threads have equivalent power. That is, given a node within a threaded tree, we can find the node's parent, and given a node within a tree with parent pointers, we can determine the targets of any threads that the node would have in a similar threaded tree.

Parent pointers have some advantages over threads. In particular, parent pointers let us more efficiently eliminate the stack for insertion and deletion in balanced trees. Rebalancing during these operations requires us to locate the parents of nodes. In our implementations of threaded balanced trees, we wrote code to do this, but it took a relatively complicated and slow helper function. Parent pointers make it much faster and easier. It is also easier to search a tree with parent pointers than a threaded tree, because there is no need to check tags. Outside of purely technical issues, many people find the use of parent pointers more intuitive than threads.

On the other hand, to traverse a tree with parent pointers in inorder we may have to follow several parent pointers instead of a single thread. What's more, parent pointers take extra space for a third pointer field in every node, whereas the tag fields in threaded balanced trees often fit into node structures without taking up additional room (see Exercise 8.1-1). Finally, maintaining parent pointers on insertion and deletion takes time. In fact, we'll see that it takes more operations (and thus, all else being equal, time) than maintaining threads.

In conclusion, a general comparison of parent pointers with threads reveals no clear winner. Further discussion of the merits of parent pointers versus those of threads will be postponed until later in this book. For now, we'll stick to the problems of parent pointer implementation.

Here's the outline of the PBST code. We're using the prefix pbst_ this time:

&#60;@xref{\NODE\, , License.&#62;,1}
#ifndef PBST_H
#define @cindex PBST_H macro
#include &#60;stddef.h&#62;
&#60;@xref{\NODE\, , Table types; tbl =>.&#62; pbst,14}
&#60;@xref{\NODE\, , TBST table structure; tbst =>.&#62; pbst,250}
&#60;@xref{\NODE\, , PBST node structure.&#62;,488}
&#60;@xref{\NODE\, , TBST traverser structure; tbst =>.&#62; pbst,267}
&#60;@xref{\NODE\, , Table function prototypes; tbl =>.&#62; pbst,15}
&#60;@xref{\NODE\, , BST extra function prototypes; bst =>.&#62; pbst,88}
#endif /* pbst.h */

&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include "pbst.h"
&#60;@xref{\NODE\, , PBST functions.&#62;,489}

14.1 Data Types  
14.2 Operations  
14.3 Insertion  
14.4 Deletion  
14.5 Traversal  
14.6 Copying  
14.7 Balance  
14.8 Testing  

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

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003