[科普中国]-AA树

AA树（AA-Tree）是计算机科学中数据结构的一种，属于自平衡二叉查找树（Self-balancing binary search tree），是红黑树的变种。1

简介AA树是Arne Andersson教授在1993年在他的论文"Balanced search trees made simple"中介绍，设计的目的是减少红黑树考虑的不同情况。区别于红黑树的是，AA树的红结点只能作为右叶子。另外AA树为实现方便，不再使用红黑两种颜色，而是用level标记结点，结点中的level相当于红黑树中结点的黑高度。AA树可以在O(log n)的时间内做查找，插入和删除，这里的n是树中元素的数目。

性能分析从实现角度看，AA树减少了红黑树插入删除考虑的情况；

AA树属于红黑树，时间复杂度和红黑树相同，即O(logn)，但是旋转次数相对较多。

level的规定满足以下5个条件

1、每个叶子的level是1；

2、每个左孩子的level是其父结点的level减1；

3、每个右孩子的level等于其父结点的level或等于其父结点的level减1；

4、每个右孙子的level一定比其祖父的level小；

5、每个level大于1的结点有两个孩子。

平衡旋转左旋出现连续向右的水平方向链（连续三个向右的孩子属于同一level）

向左旋转：

把小于等于此level的结点看做一个子树

子树的根的右孩子变为新的子树根；

原来的子树根变为新子树根的左孩子；

新的子树根level+1。

右旋出现连续向右的水平方向链（连续两个向左的孩子属于同一level）

向右旋转：

把小于等于此level的结点看做一个子树；

子树的根的左孩子变为新的子树根；

原来的子树根变为新子树根的右孩子。

插入结点插入结点方法和二叉查找树相同，每次插入值都需要检查是否需要进行平衡旋转。每当出现连续的水平方向链，就进行平衡旋转。1

**注意：**插入结点时level等于其父结点的level，只有当树进行旋转操作时才会改变结点的level值。

删除结点删除结点按后继结点右孩子的值赋给后继结点。1

情况1：

如果后继结点不是叶子，后继结点右孩子的值赋给后继结点，最后删除后继的右孩子。

情况2：

如果后继结点是叶子，后继结点父亲的level减1，如果出现向左或连续向右的水平链，进行右旋或者左旋，最后删除后继结点。

Java代码在java中定义AA树的方法

publicclassAATree{ publicAATree(){ root=nullNode; }publicvoidinsert(Comparablex){ root=insert(x,root); }publicvoidremove(Comparablex){ deletedNode=nullNode;root=remove(x,root); } publicComparablefind(Comparablex){ AANodecurrent=root; nullNode.element=x; for(;;){ if(x.compareTo(current.element)0) current=current.right; elseif(current!=nullNode)returncurrent.element; elsereturnnull;}}}本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所