7.1 Threads

In an ordinary binary search tree or balanced tree, a lot of the pointer fields go more-or-less unused. Instead of pointing to somewhere useful, they are used to store null pointers. In a sense, they're wasted. What if we were to instead use these fields to point elsewhere in the tree?

This is the idea behind a threaded tree. In a threaded tree, a node's left child pointer field, if it would otherwise be a null pointer, is used to point to the node's inorder predecessor. An otherwise-null right child pointer field points to the node's successor. The least-valued node in a threaded tree has a null pointer for its left thread, and the greatest-valued node similarly has a null right thread. These two are the only null pointers in a threaded tree.

Here's a sample threaded tree:

This diagram illustrates the convention used for threads in this book, arrowheads attached to dotted lines. Null threads in the least and greatest nodes are shown as arrows pointing into space. This kind of arrow is also used to show threads that point to nodes not shown in the diagram.

There are some disadvantages to threaded trees. Each node in an unthreaded tree has only one pointer that leads to it, either from the tree structure or its parent node, but in a threaded tree some nodes have as many as three pointers leading to them: one from the root or parent, one from its predecessor's right thread, and one from its successor's left thread. This means that, although traversing a threaded tree is simpler, building and maintaining a threaded tree is more complicated.

As we learned earlier, any node that has a right child has a successor in its right subtree, and that successor has no left child. So, a node in an threaded tree has a left thread pointing back to it if and only if the node has a right child. Similarly, a node has a right thread pointing to it if and only if the node has a left child. Take a look at the sample tree above and check these statements for yourself for some of its nodes.

See also:  [Knuth 1997], section 2.3.1.