8.5.6 Finding the Parent of a 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 (p == NULL || p->tbst_link[0] != node)               {
while (x->tbst_tag[0] == TBST_CHILD)
}
return p;
}
else if (x->tbst_tag[0] == TBST_THREAD)           {
if (p == NULL || p->tbst_link[1] != node)               {
while (y->tbst_tag[1] == TBST_CHILD)
}
return p;
}
}
else     return (struct tbst_node *) &tree->tbst_root;
}
```

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