Appendix E Catalogue of Algorithms

This appendix lists all of the algorithms described and implemented in this book, along with page number references. Each algorithm is listed under the least-specific type of tree to which it applies, which is not always the same as the place where it is introduced. For instance, rotations on threaded trees can be used in any threaded tree, so they appear under “Threaded Binary Search Tree Algorithms”, despite their formal introduction later within the threaded AVL tree chapter.

Sometimes multiple algorithms for accomplishing the same task are listed. In this case, the different algorithms are qualified by a few descriptive words. For the algorithm used in libavl, the description is enclosed by parentheses, and the description of each alternative algorithm is set off by a comma.

### Binary Search Tree Algorithms

Backing up a traverser:

Balancing:

Copying (iterative; robust):

Copying, iterative:

Copying, recursive:

Copying, recursive; robust, version 1:

Copying, recursive; robust, version 2:

Copying, recursive; robust, version 3:

Creation:

Deletion (iterative):

Deletion, by merging:

Deletion, special case for no left child:

Deletion, with data modification:

Destruction (by rotation):

Destruction, iterative:

Destruction, recursive:

Getting the current item in a traverser:

Initialization of traverser as copy:

Initialization of traverser to found item:

Initialization of traverser to greatest item:

Initialization of traverser to inserted item:

Initialization of traverser to least item:

Initialization of traverser to null item:

Insertion (iterative):

Insertion, as root:

Insertion, as root, of existing node in arbitrary subtree:

Insertion, as root, of existing node in arbitrary subtree, robustly:

Insertion, using pointer to pointer:

Join, iterative:

Join, recursive:

Refreshing of a traverser (general):

Refreshing of a traverser, optimized:

Replacing the current item in a traverser:

Rotation, left:

Rotation, left double:

Rotation, right:

Rotation, right double:

Search:

Traversal (iterative; convenient, reliable):

Traversal, iterative:

Traversal, iterative; convenient:

Traversal, iterative; convenient, reliable:

Traversal, iterative; with dynamic stack:

Traversal, level order:

Traversal, recursive:

Traversal, recursive; with nested function:

Vine compression:

Vine from tree:

Vine to balanced tree:

### AVL Tree Algorithms

Backing up a traverser:

Copying (iterative):

Deletion (iterative):

Deletion, with data modification:

Initialization of traverser to found item:

Initialization of traverser to greatest item:

Initialization of traverser to inserted item:

Initialization of traverser to least item:

Insertion (iterative):

Insertion, recursive:

### Red-Black Tree Algorithms

Deletion (iterative):

Deletion, with data modification:

Insertion (iterative):

Insertion, initial black:

### Threaded Binary Search Tree Algorithms

Backing up a traverser:

Balancing:

Copying:

Copying a node:

Creation:

Deletion (parent tracking):

Deletion, with data modification:

Deletion, with parent node algorithm:

Destruction:

Initialization of traverser as copy:

Initialization of traverser to found item:

Initialization of traverser to greatest item:

Initialization of traverser to inserted item:

Initialization of traverser to least item:

Initialization of traverser to null item:

Insertion:

Parent of a node:

Rotation, left:

Rotation, right:

Search:

Vine compression:

Vine from tree:

Vine to balanced tree:

Copying a node:

Deletion (without stack):

Deletion, with data modification:

Deletion, with stack:

Insertion:

Rotation, left double, version 1:

Rotation, left double, version 2:

Rotation, right double:

Deletion (with stack):

Deletion, with data modification:

Deletion, without stack:

Insertion (with stack):

Insertion, without stack:

### Right-Threaded Binary Search Tree Algorithms

Backing up a traverser:

Balancing:

Copying:

Copying a node:

Deletion (left-looking):

Deletion, right-looking:

Deletion, with data modification, left-looking:

Deletion, with data modification, right-looking:

Destruction:

Initialization of traverser to found item:

Initialization of traverser to greatest item:

Initialization of traverser to least item:

Insertion:

Rotation, left:

Rotation, right:

Search:

Vine compression:

Vine from tree:

Copying:

Copying a node:

Deletion (left-looking):

Deletion, right-looking:

Deletion, with data modification:

Insertion:

Deletion:

Insertion:

### Binary Search Tree with Parent Pointers Algorithms

Backing up a traverser:

Copying:

Deletion:

Initialization of traverser to found item:

Initialization of traverser to greatest item:

Initialization of traverser to inserted item:

Initialization of traverser to least item:

Insertion:

Rotation, left:

Rotation, right:

Update parent pointers:

Vine to balanced tree (without parent updates):

Vine to balanced tree, with parent updates:

Copying:

Deletion:

Insertion:

Deletion:

Insertion: