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 ints: 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 ints: Sequential Search of Ordered Array
• sequentially search a sorted array of ints using a sentinel: Sequential Search of Ordered Array with Sentinel
• sequentially search a sorted array of ints using a sentinel (2): Sequential Search of Ordered Array with Sentinel
• sequentially search an array of ints: Sequential Search
• sequentially search an array of ints 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