Appendix G Index |

- aborting allocator: Answers for Chapter 2
- array of search functions: Answers for Chapter 3
- AVL copy function: Copying an AVL Tree
- AVL functions: AVL Operations
- AVL item deletion function: Deleting from an AVL Tree
- AVL item insertion function: Inserting into an AVL Tree
- AVL maximum height: Analysis of AVL Balancing Rule
- AVL node structure: AVL Data Types
- AVL traversal functions: Traversal of an AVL Tree
- AVL traverser advance function: Traversal of an AVL Tree
- AVL traverser back up function: Traversal of an AVL Tree
- AVL traverser greatest-item initializer: Traversal of an AVL Tree
- AVL traverser insertion initializer: Traversal of an AVL Tree
- AVL traverser least-item initializer: Traversal of an AVL Tree
- AVL traverser search initializer: Traversal of an AVL Tree
- AVL tree verify function: Testing AVL Trees
`avl-test.c`: Testing AVL Trees`avl.c`: AVL Trees`avl.h`: AVL Trees*avl_copy*function: Copying an AVL Tree*avl_delete*function: Deleting from an AVL Tree`AVL_H`macro: AVL Trees`AVL_MAX_HEIGHT`macro: Analysis of AVL Balancing Rule*avl_node*structure: AVL Data Types*avl_probe*function: Inserting into an AVL Tree*avl_probe*() local variables: Inserting into an AVL Tree*avl_t_find*function: Traversal of an AVL Tree*avl_t_first*function: Traversal of an AVL Tree*avl_t_insert*function: Traversal of an AVL Tree*avl_t_last*function: Traversal of an AVL Tree*avl_t_next*function: Traversal of an AVL Tree*avl_t_prev*function: Traversal of an AVL Tree`bin-ary-test.c`: Answers for Chapter 3*bin_cmp*function: Answers for Chapter 2- binary search of ordered array: Binary Search of Ordered Array
- binary search tree entry: Binary Search Tree in Array
- binary search using
*bsearch*(): Answers for Chapter 3 *binary_tree_entry*structure: Binary Search Tree in Array*block*structure: Memory Manager- blp's implementation of
*bsearch*(): Answers for Chapter 3 *blp_bsearch*function: Answers for Chapter 3- BST balance function: Balancing a BST
- BST compression function: Implementing Compression
- BST copy error helper function: Handling Errors in Iterative BST Copying
- BST copy function: Handling Errors in Iterative BST Copying
- BST creation function: Creating a BST
- BST destruction function: Destroying a BST by Rotation
- BST extra function prototypes: Balancing a BST
- BST item deletion function: Deleting from a BST
- BST item deletion function, by merging: Deletion by Merging
- BST item insertion function: Inserting into a BST
- BST item insertion function, alternate version: Answers for Chapter 4
- BST item insertion function, root insertion version: Root Insertion in a BST
- BST join function, iterative version: Answers for Chapter 4
- BST join function, recursive version: Joining BSTs
- BST maximum height: BST Maximum Height
- BST node structure: BST Node Structure
- BST operations: BST Operations
- BST overflow test function: Testing Overflow
- BST print function: Displaying BST Structures
- BST search function: Searching a BST
- BST table structure: BST Structure
- BST test function: Testing BSTs
- BST to vine function: Transforming a BST into a Vine
- BST traversal functions: Better Iterative Traversal
- BST traverser advance function: BST Traverser Advancing
- BST traverser back up function: BST Traverser Retreating
- BST traverser check function: Testing BSTs
- BST traverser copy initializer: BST Traverser Copying
- BST traverser current item function: BST Traversal Current Item
- BST traverser greatest-item initializer: BST Traverser Last Initialization
- BST traverser insertion initializer: BST Traverser Insert Initialization
- BST traverser least-item initializer: BST Traverser First Initialization
- BST traverser null initializer: BST Traverser Null Initialization
- BST traverser refresher: Better Iterative Traversal
- BST traverser refresher, with caching: Answers for Chapter 4
- BST traverser replacement function: BST Traversal Replacing the Current Item
- BST traverser search initializer: BST Traverser Find Initialization
- BST traverser structure: Better Iterative Traversal
- BST verify function: BST Verification
`bst-test.c`: Testing BST Functions`bst.c`: Binary Search Trees`bst.h`: Binary Search Trees*bst_balance*function: Balancing a BST*bst_copy*function: Handling Errors in Iterative BST Copying*bst_copy_iterative*function: Answers for Chapter 4*bst_copy_iterative*function: Copying a BST Iteratively*bst_copy_recursive_1*function: Copying a BST Recursively*bst_create*function: Creating a BST*bst_deallocate_recursive*function: Answers for Chapter 4*bst_delete*function: Deletion by Merging*bst_delete*function: Deleting from a BST*bst_destroy*function: Destroying a BST Iteratively*bst_destroy*function: Destroying a BST by Rotation*bst_destroy_recursive*function: Destroying a BST Recursively*bst_find*function: Answers for Chapter 2*bst_find*function: Searching a BST`BST_H`macro: Binary Search Trees`BST_MAX_HEIGHT`macro: BST Maximum Height*bst_node*structure: BST Node Structure*bst_probe*function: Answers for Chapter 4*bst_probe*function: Root Insertion in a BST*bst_probe*function: Inserting into a BST*bst_robust_copy_recursive_1*function: Answers for Chapter 4*bst_robust_copy_recursive_2*function: Answers for Chapter 4*bst_t_copy*function: BST Traverser Copying*bst_t_cur*function: BST Traversal Current Item*bst_t_find*function: BST Traverser Find Initialization*bst_t_first*function: BST Traverser First Initialization*bst_t_init*function: BST Traverser Null Initialization*bst_t_insert*function: BST Traverser Insert Initialization*bst_t_last*function: BST Traverser Last Initialization*bst_t_next*function: BST Traverser Advancing*bst_t_prev*function: BST Traverser Retreating*bst_t_replace*function: BST Traversal Replacing the Current Item*bst_table*structure: BST Structure*bst_traverse_level_order*function: Answers for Chapter 4*bst_traverser*structure: Better Iterative Traversal- BSTS functions: Answers for Chapter 4
- BSTS structures: Answers for Chapter 4
- BSTS test: Answers for Chapter 4
`bsts.c`: Answers for Chapter 4*bsts_find*function: Answers for Chapter 4*bsts_insert*function: Answers for Chapter 4*bsts_node*structure: Answers for Chapter 4*bsts_tree*structure: Answers for Chapter 4- calculate
*leaves*: Balancing Implementation - case 1 in AVL deletion: Deleting an AVL Node Step 2 - Delete
- case 1 in BST deletion: Deleting from a BST
- case 1 in left-looking RTBST deletion: Left-Looking Deletion in an RTBST
- case 1 in left-side initial-black RB insertion rebalancing: Initial Black Insertion in an RB Tree
- case 1 in left-side PRB deletion rebalancing: Deleting a PRB Node Step 3 - Rebalance
- case 1 in left-side PRB insertion rebalancing: Step 3 in PRB Insertion
- case 1 in left-side RB deletion rebalancing: Deleting an RB Node Step 3 - Rebalance
- case 1 in left-side RB insertion rebalancing: Inserting an RB Node Step 3 - Rebalance
- case 1 in left-side RTRB insertion rebalancing: Step 3 in RTRB Insertion
- case 1 in left-side TRB deletion rebalancing: Deleting a TRB Node Step 3 - Rebalance
- case 1 in left-side TRB insertion rebalancing: Step 3 in TRB Insertion
- case 1 in PAVL deletion: Deleting a PAVL Node Step 2 - Delete
- case 1 in PBST deletion: Deleting from a PBST
- case 1 in PRB deletion: Deleting a PRB Node Step 2 - Delete
- case 1 in RB deletion: Deleting an RB Node Step 2 - Delete
- case 1 in right-looking RTBST deletion: Right-Looking Deletion in a RTBST
- case 1 in right-side initial-black RB insertion rebalancing: Initial Black Insertion in an RB Tree
- case 1 in right-side PRB deletion rebalancing: PRB Deletion Symmetric Case
- case 1 in right-side PRB insertion rebalancing: PRB Insertion Symmetric Case
- case 1 in right-side RB deletion rebalancing: RB Deletion Symmetric Case
- case 1 in right-side RB insertion rebalancing: RB Insertion Symmetric Case
- case 1 in right-side RTRB insertion rebalancing: Step 3 in RTRB Insertion
- case 1 in right-side TRB deletion rebalancing: TRB Deletion Symmetric Case
- case 1 in right-side TRB insertion rebalancing: TRB Insertion Symmetric Case
- case 1 in RTAVL deletion: Deleting a RTAVL Node Step 2 - Delete
- case 1 in RTAVL deletion, right-looking: Answers for Chapter 11
- case 1 in RTRB deletion: Deleting an RTRB Node Step 2 - Delete
- case 1 in TAVL deletion: Deleting a TAVL Node Step 2 - Delete
- case 1 in TAVL deletion, with stack: Answers for Chapter 8
- case 1 in TBST deletion: Deleting from a TBST
- case 1 in TRB deletion: Deleting a TRB Node Step 2 - Delete
- case 1.5 in BST deletion: Answers for Chapter 4
- case 2 in AVL deletion: Deleting an AVL Node Step 2 - Delete
- case 2 in BST deletion: Deleting from a BST
- case 2 in left-looking RTBST deletion: Left-Looking Deletion in an RTBST
- case 2 in left-side initial-black RB insertion rebalancing: Initial Black Insertion in an RB Tree
- case 2 in left-side PRB deletion rebalancing: Deleting a PRB Node Step 3 - Rebalance
- case 2 in left-side PRB insertion rebalancing: Step 3 in PRB Insertion
- case 2 in left-side RB deletion rebalancing: Deleting an RB Node Step 3 - Rebalance
- case 2 in left-side RB insertion rebalancing: Inserting an RB Node Step 3 - Rebalance
- case 2 in left-side RTRB deletion rebalancing: Deleting an RTRB Node Step 3 - Rebalance
- case 2 in left-side RTRB insertion rebalancing: Step 3 in RTRB Insertion
- case 2 in left-side TRB deletion rebalancing: Deleting a TRB Node Step 3 - Rebalance
- case 2 in left-side TRB insertion rebalancing: Step 3 in TRB Insertion
- case 2 in PAVL deletion: Deleting a PAVL Node Step 2 - Delete
- case 2 in PBST deletion: Deleting from a PBST
- case 2 in PRB deletion: Deleting a PRB Node Step 2 - Delete
- case 2 in RB deletion: Deleting an RB Node Step 2 - Delete
- case 2 in right-looking RTBST deletion: Right-Looking Deletion in a RTBST
- case 2 in right-side initial-black RB insertion rebalancing: Initial Black Insertion in an RB Tree
- case 2 in right-side PRB deletion rebalancing: PRB Deletion Symmetric Case
- case 2 in right-side PRB insertion rebalancing: PRB Insertion Symmetric Case
- case 2 in right-side RB deletion rebalancing: RB Deletion Symmetric Case
- case 2 in right-side RB insertion rebalancing: RB Insertion Symmetric Case
- case 2 in right-side RTRB deletion rebalancing: Deleting an RTRB Node Step 3 - Rebalance
- case 2 in right-side RTRB insertion rebalancing: Step 3 in RTRB Insertion
- case 2 in right-side TRB deletion rebalancing: TRB Deletion Symmetric Case
- case 2 in right-side TRB insertion rebalancing: TRB Insertion Symmetric Case
- case 2 in RTAVL deletion: Deleting a RTAVL Node Step 2 - Delete
- case 2 in RTAVL deletion, right-looking: Answers for Chapter 11
- case 2 in RTRB deletion: Deleting an RTRB Node Step 2 - Delete
- case 2 in TAVL deletion: Deleting a TAVL Node Step 2 - Delete
- case 2 in TAVL deletion, with stack: Answers for Chapter 8
- case 2 in TBST deletion: Deleting from a TBST
- case 2 in TRB deletion: Deleting a TRB Node Step 2 - Delete
- case 3 in AVL deletion: Deleting an AVL Node Step 2 - Delete
- case 3 in AVL deletion, alternate version: Answers for Chapter 5
- case 3 in BST deletion: Deleting from a BST
- case 3 in BST deletion, alternate version: Answers for Chapter 4
- case 3 in left-looking RTBST deletion: Left-Looking Deletion in an RTBST
- case 3 in left-side initial-black RB insertion rebalancing: Initial Black Insertion in an RB Tree
- case 3 in left-side PRB insertion rebalancing: Step 3 in PRB Insertion
- case 3 in left-side RB insertion rebalancing: Inserting an RB Node Step 3 - Rebalance
- case 3 in left-side RTRB insertion rebalancing: Step 3 in RTRB Insertion
- case 3 in left-side TRB insertion rebalancing: Step 3 in TRB Insertion
- case 3 in PAVL deletion: Deleting a PAVL Node Step 2 - Delete
- case 3 in PBST deletion: Deleting from a PBST
- case 3 in PRB deletion: Deleting a PRB Node Step 2 - Delete
- case 3 in RB deletion: Deleting an RB Node Step 2 - Delete
- case 3 in right-looking RTBST deletion: Right-Looking Deletion in a RTBST
- case 3 in right-side initial-black RB insertion rebalancing: Initial Black Insertion in an RB Tree
- case 3 in right-side PRB insertion rebalancing: PRB Insertion Symmetric Case
- case 3 in right-side RB insertion rebalancing: RB Insertion Symmetric Case
- case 3 in right-side RTRB insertion rebalancing: Step 3 in RTRB Insertion
- case 3 in right-side TRB insertion rebalancing: TRB Insertion Symmetric Case
- case 3 in RTAVL deletion: Deleting a RTAVL Node Step 2 - Delete
- case 3 in RTAVL deletion, right-looking: Answers for Chapter 11
- case 3 in RTRB deletion: Deleting an RTRB Node Step 2 - Delete
- case 3 in TAVL deletion: Deleting a TAVL Node Step 2 - Delete
- case 3 in TAVL deletion, with stack: Answers for Chapter 8
- case 3 in TBST deletion: Deleting from a TBST
- case 3 in TRB deletion: Deleting a TRB Node Step 2 - Delete
- case 4 in left-looking RTBST deletion: Left-Looking Deletion in an RTBST
- case 4 in left-looking RTBST deletion, alternate version: Answers for Chapter 10
- case 4 in right-looking RTBST deletion: Right-Looking Deletion in a RTBST
- case 4 in right-looking RTBST deletion, alternate version: Answers for Chapter 10
- case 4 in RTAVL deletion: Deleting a RTAVL Node Step 2 - Delete
- case 4 in RTAVL deletion, alternate version: Answers for Chapter 11
- case 4 in RTAVL deletion, right-looking: Answers for Chapter 11
- case 4 in RTRB deletion: Deleting an RTRB Node Step 2 - Delete
- case 4 in TAVL deletion: Deleting a TAVL Node Step 2 - Delete
- case 4 in TAVL deletion, alternate version: Answers for Chapter 8
- case 4 in TAVL deletion, with stack: Answers for Chapter 8
- case 4 in TBST deletion: Deleting from a TBST
- case 4 in TBST deletion, alternate version: Answers for Chapter 7
- case 4 in TRB deletion: Deleting a TRB Node Step 2 - Delete
- case 4 in TRB deletion, alternate version: Answers for Chapter 9
*cheat_search*function: Answers for Chapter 3- cheating search: Answers for Chapter 3
- check AVL tree structure: Testing AVL Trees
- check BST structure: BST Verification
- check counted nodes: BST Verification
- check for tree height in range: Balancing Implementation
- check RB tree structure: Testing RB Trees
- check root is black: Testing RB Trees
- check that backward traversal works: BST Verification
- check that forward traversal works: BST Verification
- check that the tree contains all the elements it should: BST Verification
- check that traversal from the null element works: BST Verification
- check
*tree*->*bst_count*is correct: BST Verification *check_traverser*function: Testing BSTs- clean up after search tests: Answers for Chapter 3
- command line parser: Command-Line Parser
- compare two AVL trees for structure and content: Testing AVL Trees
- compare two BSTs for structure and content: Testing BSTs
- compare two PAVL trees for structure and content: Testing PAVL Trees
- compare two PBSTs for structure and content: Testing PBSTs
- compare two PRB trees for structure and content: Testing PRB Trees
- compare two RB trees for structure and content: Testing RB Trees
- compare two RTAVL trees for structure and content: Testing RTAVL Trees
- compare two RTBSTs for structure and content: Testing RTBSTs
- compare two RTRB trees for structure and content: Testing RTRB Trees
- compare two TAVL trees for structure and content: Testing TAVL Trees
- compare two TBSTs for structure and content: Testing TBSTs
- compare two TRB trees for structure and content: Testing TRB Trees
*compare_fixed_strings*function: Answers for Chapter 2*compare_ints*function: Answers for Chapter 3*compare_ints*function: Answers for Chapter 2*compare_ints*function: Comparison Function*compare_trees*function: Testing PRB Trees*compare_trees*function: Testing PAVL Trees*compare_trees*function: Testing PBSTs*compare_trees*function: Testing RTRB Trees*compare_trees*function: Testing RTAVL Trees*compare_trees*function: Testing RTBSTs*compare_trees*function: Testing TRB Trees*compare_trees*function: Testing TAVL Trees*compare_trees*function: Testing TBSTs*compare_trees*function: Testing RB Trees*compare_trees*function: Testing AVL Trees- comparison function for
**int**s: Comparison Function *compress*function: Answers for Chapter 13*compress*function: Transforming a Vine into a Balanced TBST*copy_error_recovery*function: Copying a PBST*copy_error_recovery*function: Copying an RTBST*copy_error_recovery*function: Copying a TBST*copy_error_recovery*function: Handling Errors in Iterative BST Copying*copy_node*function: Copying an RTAVL Tree*copy_node*function: Copying an RTBST*copy_node*function: Copying a TAVL Tree*copy_node*function: Copying a TBST- default memory allocation functions: Memory Allocation
- default memory allocator header: Memory Allocation
- delete BST node: Deleting from a BST
- delete BST node by merging: Deletion by Merging
- delete item from AVL tree: Deleting an AVL Node Step 2 - Delete
- delete item from PAVL tree: Deleting a PAVL Node Step 2 - Delete
- delete item from PRB tree: Deleting a PRB Node Step 2 - Delete
- delete item from RB tree: Deleting an RB Node Step 2 - Delete
- delete item from RB tree, alternate version: Answers for Chapter 6
- delete item from TAVL tree: Deleting a TAVL Node Step 2 - Delete
- delete item from TAVL tree, with stack: Answers for Chapter 8
- delete item from TRB tree: Deleting a TRB Node Step 2 - Delete
- delete PBST node: Deleting from a PBST
- delete RTAVL node: Deleting a RTAVL Node Step 2 - Delete
- delete RTAVL node, right-looking: Answers for Chapter 11
- delete RTBST node, left-looking: Left-Looking Deletion in an RTBST
- delete RTBST node, right-looking: Right-Looking Deletion in a RTBST
- delete RTRB node: Deleting an RTRB Node Step 2 - Delete
- delete TBST node: Deleting from a TBST
*delete_order*enumeration: Test Set Generation- destroy a BST iteratively: Destroying a BST Iteratively
- destroy a BST recursively: Destroying a BST Recursively
- ensure
*w*is black in left-side PRB deletion rebalancing: Deleting a PRB Node Step 3 - Rebalance - ensure
*w*is black in left-side RB deletion rebalancing: Deleting an RB Node Step 3 - Rebalance - ensure
*w*is black in left-side TRB deletion rebalancing: Deleting a TRB Node Step 3 - Rebalance - ensure
*w*is black in right-side PRB deletion rebalancing: PRB Deletion Symmetric Case - ensure
*w*is black in right-side RB deletion rebalancing: RB Deletion Symmetric Case - ensure
*w*is black in right-side TRB deletion rebalancing: TRB Deletion Symmetric Case *error_node*variable: Answers for Chapter 4*fail*function: Utility Functions*fallback_join*function: Answers for Chapter 4- find BST node to delete: Deleting from a BST
- find BST node to delete by merging: Deletion by Merging
- find parent of a TBST node: Finding the Parent of a TBST Node
- find PBST node to delete: Deleting from a PBST
- find predecessor of RTBST node with left child: RTBST Traverser Retreating
- find predecessor of RTBST node with no left child: RTBST Traverser Retreating
- find RTBST node to delete: Deleting from an RTBST
- find TBST node to delete: Deleting from a TBST
- find TBST node to delete, with parent node algorithm: Answers for Chapter 7
*find_parent*function: Finding the Parent of a TBST Node- finish up after BST deletion by merging: Deletion by Merging
- finish up after deleting BST node: Deleting from a BST
- finish up after deleting PBST node: Deleting from a PBST
- finish up after deleting RTBST node: Deleting from an RTBST
- finish up after deleting TBST node: Deleting from a TBST
- finish up after PRB deletion: Deleting a PRB Node Step 4 - Finish Up
- finish up after RB deletion: Deleting an RB Node Step 4 - Finish Up
- finish up after RTRB deletion: Deleting an RTRB Node Step 4 - Finish Up
- finish up after TRB deletion: Deleting a TRB Node Step 4 - Finish Up
- finish up and return after AVL deletion: Deleting an AVL Node Step 5 - Finish Up
*first_item*function: Improving Convenience- found insertion point in recursive AVL insertion: Recursive Insertion
*gen_balanced_tree*function: Answers for Chapter 4*gen_deletions*function: Answers for Chapter 4*gen_insertions*function: Answers for Chapter 4- generate permutation for balanced tree: Answers for Chapter 4
- generate random permutation of integers: Answers for Chapter 4
- handle case where
*x*has a right child: BST Traverser Advancing - handle case where
*x*has no right child: BST Traverser Advancing - handle stack overflow during BST traversal: Answers for Chapter 4
*handle_long_option*function: Option Parser*handle_short_option*function: Option Parser- initialize search test array: Answers for Chapter 3
- initialize
*smaller*and*larger*within binary search tree: Answers for Chapter 3 - insert AVL node: Step 2 in AVL Insertion
- insert
*n*into arbitrary subtree: Answers for Chapter 4 - insert new BST node, root insertion version: Root Insertion in a BST
- insert new node into RTBST tree: Inserting into an RTBST
- insert PAVL node: Steps 1 and 2 in PAVL Insertion
- insert PBST node: Inserting into a PBST
- insert PRB node: Step 2 in PRB Insertion
- insert RB node: Inserting an RB Node Step 2 - Insert
- insert RTAVL node: Steps 1-1 in RTAVL Insertion
- insert RTRB node: Steps 1 and 2 in RTRB Insertion
- insert TAVL node: Steps 1 and 2 in TAVL Insertion
- insert TBST node: Inserting into a TBST
- insert TRB node: Steps 1 and 2 in TRB Insertion
*insert_order*enumeration: Test Set Generation- insertion and deletion order generation: Answers for Chapter 4
- intermediate step between
*bst_copy_recursive_2*() and*bst_copy_iterative*(): Answers for Chapter 4 *iter*variable: Answers for Chapter 4- iterative copy of BST: Copying a BST Iteratively
- iterative traversal of BST, take 1: Iterative Traversal of a BST
- iterative traversal of BST, take 2: Iterative Traversal of a BST
- iterative traversal of BST, take 3: Iterative Traversal of a BST
- iterative traversal of BST, take 4: Iterative Traversal of a BST
- iterative traversal of BST, take 5: Iterative Traversal of a BST
- iterative traversal of BST, take 6: Improving Convenience
- iterative traversal of BST, with dynamically allocated stack: Answers for Chapter 4
- left-side rebalancing after initial-black RB insertion: Initial Black Insertion in an RB Tree
- left-side rebalancing after PRB deletion: Deleting a PRB Node Step 3 - Rebalance
- left-side rebalancing after PRB insertion: Step 3 in PRB Insertion
- left-side rebalancing after RB deletion: Deleting an RB Node Step 3 - Rebalance
- left-side rebalancing after RB insertion: Inserting an RB Node Step 3 - Rebalance
- left-side rebalancing after RTRB deletion: Deleting an RTRB Node Step 3 - Rebalance
- left-side rebalancing after RTRB insertion: Step 3 in RTRB Insertion
- left-side rebalancing after TRB deletion: Deleting a TRB Node Step 3 - Rebalance
- left-side rebalancing after TRB insertion: Step 3 in TRB Insertion
- left-side rebalancing case 1 in AVL deletion: Deleting an AVL Node Step 4 - Rebalance
- left-side rebalancing case 1 in PAVL deletion: Deleting a PAVL Node Step 4 - Rebalance
- left-side rebalancing case 2 in AVL deletion: Deleting an AVL Node Step 4 - Rebalance
- left-side rebalancing case 2 in PAVL deletion: Deleting a PAVL Node Step 4 - Rebalance
- level-order traversal: Answers for Chapter 4
`LIBAVL_ALLOCATOR`macro: Memory Allocation*libavl_allocator*structure: Memory Allocation- library License: Licenses
*main*function: Answers for Chapter 3*main*function: Main Program- main program to test
*binary_search_tree_array*(): Answers for Chapter 3 - make special case TBST vine into balanced tree and count height: Transforming a Vine into a Balanced TBST
- make special case vine into balanced tree and count height: Balancing Implementation
`MAX_INPUT`macro: Answers for Chapter 3- memory allocator: Memory Allocation
- memory tracker: Memory Manager
- move BST node to root: Root Insertion in a BST
- move down then up in recursive AVL insertion: Recursive Insertion
*mt_allocate*function: Memory Manager*mt_allocator*function: Memory Manager*mt_allocator*structure: Memory Manager*mt_arg_index*enumeration: Memory Manager*mt_create*function: Memory Manager*mt_free*function: Memory Manager*mt_policy*enumeration: Memory Manager*new_block*function: Memory Manager- option parser: Option Parser
*option*structure: User Interaction*option_get*function: Option Parser*option_init*function: Option Parser*option_state*structure: Option Parser- overflow testers: Answers for Chapter 4
- overflow testers: Testing Overflow
- parse search test command line: Answers for Chapter 3
*parse_command_line*function: Command-Line Parser- PAVL copy function: Copying a PAVL Tree
- PAVL functions: PAVL Operations
- PAVL item deletion function: Deleting from a PAVL Tree
- PAVL item insertion function: Inserting into a PAVL Tree
- PAVL node structure: PAVL Data Types
- PAVL traversal functions: Traversing a PAVL Tree
`pavl-test.c`: Testing PAVL Trees`pavl.c`: AVL Trees with Parent Pointers`pavl.h`: AVL Trees with Parent Pointers*pavl_copy*function: Copying a PAVL Tree*pavl_delete*function: Deleting from a PAVL Tree`PAVL_H`macro: AVL Trees with Parent Pointers*pavl_node*structure: PAVL Data Types*pavl_probe*function: Inserting into a PAVL Tree- PBST balance function: Balancing a PBST
- PBST balance function, with integrated parent updates: Answers for Chapter 13
- PBST compression function: Answers for Chapter 13
- PBST copy error helper function: Copying a PBST
- PBST copy function: Copying a PBST
- PBST extra function prototypes: Balancing a PBST
- PBST functions: PBST Operations
- PBST item deletion function: Deleting from a PBST
- PBST item insertion function: Inserting into a PBST
- PBST node structure: PBST Data Types
- PBST traversal functions: Traversing a PBST
- PBST traverser advance function: PBST Traverser Advancing
- PBST traverser back up function: PBST Traverser Retreating
- PBST traverser first initializer: PBST Traverser First Initialization
- PBST traverser insertion initializer: PBST Traverser Insert Initialization
- PBST traverser last initializer: PBST Traverser Last Initialization
- PBST traverser search initializer: PBST Traverser Find Initialization
`pbst-test.c`: Testing PBSTs`pbst.c`: BSTs with Parent Pointers`pbst.h`: BSTs with Parent Pointers*pbst_balance*function: Answers for Chapter 13*pbst_balance*function: Balancing a PBST*pbst_copy*function: Copying a PBST*pbst_delete*function: Deleting from a PBST`PBST_H`macro: BSTs with Parent Pointers*pbst_node*structure: PBST Data Types*pbst_probe*function: Inserting into a PBST*pbst_t_find*function: PBST Traverser Find Initialization*pbst_t_first*function: PBST Traverser First Initialization*pbst_t_insert*function: PBST Traverser Insert Initialization*pbst_t_last*function: PBST Traverser Last Initialization*pbst_t_next*function: PBST Traverser Advancing*pbst_t_prev*function: PBST Traverser Retreating*permuted_integers*function: Answers for Chapter 4*pgm_name*variable: Main Program*pool_allocator*structure: Answers for Chapter 2*pool_allocator_free*function: Answers for Chapter 2*pool_allocator_malloc*function: Answers for Chapter 2*pool_allocator_tbl_create*function: Answers for Chapter 2- PRB functions: PRB Operations
- PRB item deletion function: Deleting from a PRB Tree
- PRB item insertion function: Inserting into a PRB Tree
- PRB node structure: PRB Data Types
`prb-test.c`: Testing PRB Trees`prb.c`: Red-Black Trees with Parent Pointers`prb.h`: Red-Black Trees with Parent Pointers*prb_color*enumeration: PRB Data Types*prb_delete*function: Deleting from a PRB Tree`PRB_H`macro: Red-Black Trees with Parent Pointers*prb_node*structure: PRB Data Types*prb_probe*function: Inserting into a PRB Tree*print_tree_structure*function: Testing RTBSTs*print_tree_structure*function: Testing TBSTs*print_whole_tree*function: Testing RTBSTs*print_whole_tree*function: Testing TBSTs*print_whole_tree*function: Displaying BST Structures*probe*function: Recursive Insertion*process_node*function: Improving Convenience- program License: Licenses
- random number seeding: Answers for Chapter 4
- RB functions: Operations in an RB Tree
- RB item deletion function: Deleting from an RB Tree
- RB item insertion function: Inserting into an RB Tree
- RB item insertion function, initial black: Initial Black Insertion in an RB Tree
- RB maximum height: RB Data Types
- RB node structure: RB Data Types
- RB tree verify function: Testing RB Trees
`rb-test.c`: Testing RB Trees`rb.c`: Red-Black Trees`rb.h`: Red-Black Trees*rb_color*enumeration: RB Data Types*rb_delete*function: Deleting from an RB Tree`RB_H`macro: Red-Black Trees`RB_MAX_HEIGHT`macro: RB Data Types*rb_node*structure: RB Data Types*rb_probe*function: Initial Black Insertion in an RB Tree*rb_probe*function: Inserting into an RB Tree*rb_probe*() local variables: Inserting into an RB Tree- rebalance + balance in TAVL insertion in left subtree, alternate version: Answers for Chapter 8
- rebalance after AVL deletion: Deleting an AVL Node Step 4 - Rebalance
- rebalance after AVL insertion: Rebalancing AVL Trees
- rebalance after initial-black RB insertion: Initial Black Insertion in an RB Tree
- rebalance after PAVL deletion: Deleting a PAVL Node Step 4 - Rebalance
- rebalance after PAVL insertion: Rebalancing PAVL Trees
- rebalance after PRB insertion: Step 3 in PRB Insertion
- rebalance after RB deletion: Deleting an RB Node Step 3 - Rebalance
- rebalance after RB insertion: Inserting an RB Node Step 3 - Rebalance
- rebalance after RTAVL deletion in left subtree: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance after RTAVL deletion in right subtree: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance after RTAVL insertion: Rebalancing RTAVL Trees
- rebalance after RTRB deletion: Deleting an RTRB Node Step 3 - Rebalance
- rebalance after RTRB insertion: Step 3 in RTRB Insertion
- rebalance after TAVL deletion: Deleting a TAVL Node Step 4 - Rebalance
- rebalance after TAVL deletion, with stack: Answers for Chapter 8
- rebalance after TAVL insertion: Rebalancing TAVL Trees
- rebalance after TRB insertion: Step 3 in TRB Insertion
- rebalance AVL tree after insertion in left subtree: Rebalancing AVL Trees
- rebalance AVL tree after insertion in right subtree: AVL Insertion Symmetric Case
- rebalance for + balance factor after left-side RTAVL deletion: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance for + balance factor after right-side RTAVL deletion: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance for + balance factor after TAVL deletion in left subtree: Deleting a TAVL Node Step 4 - Rebalance
- rebalance for + balance factor after TAVL deletion in right subtree: TAVL Deletion Symmetric Case
- rebalance for + balance factor in PAVL insertion in left subtree: Rebalancing PAVL Trees
- rebalance for + balance factor in PAVL insertion in right subtree: PAVL Insertion Symmetric Case
- rebalance for + balance factor in RTAVL insertion in left subtree: Rebalancing RTAVL Trees
- rebalance for + balance factor in RTAVL insertion in right subtree: Rebalancing RTAVL Trees
- rebalance for + balance factor in TAVL insertion in left subtree: Rebalancing TAVL Trees
- rebalance for + balance factor in TAVL insertion in right subtree: TAVL Insertion Symmetric Case
- rebalance for - balance factor after left-side RTAVL deletion: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance for - balance factor after right-side RTAVL deletion: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance for - balance factor after TAVL deletion in left subtree: Deleting a TAVL Node Step 4 - Rebalance
- rebalance for - balance factor after TAVL deletion in right subtree: TAVL Deletion Symmetric Case
- rebalance for - balance factor in PAVL insertion in left subtree: Rebalancing PAVL Trees
- rebalance for - balance factor in PAVL insertion in right subtree: PAVL Insertion Symmetric Case
- rebalance for - balance factor in RTAVL insertion in left subtree: Rebalancing RTAVL Trees
- rebalance for - balance factor in RTAVL insertion in right subtree: Rebalancing RTAVL Trees
- rebalance for - balance factor in TAVL insertion in left subtree: Rebalancing TAVL Trees
- rebalance for - balance factor in TAVL insertion in right subtree: TAVL Insertion Symmetric Case
- rebalance for 0 balance factor after left-side RTAVL deletion: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance for 0 balance factor after right-side RTAVL deletion: Deleting a RTAVL Node Step 4 - Rebalance
- rebalance for 0 balance factor after TAVL deletion in left subtree: Deleting a TAVL Node Step 4 - Rebalance
- rebalance for 0 balance factor after TAVL deletion in right subtree: TAVL Deletion Symmetric Case
- rebalance PAVL tree after insertion in left subtree: Rebalancing PAVL Trees
- rebalance PAVL tree after insertion in right subtree: PAVL Insertion Symmetric Case
- rebalance RTAVL tree after insertion to left: Rebalancing RTAVL Trees
- rebalance RTAVL tree after insertion to right: Rebalancing RTAVL Trees
- rebalance TAVL tree after insertion in left subtree: Rebalancing TAVL Trees
- rebalance TAVL tree after insertion in right subtree: TAVL Insertion Symmetric Case
- rebalance tree after PRB deletion: Deleting a PRB Node Step 3 - Rebalance
- rebalance tree after RB deletion: Deleting an RB Node Step 3 - Rebalance
- rebalance tree after TRB deletion: Deleting a TRB Node Step 3 - Rebalance
*recurse_verify_tree*function: Testing PRB Trees*recurse_verify_tree*function: Testing PAVL Trees*recurse_verify_tree*function: Testing PBSTs*recurse_verify_tree*function: Testing RTRB Trees*recurse_verify_tree*function: Testing RTAVL Trees*recurse_verify_tree*function: Testing RTBSTs*recurse_verify_tree*function: Testing TRB Trees*recurse_verify_tree*function: Testing TAVL Trees*recurse_verify_tree*function: Testing TBSTs*recurse_verify_tree*function: Testing RB Trees*recurse_verify_tree*function: Testing AVL Trees*recurse_verify_tree*function: BST Verification- recursive copy of BST, take 1: Copying a BST Recursively
- recursive copy of BST, take 2: Copying a BST Recursively
- recursive deallocation function: Answers for Chapter 4
- recursive insertion into AVL tree: Recursive Insertion
- recursive traversal of BST: Recursive Traversal of a BST
- recursive traversal of BST, using nested function: Answers for Chapter 4
- recursively verify AVL tree structure: Testing AVL Trees
- recursively verify BST structure: BST Verification
- recursively verify PAVL tree structure: Testing PAVL Trees
- recursively verify PBST structure: Testing PBSTs
- recursively verify PRB tree structure: Testing PRB Trees
- recursively verify RB tree structure: Testing RB Trees
- recursively verify RTAVL tree structure: Testing RTAVL Trees
- recursively verify RTBST structure: Testing RTBSTs
- recursively verify RTRB tree structure: Testing RTRB Trees
- recursively verify TAVL tree structure: Testing TAVL Trees
- recursively verify TBST structure: Testing TBSTs
- recursively verify TRB tree structure: Testing TRB Trees
- reduce TBST vine general case to special case: Transforming a Vine into a Balanced TBST
- reduce vine general case to special case: Balancing Implementation
*reject_request*function: Memory Manager- right-side rebalancing after initial-black RB insertion: Initial Black Insertion in an RB Tree
- right-side rebalancing after PRB deletion: PRB Deletion Symmetric Case
- right-side rebalancing after PRB insertion: PRB Insertion Symmetric Case
- right-side rebalancing after RB deletion: RB Deletion Symmetric Case
- right-side rebalancing after RB insertion: RB Insertion Symmetric Case
- right-side rebalancing after RTRB deletion: Deleting an RTRB Node Step 3 - Rebalance
- right-side rebalancing after RTRB insertion: Step 3 in RTRB Insertion
- right-side rebalancing after TRB deletion: TRB Deletion Symmetric Case
- right-side rebalancing after TRB insertion: TRB Insertion Symmetric Case
- right-side rebalancing case 1 in PAVL deletion: PAVL Deletion Symmetric Case
- right-side rebalancing case 2 in PAVL deletion: PAVL Deletion Symmetric Case
- robust recursive copy of BST, take 1: Answers for Chapter 4
- robust recursive copy of BST, take 2: Answers for Chapter 4
- robust recursive copy of BST, take 3: Answers for Chapter 4
- robust root insertion of existing node in arbitrary subtree: Answers for Chapter 4
- robustly move BST node to root: Answers for Chapter 4
- robustly search for insertion point in arbitrary subtree: Answers for Chapter 4
- root insertion of existing node in arbitrary subtree: Answers for Chapter 4
*root_insert*function: Answers for Chapter 4- rotate left at
*x*then right at*y*in AVL tree: Rebalancing AVL Trees - rotate left at
*y*in AVL tree: AVL Insertion Symmetric Case - rotate right at
*x*then left at*y*in AVL tree: AVL Insertion Symmetric Case - rotate right at
*y*in AVL tree: Rebalancing AVL Trees *rotate_left*function: Answers for Chapter 14*rotate_left*function: Answers for Chapter 11*rotate_left*function: Answers for Chapter 8*rotate_left*function: Answers for Chapter 4*rotate_right*function: Answers for Chapter 14*rotate_right*function: Answers for Chapter 11*rotate_right*function: Answers for Chapter 8*rotate_right*function: Answers for Chapter 4- RTAVL copy function: Copying an RTAVL Tree
- RTAVL functions: RTAVL Operations
- RTAVL item deletion function: Deleting from an RTAVL Tree
- RTAVL item insertion function: Inserting into an RTAVL Tree
- RTAVL node copy function: Copying an RTAVL Tree
- RTAVL node structure: RTAVL Data Types
`rtavl-test.c`: Testing RTAVL Trees`rtavl.c`: Right-Threaded AVL Trees`rtavl.h`: Right-Threaded AVL Trees*rtavl_delete*function: Deleting from an RTAVL Tree`RTAVL_H`macro: Right-Threaded AVL Trees*rtavl_node*structure: RTAVL Data Types*rtavl_probe*function: Inserting into an RTAVL Tree*rtavl_tag*enumeration: RTAVL Data Types- RTBST balance function: Balancing an RTBST
- RTBST copy error helper function: Copying an RTBST
- RTBST copy function: Copying an RTBST
- RTBST destruction function: Destroying an RTBST
- RTBST functions: RTBST Operations
- RTBST item deletion function: Deleting from an RTBST
- RTBST item insertion function: Inserting into an RTBST
- RTBST main copy function: Copying an RTBST
- RTBST node copy function: Copying an RTBST
- RTBST node structure: RTBST Data Types
- RTBST print function: Testing RTBSTs
- RTBST search function: Searching an RTBST
- RTBST traversal functions: Traversing an RTBST
- RTBST traverser advance function: RTBST Traverser Advancing
- RTBST traverser back up function: RTBST Traverser Retreating
- RTBST traverser first initializer: RTBST Traverser First Initialization
- RTBST traverser last initializer: RTBST Traverser Last Initialization
- RTBST traverser search initializer: RTBST Traverser Find Initialization
- RTBST tree-to-vine function: Balancing an RTBST
- RTBST vine compression function: Balancing an RTBST
`rtbst-test.c`: Testing RTBSTs`rtbst.c`: Right-Threaded Binary Search Trees`rtbst.h`: Right-Threaded Binary Search Trees*rtbst_copy*function: Copying an RTBST*rtbst_delete*function: Deleting from an RTBST*rtbst_destroy*function: Destroying an RTBST*rtbst_find*function: Searching an RTBST`RTBST_H`macro: Right-Threaded Binary Search Trees*rtbst_node*structure: RTBST Data Types*rtbst_probe*function: Inserting into an RTBST*rtbst_t_find*function: RTBST Traverser Find Initialization*rtbst_t_first*function: RTBST Traverser First Initialization*rtbst_t_last*function: RTBST Traverser Last Initialization*rtbst_t_next*function: RTBST Traverser Advancing*rtbst_t_prev*function: RTBST Traverser Retreating*rtbst_tag*enumeration: RTBST Data Types- RTRB functions: RTRB Operations
- RTRB item deletion function: Deleting from an RTRB Tree
- RTRB item insertion function: Inserting into an RTRB Tree
- RTRB node structure: RTRB Data Types
`rtrb-test.c`: Testing RTRB Trees`rtrb.c`: Right-Threaded Red-Black Trees`rtrb.h`: Right-Threaded Red-Black Trees*rtrb_color*enumeration: RTRB Data Types*rtrb_delete*function: Deleting from an RTRB Tree`RTRB_H`macro: Right-Threaded Red-Black Trees*rtrb_node*structure: RTRB Data Types*rtrb_probe*function: Inserting into an RTRB Tree*rtrb_tag*enumeration: RTRB Data Types- run search tests: Answers for Chapter 3
*s*variable: Answers for Chapter 11*s*variable: Answers for Chapter 9*s*variable: Answers for Chapter 5- search AVL tree for insertion point: Step 1 in AVL Insertion
- search AVL tree for item to delete: Deleting an AVL Node Step 1 - Search
- search BST for insertion point, root insertion version: Root Insertion in a BST
- search for insertion point in arbitrary subtree: Answers for Chapter 4
- search functions: Answers for Chapter 3
- search of binary search tree stored as array: Binary Search Tree in Array
- search PAVL tree for insertion point: Steps 1 and 2 in PAVL Insertion
- search PBST tree for insertion point: Inserting into a PBST
- search RB tree for insertion point: Inserting an RB Node Step 1 - Search
- search RTAVL tree for insertion point: Steps 1-1 in RTAVL Insertion
- search RTAVL tree for item to delete: Deleting a RTAVL Node Step 1 - Search
- search RTBST for insertion point: Inserting into an RTBST
- search RTRB tree for insertion point: Steps 1 and 2 in RTRB Insertion
- search TAVL tree for insertion point: Steps 1 and 2 in TAVL Insertion
- search TAVL tree for item to delete: Deleting a TAVL Node Step 1 - Search
- search TBST for insertion point: Inserting into a TBST
- search test functions: Answers for Chapter 3
- search test main program: Answers for Chapter 3
- search TRB tree for insertion point: Steps 1 and 2 in TRB Insertion
- search TRB tree for item to delete: Deleting a TRB Node Step 1 - Search
*search_func*structure: Answers for Chapter 3`seq-test.c`: Answers for Chapter 3- sequentially search a sorted array of
**int**s: Sequential Search of Ordered Array - sequentially search a sorted array of
**int**s using a sentinel: Sequential Search of Ordered Array with Sentinel - sequentially search a sorted array of
**int**s using a sentinel (2): Sequential Search of Ordered Array with Sentinel - sequentially search an array of
**int**s: Sequential Search - sequentially search an array of
**int**s using a sentinel: Sequential Search with Sentinel - set parents of main vine: Answers for Chapter 13
- show
`bin-ary-test`usage message: Answers for Chapter 3 `srch-test.c`: Answers for Chapter 3*start_timer*function: Answers for Chapter 3*stoi*function: Answers for Chapter 3*stoi*function: Command-Line Parser*stop_timer*function: Answers for Chapter 3- string to integer function
*stoi*(): Answers for Chapter 3 - summing string lengths with
*next_item*(): Improving Convenience - summing string lengths with
*walk*(): Improving Convenience - symmetric case in PAVL deletion: PAVL Deletion Symmetric Case
- symmetric case in TAVL deletion: TAVL Deletion Symmetric Case
- symmetric case in TAVL deletion, with stack: Answers for Chapter 8
- table assertion function control directives: Answers for Chapter 2
- table assertion function prototypes: Assertions
- table assertion functions: Answers for Chapter 2
- table count function prototype: Count
- table count macro: Answers for Chapter 2
- table creation function prototypes: Creation and Destruction
- table function prototypes: Table Headers
- table function types: Item and Copy Functions
- table function types: Comparison Function
- table insertion and deletion function prototypes: Insertion and Deletion
- table insertion convenience functions: Answers for Chapter 2
- table types: Table Headers
- TAVL copy function: Copying a TAVL Tree
- TAVL functions: TAVL Operations
- TAVL item deletion function: Deleting from a TAVL Tree
- TAVL item deletion function, with stack: Answers for Chapter 8
- TAVL item insertion function: Inserting into a TAVL Tree
- TAVL node copy function: Copying a TAVL Tree
- TAVL node structure: TAVL Data Types
`tavl-test.c`: Testing TAVL Trees`tavl.c`: Threaded AVL Trees`tavl.h`: Threaded AVL Trees*tavl_delete*function: Answers for Chapter 8*tavl_delete*function: Deleting from a TAVL Tree`TAVL_H`macro: Threaded AVL Trees*tavl_node*structure: TAVL Data Types*tavl_probe*function: Inserting into a TAVL Tree*tavl_tag*enumeration: TAVL Data Types*tbl_allocator_default*variable: Memory Allocation*tbl_assert_delete*function: Answers for Chapter 2*tbl_assert_delete*macro: Answers for Chapter 2*tbl_assert_insert*function: Answers for Chapter 2*tbl_assert_insert*macro: Answers for Chapter 2**tbl_comparison_func**type: Comparison Function**tbl_copy_func**type: Item and Copy Functions*tbl_count*macro: Answers for Chapter 2*tbl_free*function: Memory Allocation*tbl_insert*function: Answers for Chapter 2**tbl_item_func**type: Item and Copy Functions*tbl_malloc_abort*function: Answers for Chapter 2*tbl_replace*function: Answers for Chapter 2- TBST balance function: Balancing a TBST
- TBST copy error helper function: Copying a TBST
- TBST copy function: Copying a TBST
- TBST creation function: Creating a TBST
- TBST destruction function: Destroying a TBST
- TBST functions: TBST Operations
- TBST item deletion function: Deleting from a TBST
- TBST item insertion function: Inserting into a TBST
- TBST main balance function: Balancing a TBST
- TBST main copy function: Copying a TBST
- TBST node copy function: Copying a TBST
- TBST node structure: TBST Data Types
- TBST print function: Testing TBSTs
- TBST search function: Searching a TBST
- TBST table structure: TBST Data Types
- TBST test function: Testing TBSTs
- TBST traversal functions: Traversing a TBST
- TBST traverser advance function: TBST Traverser Advancing
- TBST traverser back up function: TBST Traverser Retreating
- TBST traverser copy initializer: TBST Traverser Copying
- TBST traverser first initializer: TBST Traverser First Initialization
- TBST traverser insertion initializer: TBST Traverser Insert Initialization
- TBST traverser last initializer: TBST Traverser Last Initialization
- TBST traverser null initializer: TBST Traverser Null Initialization
- TBST traverser search initializer: TBST Traverser Find Initialization
- TBST traverser structure: Traversing a TBST
- TBST tree-to-vine function: Transforming a TBST into a Vine
- TBST verify function: Testing TBSTs
- TBST vine compression function: Transforming a Vine into a Balanced TBST
- TBST vine-to-tree function: Transforming a Vine into a Balanced TBST
`tbst-test.c`: Testing TBSTs`tbst.c`: Threaded Binary Search Trees`tbst.h`: Threaded Binary Search Trees*tbst_balance*function: Balancing a TBST*tbst_copy*function: Copying a TBST*tbst_create*function: Creating a TBST*tbst_delete*function: Deleting from a TBST*tbst_destroy*function: Destroying a TBST*tbst_find*function: Searching a TBST`TBST_H`macro: Threaded Binary Search Trees*tbst_link*structure: Answers for Chapter 7*tbst_node*structure: Answers for Chapter 7*tbst_node*structure: TBST Data Types*tbst_probe*function: Inserting into a TBST*tbst_t_copy*function: TBST Traverser Copying*tbst_t_find*function: TBST Traverser Find Initialization*tbst_t_first*function: TBST Traverser First Initialization*tbst_t_init*function: TBST Traverser Null Initialization*tbst_t_insert*function: TBST Traverser Insert Initialization*tbst_t_last*function: TBST Traverser Last Initialization*tbst_t_next*function: TBST Traverser Advancing*tbst_t_prev*function: TBST Traverser Retreating*tbst_table*structure: Answers for Chapter 7*tbst_table*structure: TBST Data Types*tbst_tag*enumeration: TBST Data Types*tbst_traverser*structure: Traversing a TBST- test BST traversal during modifications: Testing BSTs
- test creating a BST and inserting into it: Testing BSTs
- test declarations: Main Program
- test declarations: User Interaction
- test declarations: Memory Manager
- test declarations: Test Set Generation
- test deleting from an empty tree: Testing BSTs
- test deleting nodes from the BST and making copies of it: Testing BSTs
- test destroying the tree: Testing BSTs
*test*enumeration: Main Program- test main program: Main Program
- test prototypes: Utility Functions
- test prototypes: Testing Overflow
- test prototypes: Testing BSTs
- test TBST balancing: Testing TBSTs
- test utility functions: Utility Functions
`test.c`: Testing BST Functions`test.h`: Testing BST Functions*test_bst_copy*function: Answers for Chapter 4*test_bst_t_find*function: Answers for Chapter 4*test_bst_t_first*function: Testing Overflow*test_bst_t_insert*function: Answers for Chapter 4*test_bst_t_last*function: Answers for Chapter 4*test_bst_t_next*function: Answers for Chapter 4*test_bst_t_prev*function: Answers for Chapter 4*test_correctness*function: Answers for Chapter 4*test_correctness*function: Testing TBSTs*test_correctness*function: Testing BSTs`TEST_H`macro: Testing BST Functions*test_options*enumeration: Main Program*test_overflow*function: Answers for Chapter 4*test_overflow*function: Testing Overflow*time_seed*function: Answers for Chapter 4*time_successful_search*function: Answers for Chapter 3*time_unsuccessful_search*function: Answers for Chapter 3- timer functions: Answers for Chapter 3
*total_length*function: Improving Convenience- transform left-side PRB deletion rebalancing case 3 into case 2: Deleting a PRB Node Step 3 - Rebalance
- transform left-side RB deletion rebalancing case 3 into case 2: Deleting an RB Node Step 3 - Rebalance
- transform left-side RTRB deletion rebalancing case 3 into case 2: Deleting an RTRB Node Step 3 - Rebalance
- transform left-side TRB deletion rebalancing case 3 into case 2: Deleting a TRB Node Step 3 - Rebalance
- transform right-side PRB deletion rebalancing case 3 into case 2: PRB Deletion Symmetric Case
- transform right-side RB deletion rebalancing case 3 into case 2: RB Deletion Symmetric Case
- transform right-side RTRB deletion rebalancing case 3 into case 2: Deleting an RTRB Node Step 3 - Rebalance
- transform right-side TRB deletion rebalancing case 3 into case 2: TRB Deletion Symmetric Case
*trav_refresh*function: Answers for Chapter 4*trav_refresh*function: Better Iterative Traversal*traverse_iterative*function: Answers for Chapter 4*traverse_iterative*function: Iterative Traversal of a BST*traverse_recursive*function: Recursive Traversal of a BST- traverser constructor function prototypes: Constructors
- traverser manipulator function prototypes: Manipulators
*traverser*structure: Improving Convenience- TRB functions: TRB Operations
- TRB item deletion function: Deleting from a TRB Tree
- TRB item deletion function, without stack: Answers for Chapter 9
- TRB item insertion function: Inserting into a TRB Tree
- TRB item insertion function, without stack: Answers for Chapter 9
- TRB node structure: TRB Data Types
`trb-test.c`: Testing TRB Trees`trb.c`: Threaded Red-Black Trees`trb.h`: Threaded Red-Black Trees*trb_color*enumeration: TRB Data Types*trb_delete*function: Answers for Chapter 9*trb_delete*function: Deleting from a TRB Tree`TRB_H`macro: Threaded Red-Black Trees*trb_node*structure: TRB Data Types*trb_probe*function: Answers for Chapter 9*trb_probe*function: Inserting into a TRB Tree*trb_tag*enumeration: TRB Data Types*tree_to_vine*function: Balancing an RTBST*tree_to_vine*function: Transforming a TBST into a Vine*tree_to_vine*function: Transforming a BST into a Vine- uniform binary search of ordered array: Answers for Chapter 3
- update balance factors after AVL insertion: Step 3 in AVL Insertion
- update balance factors after AVL insertion, with bitmasks: Answers for Chapter 5
- update balance factors after PAVL insertion: Step 3 in PAVL Insertion
- update balance factors and rebalance after AVL deletion: Deleting an AVL Node Step 3 - Update
- update balance factors and rebalance after PAVL deletion: Deleting a PAVL Node Step 3 - Update
- update balance factors and rebalance after RTAVL deletion: Deleting a RTAVL Node Step 3 - Update
- update balance factors and rebalance after TAVL deletion: Deleting a TAVL Node Step 3 - Update
- update balance factors and rebalance after TAVL deletion, with stack: Answers for Chapter 8
- update parent pointers function: Balancing a PBST
- update
*y*'s balance factor after left-side AVL deletion: Deleting an AVL Node Step 3 - Update - update
*y*'s balance factor after right-side AVL deletion: AVL Deletion Symmetric Case *update_parents*function: Balancing a PBST*usage*function: Answers for Chapter 3*usage*function: Command-Line Parser- usage printer for search test program: Answers for Chapter 3
- verify AVL node balance factor: Testing AVL Trees
- verify binary search tree ordering: BST Verification
- verify PBST node parent pointers: Testing PBSTs
- verify RB node color: Testing RB Trees
- verify RB node rule 1 compliance: Testing RB Trees
- verify RB node rule 2 compliance: Testing RB Trees
- verify RTRB node rule 1 compliance: Testing RTRB Trees
- verify TRB node rule 1 compliance: Testing TRB Trees
*verify_tree*function: Testing TBSTs*verify_tree*function: Testing RB Trees*verify_tree*function: Testing AVL Trees*verify_tree*function: BST Verification- vine to balanced BST function: Balancing Implementation
- vine to balanced PBST function: Balancing a PBST
- vine to balanced PBST function, with parent updates: Answers for Chapter 13
*vine_to_tree*function: Answers for Chapter 13*vine_to_tree*function: Balancing a PBST*vine_to_tree*function: Transforming a Vine into a Balanced TBST*walk*function: Answers for Chapter 4*walk*function: Recursive Traversal of a BST*xmalloc*function: Utility Functions