Appendix F 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

Advancing a traverser:

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

Advancing a traverser:

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:

Insertion, with bitmask:

Red-Black Tree Algorithms

Deletion (iterative):

Deletion, with data modification:

Insertion (iterative):

Insertion, initial black:

Threaded Binary Search Tree Algorithms

Advancing a traverser:

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:

Threaded AVL Tree Algorithms

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:

Threaded Red-Black Tree Algorithms

Deletion (with stack):

Deletion, with data modification:

Deletion, without stack:

Insertion (with stack):

Insertion, without stack:

Right-Threaded Binary Search Tree Algorithms

Advancing a traverser:

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:

Right-Threaded AVL Tree Algorithms

Copying:

Copying a node:

Deletion (left-looking):

Deletion, right-looking:

Deletion, with data modification:

Insertion:

Right-Threaded Red-Black Tree Algorithms

Deletion:

Insertion:

Binary Search Tree with Parent Pointers Algorithms

Advancing a traverser:

Backing up a traverser:

Balancing (with later parent updates):

Balancing, with integrated parent updates:

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 compression (with parent updates):

Vine to balanced tree (without parent updates):

Vine to balanced tree, with parent updates:

AVL Tree with Parent Pointers Algorithms

Copying:

Deletion:

Insertion:

Red-Black Tree with Parent Pointers Algorithms

Deletion:

Insertion:

Chapter 14

Table of Contents

Appendix G Index