 Index Entry  Section 

D   
 default memory allocation functions  3.5 Memory Allocation 
 default memory allocator header  3.5 Memory Allocation 
 delete BST node  Implementation 
 delete BST node by merging  5.8.1 Aside: Deletion by Merging 
 delete item from AVL tree  6.5.2 Step 2: Delete 
 delete item from AVL tree  6.5.2 Step 2: Delete 
 delete item from PAVL tree  15.5.1 Step 2: Delete 
 delete item from PRB tree  16.4.1 Step 2: Delete 
 delete item from RB tree  7.5.1 Step 2: Delete 
 delete item from RB tree, alternate version  Section 6.5.1 
 delete item from RB tree, alternate version  Section 6.5.1 
 delete item from RB tree, alternate version  Section 6.5.1 
 delete item from TAVL tree  9.5.2 Step 2: Delete 
 delete item from TAVL tree, with stack  Section 8.5.6 
 delete item from TRB tree  10.4.2 Step 2: Delete 
 delete PBST node  14.4 Deletion 
 delete RTAVL node  12.5.2 Step 2: Delete 
 delete RTAVL node, rightlooking  Section 11.5.4 
 delete RTBST node, leftlooking  11.5.2 LeftLooking Deletion 
 delete RTBST node, rightlooking  11.5.1 RightLooking Deletion 
 delete RTRB node  13.4.1 Step 2: Delete 
 delete TBST node  8.7 Deletion 
 delete_order enumeration  5.14.2 Test Set Generation 
 destroy a BST iteratively  5.11.3 Aside: Iterative Destruction 
 destroy a BST recursively  5.11.2 Aside: Recursive Destruction 

E   
 ensure w is black in leftside PRB deletion rebalancing  Case Reduction: Ensure w is black 
 ensure w is black in leftside RB deletion rebalancing  Case Reduction: Ensure w is black 
 ensure w is black in leftside TRB deletion rebalancing  Case Reduction: Ensure w is black 
 ensure w is black in rightside PRB deletion rebalancing  16.4.4 Symmetric Case 
 ensure w is black in rightside RB deletion rebalancing  7.5.4 Symmetric Case 
 ensure w is black in rightside TRB deletion rebalancing  10.4.5 Symmetric Case 
 error_node variable  Section 4.10.1 

F   
 fail function  5.14.6 Utility Functions 
 fallback_join function  Section 4.13 
 find BST node to delete  Implementation 
 find BST node to delete by merging  5.8.1 Aside: Deletion by Merging 
 find parent of a TBST node  9.5.6 Finding the Parent of a Node 
 find PBST node to delete  14.4 Deletion 
 find PBST node to delete  14.4 Deletion 
 find predecessor of RTBST node with left child  11.6.5 Backing Up to the Previous Node 
 find predecessor of RTBST node with no left child  11.6.5 Backing Up to the Previous Node 
 find RTBST node to delete  11.5 Deletion 
 find TBST node to delete  8.7 Deletion 
 find TBST node to delete, with parent node algorithm  Section 7.7 
 find_parent function  9.5.6 Finding the Parent of a Node 
 finish up after BST deletion by merging  5.8.1 Aside: Deletion by Merging 
 finish up after deleting BST node  Implementation 
 finish up after deleting PBST node  Case 3: p's right child has a left child 
 finish up after deleting RTBST node  11.5 Deletion 
 finish up after deleting TBST node  Case 4: p's right child has a left child 
 finish up after PRB deletion  16.4.3 Step 4: Finish Up 
 finish up after RB deletion  7.5.3 Step 4: Finish Up 
 finish up after RTRB deletion  13.4.3 Step 4: Finish Up 
 finish up after TRB deletion  10.4.4 Step 4: Finish Up 
 finish up and return after AVL deletion  6.5.5 Step 5: Finish Up 
 first_item function  5.9.2.1 Improving Convenience 
 found insertion point in recursive AVL insertion  6.4.7 Aside: Recursive Insertion 

G   
 gen_balanced_tree function  Section 4.14.2 
 gen_deletions function  Section 4.14.2 
 gen_insertions function  Section 4.14.2 
 generate permutation for balanced tree  Section 4.14.2 
 generate random permutation of integers  Section 4.14.2 

H   
 handle case where x has a right child  5.9.3.7 Advancing to the Next Node 
 handle case where x has no right child  5.9.3.7 Advancing to the Next Node 
 handle stack overflow during BST traversal  Section 4.9.2.1 
 handle_long_option function  B.1 Option Parser 
 handle_short_option function  B.1 Option Parser 

I   
 initialize search test array  Section 3.5 
 initialize smaller and larger within binary search tree  Section 3.6 
 insert AVL node  6.4.2 Step 2: Insert 
 insert n into arbitrary subtree  Section 4.7.1 
 insert new BST node, root insertion version  5.7.1 Aside: Root Insertion 
 insert new node into RTBST tree  11.4 Insertion 
 insert PAVL node  15.4.1 Steps 1 and 2: Search and Insert 
 insert PBST node  14.3 Insertion 
 insert PRB node  16.3.1 Step 2: Insert 
 insert RB node  7.4.2 Step 2: Insert 
 insert RTAVL node  12.4.1 Steps 12: Search and Insert 
 insert RTRB node  13.3.1 Steps 1 and 2: Search and Insert 
 insert TAVL node  9.4.1 Steps 1 and 2: Search and Insert 
 insert TBST node  8.6 Insertion 
 insert TRB node  10.3.1 Steps 1 and 2: Search and Insert 
 insert_order enumeration  5.14.2 Test Set Generation 
 insertion and deletion order generation  Section 4.14.2 
 intermediate step between bst_copy_recursive_2() and bst_copy_iterative()  Section 4.10.2 
 iter variable  Section 4.9.2.1 
 iter variable  Section 4.9.2.1 
 iterative copy of BST  5.10.2 Iterative Copying 
 iterative copy of BST  5.10.2 Iterative Copying 
 iterative copy of BST  5.10.2 Iterative Copying 
 iterative copy of BST  5.10.2 Iterative Copying 
 iterative traversal of BST, take 1  5.9.2 Traversal by Iteration 
 iterative traversal of BST, take 2  5.9.2 Traversal by Iteration 
 iterative traversal of BST, take 3  5.9.2 Traversal by Iteration 
 iterative traversal of BST, take 4  5.9.2 Traversal by Iteration 
 iterative traversal of BST, take 5  5.9.2 Traversal by Iteration 
 iterative traversal of BST, take 6  5.9.2.1 Improving Convenience 
 iterative traversal of BST, take 6  5.9.2.1 Improving Convenience 
 iterative traversal of BST, take 6  5.9.2.1 Improving Convenience 
 iterative traversal of BST, with dynamically allocated stack  Section 4.9.2 

L   
 leftside rebalancing after initialblack RB insertion  7.4.5 Aside: Initial Black Insertion 
 leftside rebalancing after PRB deletion  16.4.2 Step 3: Rebalance 
 leftside rebalancing after PRB insertion  16.3.2 Step 3: Rebalance 
 leftside rebalancing after RB deletion  7.5.2 Step 3: Rebalance 
 leftside rebalancing after RB insertion  7.4.3 Step 3: Rebalance 
 leftside rebalancing after RTRB deletion  13.4.2 Step 3: Rebalance 
 leftside rebalancing after RTRB insertion  13.3.2 Step 3: Rebalance 
 leftside rebalancing after TRB deletion  10.4.3 Step 3: Rebalance 
 leftside rebalancing after TRB insertion  10.3.2 Step 3: Rebalance 
 leftside rebalancing case 1 in AVL deletion  Case 1: x has  balance factor 
 leftside rebalancing case 1 in PAVL deletion  Case 1: x has  balance factor 
 leftside rebalancing case 2 in AVL deletion  Case 2: x has + or 0 balance factor 
 leftside rebalancing case 2 in PAVL deletion  Case 2: x has + or 0 balance factor 
 levelorder traversal  Section 4.7 
 libavl_allocator structure  3.5 Memory Allocation 
 license  2.4 License 
