AA树在计算机科学一种形式的自平衡二叉查找树用于高效存储和检索序数据。AA树的名称是由它的发明者阿尔尼·安德森(Arne Andersson)而来。
AA树是红黑树的一种变种,是安德森教授在1993年年在他的论文《Balanced search trees made simple》中介绍,设计的目的是减少红黑树考虑的不同情况,区别于红黑树的是,AA树的红节点只能作为右叶子,从而大大简化了维护2-3树的模拟。维护红黑树的平衡需要考虑7种不同的情况:
因为AA树有严格的条件(红节点只能为右节点),故只需考虑2种情形: