AA Tree

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

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

Links

Last updated: 28.10.2017,
created: 24.09.2017.