درخت آآ

 '''function''' skew '''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(left(T)) '''then'''
         '''return''' T
     '''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'''

 '''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'''

 '''function''' insert '''is'''
     '''input:''' X, the value to be inserted, and T, the root of the tree to insert it into.
     '''output:''' A balanced version T including X.

     ''Do the normal binary tree insertion procedure. Set the result of the''
     ''recursive call to the correct child in case a new node was created or the''
     ''root of the subtree changes. ''
     '''if''' nil(T) '''then'''
         ''Create a new leaf node with X. ''
         '''return''' node(X, 1, Nil, Nil)
     '''else if''' X < value(T) '''then'''
         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'''

 '''function''' delete '''is'''
     '''input:''' X, the value to delete, and T, the root of the tree from which it should be deleted.
     '''output:''' T, balanced, without the value X.

     '''if''' nil(T) '''then'''
         return T
     '''else if''' X > value(T) '''then'''
         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 Nil
         '''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'''