基本介紹
- 中文名：AA樹
- 外文名：AA-Tree
- 學科：計算機
- 屬於：自平衡二叉查找樹
- 領域：數據結構
- 提出者：Arne Andersson教授
簡介,性能分析,平衡旋轉,左旋,右旋,插入結點,刪除結點,Java代碼,
簡介
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的結點看做一個子樹；
- 子樹的根的左孩子變為新的子樹根；
- 原來的子樹根變為新子樹根的右孩子。
插入結點
插入結點方法和二叉查找樹相同，每次插入值都需要檢查是否需要進行平衡旋轉。每當出現連續的水平方向鏈，就進行平衡旋轉。
注意：插入結點時level等於其父結點的level，只有當樹進行旋轉操作時才會改變結點的level值。
刪除結點
刪除結點按後繼結點右孩子的值賦給後繼結點。
情況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.left; elseif(x.compareTo(current.element)>0) current=current.right; elseif(current!=nullNode)returncurrent.element; elsereturnnull;}}}