AA树

AA 树在计算机科学一种形式的自平衡二叉查找树用于高效存储和检索序数据。 AA 树的名称是由它的发明者Arne Andersson而来。
AA树是红黑树的一种变种，是Arne Andersson教授在1993年年在他的论文"Balanced search trees made simple"中介绍，设计的目的是减少红黑树考虑的不同情况，区别于红黑树的是，AA树的红节点只能作为右叶子。换句话说，没有红节点可以是一个左子儿。这导致代替2-3-4树，从而大大简化了维护2-3树的模拟。维护红黑树的平衡需要考虑7种不同的情况:
因为AA树有严格的条件(红节点只能为右节点)，故只需考虑2种情形:

插入

在递回的实做中，除了叶节点之外，在每次的递回结束后呼叫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 Tend function

效能

AA树的性能和红黑树是很类似的(其实很慢)。因为AA树比红黑树做较多次旋转，所以较容易实做。虽然红黑树效能较为平均，但是AA树高度较浅故查找时间较快