An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named for Arne Andersson, their inventor.
AA trees are a variation of the red-black tree, which in turn is an enhancement to the binary search tree. Unlike red-black trees, red nodes on an AA tree can only be added as a right subchild. In other words, no red node can be a left sub-child. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which greatly simplifies the maintenance operations. The maintenance algorithms for a red-black tree need to consider seven different shapes to properly balance the tree:
An AA tree on the other hand only needs to consider two shapes due to the strict requirement that only right links can be red:
Read more about AA Tree: Balancing Rotations, Insertion, Deletion, Performance
Famous quotes containing the word tree:
“There was not a tree as far as we could see, and that was many miles each way, the general level of the upland being about the same everywhere. Even from the Atlantic side we overlooked the Bay, and saw to Manomet Point in Plymouth, and better from that side because it was the highest.”
—Henry David Thoreau (1817–1862)