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. Performance The performance of an AA tree is equivalent to the performance of a red–black tree. While an AA tree makes more rotations than a red–black tree, the simpler algorithms tend to be faster, and all of this balances out to result in similar performance. A red–black tree is more consistent in its performance than an AA tree, but an AA tree tends to be flatter, which results in slightly faster search times. See also Red–black tree B-tree AVL tree Scapegoat tree References External links A. Andersson. Balanced search trees made simple A. Andersson. A note on searching in a binary search tree BSTlib – an open source AA tree library for C by trijezdci AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures Thorough tutorial Julienne Walker with lots of code, including a practical implementation Object Oriented implementation with tests A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67–75) – comparison of AA trees, red–black trees, treaps, skip lists, and radix trees An Objective-C implementation Python implementation Search trees