13.2 Operations [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

When we added parent pointers to BST nodes, we did not change the interpretation of any of the node members. This means that any function that examines PBSTs without modifying them will work without change. We take advantage of that for tree search. We also get away with it for destruction, since there's no problem with failing to update parent pointers in that case. Although we could, technically, do the same for traversal, that would negate much of the advantage of parent pointers, so we reimplement them. Here is the overall outline: 

489. <PBST functions 489> =
<TBST creation function; tbst => pbst 252>
<BST search function; bst => pbst 31>
<PBST item insertion function 490>
<Table insertion convenience functions; tbl => pbst 592>
<PBST item deletion function 493>
<PBST traversal functions 502>
<PBST copy function 509>
<BST destruction function; bst => pbst 84>
<PBST balance function 511>
<Default memory allocation functions; tbl => pbst 6>
<Table assertion functions; tbl => pbst 594>

This code is included in 487.