AA树在电脑科学一种形式的自平衡二元搜寻树用于高效存储和检索序数据。AA树的名称是由它的发明者阿尔尼·安德森（Arne Andersson）而来。 AA树是红黑树的一种变种，是安德森教授在1993年年在他的论文《Balanced search trees made simple》中介绍，设计的目的是减少红黑树考虑的不同情况，区别于红黑树的是，AA树的红节点只能作为右叶子，从而大大简化了维护2-3树的模拟。维护红黑树的平衡需要考虑7种不同的情况: 因为AA树有严格的条件(红节点只能为右节点)，故只需考虑2种情形: 旋转平衡. 平衡一颗红黑树需要记录其颜色，而AA树是在每个节点记录其"level"这相当于红黑树节点的黑高度 两个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 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，这个方法最受到欢迎的，因为它的概念易懂，可以列举成下列三个简单步骤: 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树高度较浅，故查找时间较快