Trees

Trees comprise of a series of linked nodes that form a hierarchy.

In the ITree interface nodes constitute key-value pairs.

Keys support a total-ordering, enabling a rich API:

• Get, Put, Delete - Fetch, place and delete key-value pairs from the tree respectively
• Pairs - iterate through the key-value pairs of the tree inorder
• Min, Max- return the extreme keys from the tree
• Ceiling and Floor operations

Two implementations are available:

Implementation	Performance	Std. lib equivalent
BinarySearchTree	Logarithmic *	None
RedBlackTree	Logarithmic	SortedDictionary

A BinarySearchTree is a binary tree in symmetric order.

To be performant binary search trees require the client to enter keys in random order. This is rarely possible in practice so it is advised to use the RedBlackTree instead.

The RedBlackTree offers a way of representing a 2-3 tree, which is an extension of a binary search tree that allows nodes to support two keys and three children. 2-3 trees maintain perfect balance and symmetric order.

One other data structure that could be explored is the BTree.