www.delorie.com/gnu/docs/avl/libavl_137.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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 |
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:
<@xref{\NODE\, , TBST traverser null initializer.>,269} <@xref{\NODE\, , TBST traverser first initializer.>,270} <@xref{\NODE\, , TBST traverser last initializer.>,271} <@xref{\NODE\, , TBST traverser search initializer.>,272} <@xref{\NODE\, , TBST traverser insertion initializer.>,273} <@xref{\NODE\, , TBST traverser copy initializer.>,274} <@xref{\NODE\, , TBST traverser advance function.>,275} <@xref{\NODE\, , TBST traverser back up function.>,276} <@xref{\NODE\, , BST traverser current item function; bst =>.> tbst,74} <@xref{\NODE\, , BST traverser replacement function; bst =>.> tbst,75} |
See also: [ Knuth 1997], algorithm 2.3.1S.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster donations bookstore | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |