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

GNU libavl 2.0.1

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

11.6 Traversal

Traversal in an RTBST is unusual due to its asymmetry. Moving from smaller nodes to larger nodes is easy: we do it with the same algorithm used in a TBST. Moving the other way is more difficult and inefficient besides: we have neither a stack of parent nodes to fall back on nor left threads to short-circuit.

RTBSTs use the same traversal structure as TBSTs, so we can reuse some of the functions from TBST traversers. We also get a few directly from the implementations for BSTs. Other than that, everything has to be written anew here:

&#60;@xref{\NODE\, , TBST traverser null initializer; tbst =>.&#62; rtbst,269}
&#60;@xref{\NODE\, , RTBST traverser first initializer.&#62;,396}
&#60;@xref{\NODE\, , RTBST traverser last initializer.&#62;,397}
&#60;@xref{\NODE\, , RTBST traverser search initializer.&#62;,398}
&#60;@xref{\NODE\, , TBST traverser insertion initializer; tbst =>.&#62; rtbst,273}
&#60;@xref{\NODE\, , TBST traverser copy initializer; tbst =>.&#62; rtbst,274}
&#60;@xref{\NODE\, , RTBST traverser advance function.&#62;,399}
&#60;@xref{\NODE\, , RTBST traverser back up function.&#62;,400}
&#60;@xref{\NODE\, , BST traverser current item function; bst =>.&#62; rtbst,74}
&#60;@xref{\NODE\, , BST traverser replacement function; bst =>.&#62; rtbst,75}
This code is included in @refalso{375

11.6.1 Starting at the First Node  
11.6.2 Starting at the Last Node  
11.6.3 Starting at a Found Node  
11.6.4 Advancing to the Next Node  
11.6.5 Backing Up to the Previous Node  

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