AA树

平衡一颗红黑树需要记录其颜色，而AA树是在每个节点记录其"level"这相当于红黑树节点的黑高度

1. 所有叶节点的level都是1
2. 每个左孩子的level恰好为其父亲的level减一
3. 每个右孩子的level等于其父亲的level或为其父亲的level减一
4. 每个右孙子的level严格小于其祖父节点的level
5. 每一个level大于1的节点有两个子节点

两个level相同的点之间的边水平边，也就是红黑树上的红边。往右的水平边是允许的，但不可连续(红黑树性质)；不能有向左的水平边(AA树性质)。因为AA树的条件比红黑树严格，所以重新平衡一颗AA树会比重新平衡一颗红黑树容易。

插入和删除会让AA树变的不平衡(即违反它的性质)。恢复平衡只需两种操作:"skew"和"split". Skew是一个右旋转使得子树中向左的水平边变成向右的水平边；Split是一个左旋并增加子树根节点的level(请看范例)使得连续向右的水平边消失。平衡插入和删除操作的实现是由skew及split决定是否旋转，而不是在主程序中判断。

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

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:

在递归的实做中，除了叶节点之外，在每次的递归结束后调用skew和split即可

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

在大部分的二元搜索树，删除一个内部节点可以转换成交换内部节点及其最接近的前驱或后继节点，这取决于用户。 为了平衡这颗树，有几中方法，Andersson教授描述的original paper（页面存档备份，存于）是最基本的，尽管它还能再被优化。删除后第一件事是降低其level(如果可以)，于是，整个level必须skew和split，这个方法最受到欢迎的，因为它的概念易懂，可以枚举成下列三个简单步骤:

1. 如果可以的话，减少其level
2. Skew其level.
3. Split其level.

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

这个网站展示了良好的删除示范Andersson paper（页面存档备份，存于）.

AA树的性能和红黑树是很类似的。尽管AA树比红黑树做较多次旋转，却较容易实做，故二者性能相似。但是AA树高度较浅，故查找时间较快[1]

• 红黑树
• B树
• AVL树
• 左倾红黑树

• A. Andersson. Balanced search trees made simple（页面存档备份，存于）
• A. Andersson. A note on searching in a binary search tree（页面存档备份，存于）
• AA-Tree Applet（页面存档备份，存于） by Kubo Kovac
• BSTlib - 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 example C implementation
• An Objective-C implementation（页面存档备份，存于）