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:
“The pine tree seems to listen, the fir tree seems to wait, and neither with impatience:Mthey give no thought to the little people below them whose impatience and curiosity eat them up alive.”
—Friedrich Nietzsche (1844–1900)