10.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:

397. <RTBST traversal functions 397> =
<TBST traverser null initializer; tbst => rtbst 271>
<RTBST traverser first initializer 398>
<RTBST traverser last initializer 399>
<RTBST traverser search initializer 400>
<TBST traverser insertion initializer; tbst => rtbst 275>
<TBST traverser copy initializer; tbst => rtbst 276>
<RTBST traverser advance function 401>
<RTBST traverser back up function 402>
<BST traverser current item function; bst => rtbst 75>
<BST traverser replacement function; bst => rtbst 76>

This code is included in 377, 420, and 457.

• RTBST Traverser First Initialization
• RTBST Traverser Last Initialization
• RTBST Traverser Find Initialization
• RTBST Traverser Advancing
• RTBST Traverser Retreating