AA Tree

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 tree the tempest with a crash of wood
    Throws down in front of us is not to bar
    Our passage to our journey’s end for good,
    But just to ask us who we think we are....
    Robert Frost (1874–1963)