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 is hardly an American male of my generation who has not at one time or another tried to master the victory cry of the great ape as it issued from the androgynous chest of Johnny Weissmuller, to the accompaniment of thousands of arms and legs snapping during attempts to swing from tree to tree in the backyards of the Republic.”
—Gore Vidal (b. 1925)