| 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, right-looking | Section 11.5.4 |
| delete RTBST node, left-looking | 11.5.2 Left-Looking Deletion |
| delete RTBST node, right-looking | 11.5.1 Right-Looking 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 left-side PRB deletion rebalancing | Case Reduction: Ensure w is black |
| ensure w is black in left-side RB deletion rebalancing | Case Reduction: Ensure w is black |
| ensure w is black in left-side TRB deletion rebalancing | Case Reduction: Ensure w is black |
| ensure w is black in right-side PRB deletion rebalancing | 16.4.4 Symmetric Case |
| ensure w is black in right-side RB deletion rebalancing | 7.5.4 Symmetric Case |
| ensure w is black in right-side 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 1--2: 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 | | |
|---|
| left-side rebalancing after initial-black RB insertion | 7.4.5 Aside: Initial Black Insertion |
| left-side rebalancing after PRB deletion | 16.4.2 Step 3: Rebalance |
| left-side rebalancing after PRB insertion | 16.3.2 Step 3: Rebalance |
| left-side rebalancing after RB deletion | 7.5.2 Step 3: Rebalance |
| left-side rebalancing after RB insertion | 7.4.3 Step 3: Rebalance |
| left-side rebalancing after RTRB deletion | 13.4.2 Step 3: Rebalance |
| left-side rebalancing after RTRB insertion | 13.3.2 Step 3: Rebalance |
| left-side rebalancing after TRB deletion | 10.4.3 Step 3: Rebalance |
| left-side rebalancing after TRB insertion | 10.3.2 Step 3: Rebalance |
| left-side rebalancing case 1 in AVL deletion | Case 1: x has - balance factor |
| left-side rebalancing case 1 in PAVL deletion | Case 1: x has - balance factor |
| left-side rebalancing case 2 in AVL deletion | Case 2: x has + or 0 balance factor |
| left-side rebalancing case 2 in PAVL deletion | Case 2: x has + or 0 balance factor |
| level-order traversal | Section 4.7 |
| libavl_allocator structure | 3.5 Memory Allocation |
| license | 2.4 License |
|
