Traversing a TBST - GNU libavl 2.0.2

Traversal in a threaded BST is much simpler than in an unthreaded one. This is, indeed, much of the point to threading our trees. This section implements all of the libavl traverser functions for threaded trees.

Suppose we wish to find the successor of an arbitrary node in a threaded tree. If the node has a right child, then the successor is the smallest item in the node's right subtree. Otherwise, the node has a right thread, and its sucessor is simply the node to which the right thread points. If the right thread is a null pointer, then the node is the largest in the tree. We can find the node's predecessor in a similar manner.

We don't ever need to know the parent of a node to traverse the threaded tree, so there's no need to keep a stack. Moreover, because a traverser has no stack to be corrupted by changes to its tree, there is no need to keep or compare generation numbers. Therefore, this is all we need for a TBST traverser structure:

267. <TBST traverser structure 267> =
/* TBST traverser structure. */
struct tbst_traverser 
  {
    struct tbst_table *tbst_table;        /* Tree being traversed. */
    struct tbst_node *tbst_node;          /* Current node in tree. */
  };

This code is included in 247, 297, 333, 372, 415, 452, 486, 519, and 551.

The traversal functions are collected together here. A few of the functions are implemented directly in terms of their unthreaded BST counterparts, but most must be reimplemented:

268. <TBST traversal functions 268> =
<TBST traverser null initializer 269>
<TBST traverser first initializer 270>
<TBST traverser last initializer 271>
<TBST traverser search initializer 272>
<TBST traverser insertion initializer 273>
<TBST traverser copy initializer 274>
<TBST traverser advance function 275>
<TBST traverser back up function 276>
<BST traverser current item function; bst => tbst 74>
<BST traverser replacement function; bst => tbst 75>

This code is included in 251, 300, and 336.

See also: [Knuth 1997], algorithm 2.3.1S.