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:
“A revolution is not the overturning of a cart, a reshuffling in the cards of state. It is a process, a swelling, a new growth in the race. If it is real, not simply a trauma, it is another ring in the tree of history, layer upon layer of invisible tissue composing the evidence of a circle.”
—Kate Millett (b. 1934)