AA樹（AA-Tree）是計(jì)算機(jī)科學(xué)中數(shù)據(jù)結(jié)構(gòu)的一種，屬于自平衡二叉查找樹（Self-balancing binary search tree），是紅黑樹的變種。

外文名

AA-Tree

領(lǐng)域

數(shù)據(jù)結(jié)構(gòu)

學(xué)科

計(jì)算機(jī)

簡介

AA樹是Arne Andersson教授在1993年在他的論文"Balanced search trees made simple"中介紹，設(shè)計(jì)的目的是減少紅黑樹考慮的不同情況。區(qū)別于紅黑樹的是，AA樹的紅結(jié)點(diǎn)只能作為右葉子。另外AA樹為實(shí)現(xiàn)方便，不再使用紅黑兩種顏色，而是用level標(biāo)記結(jié)點(diǎn)，結(jié)點(diǎn)中的level相當(dāng)于紅黑樹中結(jié)點(diǎn)的黑高度。AA樹可以在O(log n)的時(shí)間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。

性能分析

從實(shí)現(xiàn)角度看，AA樹減少了紅黑樹插入刪除考慮的情況

AA樹屬于紅黑樹，時(shí)間復(fù)雜度和紅黑樹相同，即O(logn)，但是旋轉(zhuǎn)次數(shù)相對較多;

level算法

level的規(guī)定滿足以下5個條件

1、每個葉子的level是1

2、每個左孩子的level是其父結(jié)點(diǎn)的level減1

3、每個右孩子的level等于其父結(jié)點(diǎn)的level或等于其父結(jié)點(diǎn)的level減1

4、每個右孫子的level一定比其祖父的level小

5、每個level大于1的結(jié)點(diǎn)有兩個孩子

平衡旋轉(zhuǎn)

左旋

AA樹

出現(xiàn)連續(xù)向右的水平方向鏈（連續(xù)三個向右的孩子屬于同一level）

向左旋轉(zhuǎn)：

把小于等于此level的結(jié)點(diǎn)看做一個子樹

  1. 子樹的根的右孩子變?yōu)樾碌淖訕涓?/li>
  2. 原來的子樹根變?yōu)樾伦訕涓淖蠛⒆?/li>
  3. 新的子樹根level+1
右旋

出現(xiàn)連續(xù)向右的水平方向鏈（連續(xù)兩個向左的孩子屬于同一level）

向右旋轉(zhuǎn)：

把小于等于此level的結(jié)點(diǎn)看做一個子樹

  1. 子樹的根的左孩子變?yōu)樾碌淖訕涓?/li>
  2. 原來的子樹根變?yōu)樾伦訕涓挠液⒆?/li>

插入結(jié)點(diǎn)

插入結(jié)點(diǎn)方法和二叉查找樹相同，每次插入值都需要檢查是否需要進(jìn)行平衡旋轉(zhuǎn)。每當(dāng)出現(xiàn)連續(xù)的水平方向鏈，就進(jìn)行平衡旋轉(zhuǎn)。

注意：

插入結(jié)點(diǎn)時(shí)level等于其父結(jié)點(diǎn)的level，只有當(dāng)樹進(jìn)行旋轉(zhuǎn)操作時(shí)才會改變結(jié)點(diǎn)的level值。

刪除結(jié)點(diǎn)

刪除結(jié)點(diǎn)按后繼結(jié)點(diǎn)右孩子的值賦給后繼結(jié)點(diǎn)。

情況1：

如果后繼結(jié)點(diǎn)不是葉子，后繼結(jié)點(diǎn)右孩子的值賦給后繼結(jié)點(diǎn)，最后刪除后繼的右孩子。

情況2：

如果后繼結(jié)點(diǎn)是葉子，后繼結(jié)點(diǎn)父親的level減1，如果出現(xiàn)向左或連續(xù)向右的水平鏈，進(jìn)行右旋或者左旋，最后刪除后繼結(jié)點(diǎn)。

Java代碼

在java中定義AA樹的方法

public class AATree {　? ? public AATree( ) {　? ?? ???root = nullNode;　? ? }? ? public void insert( Comparable x ) {? ? 　root = insert( x, root );　? ? }? ? public void remove( Comparable x ) {　? ?? ???deletedNode = nullNode;? ?? ???root = remove( x, root );　}　public Comparable find( Comparable x ) {　? ?? ???AANode current = root;? ? 　nullNode.element = x;? ? 　for( ; ; ) {　? ?? ?? ?? ?if( x.compareTo( current.element ) < 0 )　? ?? ?? ?? ?? ? current = current.left;　? ?? ?? ?? ?else if( x.compareTo( current.element ) > 0 )　? ?? ?? ?? ?? ? current = current.right;　? ?? ?? ?? ?else if( current != nullNode )? ?? ?? ?? ?? ? return current.element;? ?? ???　else? ?? ?? ?? ?? ? return null;? ?? ???}? ? }}