 Index Entry  Section 

C   
 calculate leaves  5.12.2.2 Implementation 
 case 1 in AVL deletion  Case 1: p has no right child 
 case 1 in BST deletion  Implementation 
 case 1 in leftlooking RTBST deletion  Case 1: p has a right child but no left child 
 case 1 in leftside initialblack RB insertion rebalancing  Case 1: q's uncle is red 
 case 1 in leftside PRB deletion rebalancing  Case 1: w has no red children 
 case 1 in leftside PRB insertion rebalancing  Case 1: q's uncle is red 
 case 1 in leftside RB deletion rebalancing  Case 1: w has no red children 
 case 1 in leftside RB insertion rebalancing  Case 1: q's uncle is red 
 case 1 in leftside RTRB insertion rebalancing  Case 1: q's uncle is red 
 case 1 in leftside TRB deletion rebalancing  Case 1: w has no red children 
 case 1 in leftside TRB insertion rebalancing  Case 1: q's uncle is red 
 case 1 in PAVL deletion  Case 1: p has no right child 
 case 1 in PBST deletion  Case 1: p has no right child 
 case 1 in PRB deletion  Case 1: p has no right child 
 case 1 in RB deletion  Case 1: p has no right child 
 case 1 in rightlooking RTBST deletion  Case 1: p has a right thread and a left child 
 case 1 in rightside initialblack RB insertion rebalancing  7.4.5.1 Symmetric Case 
 case 1 in rightside PRB deletion rebalancing  16.4.4 Symmetric Case 
 case 1 in rightside PRB insertion rebalancing  16.3.3 Symmetric Case 
 case 1 in rightside RB deletion rebalancing  7.5.4 Symmetric Case 
 case 1 in rightside RB insertion rebalancing  7.4.4 Symmetric Case 
 case 1 in rightside RTRB insertion rebalancing  Case 1: q's uncle is red 
 case 1 in rightside TRB deletion rebalancing  10.4.5 Symmetric Case 
 case 1 in rightside TRB insertion rebalancing  10.3.3 Symmetric Case 
 case 1 in RTAVL deletion  Case 1: p has a right child but no left child 
 case 1 in RTAVL deletion, rightlooking  Section 11.5.4 
 case 1 in RTRB deletion  Case 1: p has a right child but no left child 
 case 1 in TAVL deletion  Case 1: p has a right thread and a left child 
 case 1 in TAVL deletion, with stack  Section 8.5.6 
 case 1 in TBST deletion  Case 1: p has a right thread and a left child 
 case 1 in TRB deletion  Case 1: p has a right thread and a left child 
 case 1.5 in BST deletion  Section 4.8 
 case 2 in AVL deletion  Case 2: p's right child has no left child 
 case 2 in BST deletion  Implementation 
 case 2 in leftlooking RTBST deletion  Case 2: p has a right thread and no left child 
 case 2 in leftside initialblack RB insertion rebalancing  Case 2: q is the left child of pa[k  1] 
 case 2 in leftside PRB deletion rebalancing  Case 2: w's right child is red 
 case 2 in leftside PRB insertion rebalancing  Case 2: q is the left child of its parent 
 case 2 in leftside RB deletion rebalancing  Case 2: w's right child is red 
 case 2 in leftside RB insertion rebalancing  Case 2: q is the left child of pa[k  1] 
 case 2 in leftside RTRB deletion rebalancing  Case 2: w's child opposite the deletion is red 
 case 2 in leftside RTRB insertion rebalancing  Case 2: q is on same side of parent as parent is of grandparent 
 case 2 in leftside TRB deletion rebalancing  Case 2: w's right child is red 
 case 2 in leftside TRB insertion rebalancing  Case 2: q is the left child of its parent 
 case 2 in PAVL deletion  Case 2: p's right child has no left child 
 case 2 in PBST deletion  Case 2: p's right child has no left child 
 case 2 in PRB deletion  Case 2: p's right child has no left child 
 case 2 in RB deletion  Case 2: p's right child has no left child 
 case 2 in rightlooking RTBST deletion  Case 2: p has a right thread and no left child 
 case 2 in rightside initialblack RB insertion rebalancing  7.4.5.1 Symmetric Case 
 case 2 in rightside PRB deletion rebalancing  16.4.4 Symmetric Case 
 case 2 in rightside PRB insertion rebalancing  16.3.3 Symmetric Case 
 case 2 in rightside RB deletion rebalancing  7.5.4 Symmetric Case 
 case 2 in rightside RB insertion rebalancing  7.4.4 Symmetric Case 
 case 2 in rightside RTRB deletion rebalancing  Case 2: w's child opposite the deletion is red 
 case 2 in rightside RTRB insertion rebalancing  Case 2: q is on same side of parent as parent is of grandparent 
 case 2 in rightside TRB deletion rebalancing  10.4.5 Symmetric Case 
 case 2 in rightside TRB insertion rebalancing  10.3.3 Symmetric Case 
 case 2 in RTAVL deletion  Case 2: p has a right thread and no left child 
 case 2 in RTAVL deletion, rightlooking  Section 11.5.4 
 case 2 in RTRB deletion  Case 2: p has a right thread and no left child 
 case 2 in TAVL deletion  Case 2: p has a right thread and a left thread 
 case 2 in TAVL deletion, with stack  Section 8.5.6 
 case 2 in TBST deletion  Case 2: p has a right thread and a left thread 
 case 2 in TRB deletion  Case 2: p has a right thread and a left thread 
 case 3 in AVL deletion  Case 3: p's right child has a left child 
 case 3 in AVL deletion, alternate version  Section 5.5.2 
 case 3 in BST deletion  Implementation 
 case 3 in BST deletion  Implementation 
 case 3 in BST deletion, alternate version  Section 4.8 
 case 3 in leftlooking RTBST deletion  Case 3: p's left child has a right thread 
 case 3 in leftside initialblack RB insertion rebalancing  Case 3: q is the right child of pa[k  1] 
 case 3 in leftside PRB insertion rebalancing  Case 3: q is the right child of its parent 
 case 3 in leftside RB insertion rebalancing  Case 3: q is the right child of pa[k  1] 
 case 3 in leftside RTRB insertion rebalancing  Case 3: q is on opposite side of parent as parent is of grandparent 
 case 3 in leftside TRB insertion rebalancing  Case 3: q is the right child of its parent 
 case 3 in PAVL deletion  Case 3: p's right child has a left child 
 case 3 in PBST deletion  Case 3: p's right child has a left child 
 case 3 in PBST deletion  Case 3: p's right child has a left child 
 case 3 in PRB deletion  Case 3: p's right child has a left child 
 case 3 in RB deletion  Case 3: p's right child has a left child 
 case 3 in rightlooking RTBST deletion  Case 3: p's right child has no left child 
 case 3 in rightside initialblack RB insertion rebalancing  7.4.5.1 Symmetric Case 
 case 3 in rightside PRB insertion rebalancing  16.3.3 Symmetric Case 
 case 3 in rightside RB insertion rebalancing  7.4.4 Symmetric Case 
 case 3 in rightside RTRB insertion rebalancing  Case 3: q is on opposite side of parent as parent is of grandparent 
 case 3 in rightside TRB insertion rebalancing  10.3.3 Symmetric Case 
 case 3 in RTAVL deletion  Case 3: p's left child has a right thread 
 case 3 in RTAVL deletion, rightlooking  Section 11.5.4 
 case 3 in RTRB deletion  Case 3: p's left child has a right thread 
 case 3 in TAVL deletion  Case 3: p's right child has a left thread 
 case 3 in TAVL deletion, with stack  Section 8.5.6 
 case 3 in TBST deletion  Case 3: p's right child has a left thread 
 case 3 in TRB deletion  Case 3: p's right child has a left thread 
 case 4 in leftlooking RTBST deletion  Case 4: p's left child has a right child 
 case 4 in leftlooking RTBST deletion  Case 4: p's left child has a right child 
 case 4 in leftlooking RTBST deletion  Case 4: p's left child has a right child 
 case 4 in leftlooking RTBST deletion, alternate version  Section 10.5.2 
 case 4 in rightlooking RTBST deletion  Case 4: p's right child has a left child 
 case 4 in rightlooking RTBST deletion, alternate version  Section 10.5.1 
 case 4 in RTAVL deletion  Case 4: p's left child has a right child 
 case 4 in RTAVL deletion  Case 4: p's left child has a right child 
 case 4 in RTAVL deletion  Case 4: p's left child has a right child 
 case 4 in RTAVL deletion, alternate version  Section 11.5.4 
 case 4 in RTAVL deletion, rightlooking  Section 11.5.4 
 case 4 in RTRB deletion  Case 4: p's left child has a right child 
 case 4 in TAVL deletion  Case 4: p's right child has a left child 
 case 4 in TAVL deletion, alternate version  Section 8.5.2 
 case 4 in TAVL deletion, with stack  Section 8.5.6 
 case 4 in TBST deletion  Case 4: p's right child has a left child 
 case 4 in TBST deletion  Case 4: p's right child has a left child 
 case 4 in TBST deletion  Case 4: p's right child has a left child 
 case 4 in TBST deletion, alternate version  Section 7.7 
 case 4 in TRB deletion  Case 4: p's right child has a left child 
 case 4 in TRB deletion, alternate version  Section 9.4.2 
 cheat_search function  Section 3.5 
 cheating search  Section 3.5 
 check AVL tree structure  6.8 Testing 
 check BST structure  5.14.1.1 BST Verification 
 check counted nodes  5.14.1.1 BST Verification 
 check for tree height in range  5.12.2.2 Implementation 
 check RB tree structure  7.6 Testing 
 check root is black  7.6 Testing 
 check that backward traversal works  5.14.1.1 BST Verification 
 check that forward traversal works  5.14.1.1 BST Verification 
 check that the tree contains all the elements it should  5.14.1.1 BST Verification 
 check that traversal from the null element works  5.14.1.1 BST Verification 
 check tree>bst_count is correct  5.14.1.1 BST Verification 
 check_traverser function  5.14.1 Testing BSTs 
 clean up after search tests  Section 3.5 
 command line parser  B.2 CommandLine Parser 
 compare two AVL trees for structure and content  6.8 Testing 
 compare two BSTs for structure and content  5.14.1 Testing BSTs 
 compare two PAVL trees for structure and content  15.8 Testing 
 compare two PBSTs for structure and content  14.8 Testing 
 compare two PRB trees for structure and content  16.5 Testing 
 compare two RB trees for structure and content  7.6 Testing 
 compare two RTAVL trees for structure and content  12.7 Testing 
 compare two RTBSTs for structure and content  11.10 Testing 
 compare two RTRB trees for structure and content  13.5 Testing 
 compare two TAVL trees for structure and content  9.7 Testing 
 compare two TBSTs for structure and content  8.12 Testing 
 compare two TRB trees for structure and content  10.5 Testing 
 compare_fixed_strings function  Section 2.3 
 compare_ints function  3.3 Comparison Function 
 compare_ints function  Section 2.3 
 compare_ints function  Section 2.3 
 compare_ints function  Section 3.5 
 compare_trees function  6.8 Testing 
 compare_trees function  7.6 Testing 
 compare_trees function  8.12 Testing 
 compare_trees function  9.7 Testing 
 compare_trees function  10.5 Testing 
 compare_trees function  11.10 Testing 
 compare_trees function  12.7 Testing 
 compare_trees function  13.5 Testing 
 compare_trees function  14.8 Testing 
 compare_trees function  15.8 Testing 
 compare_trees function  16.5 Testing 
 comparison function for ints  3.3 Comparison Function 
 compress function  8.11.2 From Vine to Balanced Tree 
 compress function  Section 13.7 
 copy_error_recovery function  5.10.3 Error Handling 
 copy_error_recovery function  8.9 Copying 
 copy_error_recovery function  11.7 Copying 
 copy_error_recovery function  14.6 Copying 
 copy_node function  8.9 Copying 
 copy_node function  9.6 Copying 
 copy_node function  11.7 Copying 
 copy_node function  12.6 Copying 
