Finding the Parent of a TBST Node

The last component of tavl_delete() left undiscussed is the implementation of its helper function find_parent(), which requires an algorithm for finding the parent of an arbitrary node in a TAVL tree. If there were no efficient algorithm for this purpose, we would have to keep a stack of parent nodes as we did for unthreaded AVL trees. (This is still an option, as shown in Exercise 3.) We are fortunate that such an algorithm does exist. Let's discover it.

Because child pointers always lead downward in a BST, the only way that we're going to get from one node to another one above it is by following a thread. Almost directly from our definition of threads, we know that if a node q has a right child p, then there is a left thread in the subtree rooted at p that points back to q. Because a left thread points from a node to its predecessor, this left thread to q must come from q's successor, which we'll call s. The situation looks like this:

This leads immediately to an algorithm to find q given p, if p is q's right child. We simply follow left links starting at p until we we reach a thread, then we follow that thread. On the other hand, it doesn't help if p is q's left child, but there's an analogous situation with q's predecessor in that case.

Will this algorithm work for any node in a TBST? It won't work for the root node, because no thread points above the root (see Exercise 2). It will work for any other node, because any node other than the root has its successor or predecessor as its parent.

Here is the actual code, which finds and returns the parent of node. It traverses both the left and right subtrees of node at once, using x to move down to the left and y to move down to the right. When it hits a thread on one side, it checks whether it leads to node's parent. If it does, then we're done. If it doesn't, then we continue traversing along the other side, which is guaranteed to lead to node's parent.

327. <Find parent of a TBST node 327> =
/* Returns the parent of node within tree,
   or a pointer to tbst_root if s is the root of the tree. */
static struct tbst_node *
find_parent (struct tbst_table *tree, struct tbst_node *node) 
{
  if (node != tree->tbst_root) 
    {
      struct tbst_node *x, *y;

      for (x = y = node; ; x = x->tbst_link[0], y = y->tbst_link[1])
        if (y->tbst_tag[1] == TBST_THREAD) 
          {
            struct tbst_node *p = y->tbst_link[1];
            if (p == NULL || p->tbst_link[0] != node) 
              {
                while (x->tbst_tag[0] == TBST_CHILD)
                  x = x->tbst_link[0];
                p = x->tbst_link[0];
              }
            return p;
          }
        else if (x->tbst_tag[0] == TBST_THREAD) 
          {
            struct tbst_node *p = x->tbst_link[0];
            if (p == NULL || p->tbst_link[1] != node) 
              {
                while (y->tbst_tag[1] == TBST_CHILD)
                  y = y->tbst_link[1];
                p = y->tbst_link[1];
              }
            return p;
          }
    }
  else 
    return (struct tbst_node *) &tree->tbst_root;
}

This code is included in 311, 668, and 670.

See also: [Knuth 1997], exercise 2.3.1-19.

Exercises:

*1. Show that finding the parent of a given node using this algorithm, averaged over all the node within a TBST, requires only a constant number of links to be followed. [answer]

2. The structure of threads in our TBSTs force finding the parent of the root node to be special-cased. Suggest a modification to the tree structure to avoid this. [answer]

3. It can take several steps to find the parent of an arbitrary node in a TBST, even though the operation is “efficient” in the sense of Exercise 7.7-4. On the other hand, finding the parent of a node is very fast with a stack, but it costs time to construct the stack. Rewrite tavl_delete() to use a stack instead of the parent node algorithm. [answer]