Home > Trees > IBinaryTree > ScapegoatTree

A ScapegoatTree is a BinaryTree implementation which implements the standard Scapegoat Tree data structure. This is a self balancing binary tree that providers amortized O(log n) performance, what this means is that most operations run in O(log n) time but that occasional operations run in O(n) time. This is due to the balancing algorithm that scapegoat trees use, the algorithm means they have to perform balances less often but that they are more costly when they do occur.

As with all our examples we assume a tree mapping from strings to integers for simplicity.

A ScapegoatTree can be created in several ways like so:

//Use the default comparer for the key type
ScapegoatTree<String, int> tree = new ScapegoatTree<String, int>();

//Use a custom comparer for the key type
tree = new ScapegoatTree<String, int>(StringComparer.OrdinalIgnoreCase);

//Use a custom balance factor for the tree
//Must meet condition 0.5 < factor < 1.0
tree = new ScapegoatTree<String, int>(0.8d);

//Use a custom comparer and balance factor
tree = new ScapegoatTree<String, int>(StringComparer.Ordinal, 0.9d);

The balance factor affects how often the tree is rebalanced, a high value (closer to 1.0) results in fewer balances so inserts are quicker but lookups and deletes are slower. A lower value (closer to 0.5) results in more balances so inserts are slower but lookups and deletes are quicker.

The default factor used is 0.75 which provides a balance of performance between the two.

All other operations use the standard ITree interface.