Data Structure - AA Tree
AA Tree is a form of a balanced tree used for storing and retrieving ordered data efficiently.
It supports the following operation: addition, deletion, searching and enumerating entries in a defined order.
An ordering operator for entries is required.
AA Tree was invented by Arne Andersson in order to simplify the implementation of operations
in comparison to a more traditional Red-Black and AVL trees found in many libraries. See links below.
AA Tree can be used to implement useful collections: Set, Dictionary, Immutable List, etc.
This picture illustrates the effect of an addition of the item to the AA Tree that causes tree rebalance.
C# implementation - Open on Github
AATree<TEntry> requires a comparer implementation to perform key comparisons.
You can specify an implementation of the IComparer<T> generic interface by using a
constructor that accepts a comparer parameter; if you do not specify an implementation,
the default genericcomparer Comparer<T>.Default is used.
If type TEntry implements the System.IComparable<T> generic interface, the default comparer
uses that implementation.
The foreach statement of the C# language returns entries ordered by key.