7.8 Traversal [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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: 

269. <TBST traverser structure 269> =
/* 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 249, 299, 335, 374, 417, 454, 488, 521, and 553.

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: 

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

This code is included in 253, 302, and 338.

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