13 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.¹ 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:

486. <pbst.h 486> =
<License 1>
#ifndef PBST_H
#define PBST_H 1

#include <stddef.h>

<Table types; tbl => pbst 14>
<TBST table structure; tbst => pbst 250>
<PBST node structure 488>
<TBST traverser structure; tbst => pbst 267>
<Table function prototypes; tbl => pbst 15>
<BST extra function prototypes; bst => pbst 88>

#endif /* pbst.h */

487. <pbst.c 487> =
<License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "pbst.h"

<PBST functions 489>

• PBST Data Types
• PBST Operations
• Inserting into a PBST
• Deleting from a PBST
• Traversing a PBST
• Copying a PBST
• Balancing a PBST
• Testing PBSTs