www.delorie.com/gnu/docs/avl/libavl_137.html   search  
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

8.8 Traversal

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:

/* 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 @refalso{247

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:

&#60;@xref{\NODE\, , TBST traverser null initializer.&#62;,269}
&#60;@xref{\NODE\, , TBST traverser first initializer.&#62;,270}
&#60;@xref{\NODE\, , TBST traverser last initializer.&#62;,271}
&#60;@xref{\NODE\, , TBST traverser search initializer.&#62;,272}
&#60;@xref{\NODE\, , TBST traverser insertion initializer.&#62;,273}
&#60;@xref{\NODE\, , TBST traverser copy initializer.&#62;,274}
&#60;@xref{\NODE\, , TBST traverser advance function.&#62;,275}
&#60;@xref{\NODE\, , TBST traverser back up function.&#62;,276}
&#60;@xref{\NODE\, , BST traverser current item function; bst =>.&#62; tbst,74}
&#60;@xref{\NODE\, , BST traverser replacement function; bst =>.&#62; tbst,75}
This code is included in @refalso{251

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

8.8.1 Starting at the Null Node  
8.8.2 Starting at the First Node  
8.8.3 Starting at the Last Node  
8.8.4 Starting at a Found Node  
8.8.5 Starting at an Inserted Node  
8.8.6 Initialization by Copying  
8.8.7 Advancing to the Next Node  
8.8.8 Backing Up to the Previous Node  

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003