Binary Search Trees

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.

Ordered Binary Tree

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.
TreeUtils.h

http://en.wikipedia.org/wiki/Ordered_tree_data_structure

AA Tree (Anderson tree)

An Anderson tree implementation.
AATreeUtils.h

http://en.wikipedia.org/wiki/AA_tree

AVL Tree

An AVL tree implementation.
AVLTreeUtils.h

http://en.wikipedia.org/wiki/AVL_tree

Red-Black Tree

An Red-Black tree implementation. Quite nasty deletion though, needs a rewrite.
RedBlackTreeUtils.h

http://en.wikipedia.org/wiki/Red-black_tree

Splay Tree

A splay-tree implementation.
SplayTreeUtils.h

http://en.wikipedia.org/wiki/Splay_tree

Scapegoat Tree

A scapegoat-tree implementation.
ScapegoatTreeUtils.h

http://en.wikipedia.org/wiki/Scapegoat_tree