Introduction to AA trees

AA trees were introduced by Arne Andersson in 1993 and hence the name AA. They are a type of balanced binary search trees. It was developed as a simpler alternative to red black trees.

It eliminates many of the conditions that need to be considered to maintain a red-black tree.

To understand AA trees, it is important to have a clear understanding of the concepts of a red black tree.

The tree below is an example of a red-black tree:

Properties of a red-black tree

Every node is either red or bl...