13.2 Operations

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:

491. <PBST functions 491> =
<TBST creation function; tbst => pbst 254>
<BST search function; bst => pbst 32>
<PBST item insertion function 492>
<Table insertion convenience functions; tbl => pbst 594>
<PBST item deletion function 495>
<PBST traversal functions 504>
<PBST copy function 511>
<BST destruction function; bst => pbst 85>
<PBST balance function 513>
<Default memory allocation functions; tbl => pbst 7>
<Table assertion functions; tbl => pbst 596>

This code is included in 489.