Data Structure - AA Tree

Introduction

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 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 the addition of the item to the AA Tree that causes a tree to rebalance.

Implementation

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.

Problems

• Sequential prefix function - an immutable version of AA Tree can be used for this problem.

Links

• Arne Andersson Balanced Search Trees Made Simple
• AA Tree on Wikipedia
• STL's Red-Black Trees
• Immutable collections in .NET