by Malcolm Phillips
There are various types of binary trees that are useful for searching, including self-balancing trees. Below is some basic code for various binary-tree algorithms. These are required to use algorithms such as AVLTreeSort. The files also contain other useful things like, algorithms for removal, find, find min, find max, verify (check ordering etc), item counting, merging two trees, partitioning a tree into two trees, inorder-process, etc.
Just a standard ordered binary search tree. Can be used as a randomised
binary search tree if you shuffle all the items before inserting them.
An Anderson tree implementation.
An AVL tree implementation.
An Red-Black tree implementation. Quite nasty deletion though, needs a
A splay-tree implementation.
A scapegoat-tree implementation.