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 after their originator, Swedish computer scientist Arne Andersson. AA trees are a variation of the red–black tree, a form of binary search tree which supports efficient addition and deletion of entries. 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:

An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named after their originator, Swedish computer scientist Arne Andersson. AA trees are a variation of the red–black tree, a form of binary search tree which supports efficient addition and deletion of entries. 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: else if level(left(T)) == level(T) then Swap the pointers of horizontal left links. L = left(T) left(T) := right(L) right(L) := T return L else return T end if end function Skew: function split is input: T, a node representing an AA tree that needs to be rebalanced. output: Another node representing the rebalanced AA tree. if nil(T) then return Nil else if nil(right(T)) or nil(right(right(T))) then return T else if level(T) == level(right(right(T))) then We have two horizontal right links. Take the middle node, elevate it, and return it. R = right(T) right(T) := left(R) left(R) := T level(R) := level(R) + 1 return R else return T end if end function Split: left(T) := insert(X, left(T)) else if X > value(T) then right(T) := insert(X, right(T)) end if Note that the case of X == value(T) is unspecified. As given, an insert will have no effect. The implementor may desire different behavior. Perform skew and then split. The conditionals that determine whether or not a rotation will occur or not are inside of the procedures, as given above. T := skew(T) T := split(T) return T end function right(T) := delete(X, right(T)) else if X < value(T) then left(T) := delete(X, left(T)) else If we're a leaf, easy, otherwise reduce to leaf case. if leaf(T) then return right(T) else if nil(left(T)) then L := successor(T) right(T) := delete(value(L), right(T)) value(T) := value(L) else L := predecessor(T) left(T) := delete(value(L), left(T)) value(T) := value(L) end if end if Rebalance the tree. Decrease the level of all nodes in this level if necessary, and then skew and split all nodes in the new level. T := decrease_level(T) T := skew(T) right(T) := skew(right(T)) if not nil(right(T)) right(right(T)) := skew(right(right(T))) end if T := split(T) right(T) := split(right(T)) return T end function function decrease_level is input: T, a tree for which we want to remove links that skip levels. output: T with its level decreased. should_be = min(level(left(T)), level(right(T))) + 1 if should_be < level(T) then level(T) := should_be if should_be < level(right(T)) then level(right(T)) := should_be end if end if return T end function A good example of deletion by this algorithm is present in the Andersson paper.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1290444271 under CC BY-SA 4.0; modifications have been made.