编辑“︁AA树”︁（章节）

== 旋轉平衡 ==

平衡一顆[[紅黑樹]]需要記錄其顏色，而AA樹是在每個節點記錄其"level"這相當於紅黑樹節點的黑高度

# 所有葉節點的level都是1
# 每個左孩子的level恰好為其父親的level減一
# 每個右孩子的level等於其父親的level或為其父親的level減一
# 每個右孫子的level嚴格小於其祖父節點的level
# 每一個level大於1的節點有兩個子節點

兩個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: [[Image:AA Tree Skew2.svg]]

 '''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: [[Image:AA Tree Split2.svg]]