# AA树

## 旋轉平衡

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

```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:

```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:

## 插入

```function insert is
input: X, the value to be inserted, and T, the root of the tree to insert it into.
output: A balanced version T including X.

Do the normal binary tree insertion procedure. Set the result of the
recursive call to the correct child in case a new node was created or the
root of the subtree changes.
if nil(T) then
Create a new leaf node with X.
return node(X, 1, Nil, Nil)
else if X < value(T) then
left(T) := insert(X, left(T))
else if X > value(T) then
right(T) := insert(X, right(T))
end if
Note that the case of X == value(T) is unspecified. As given, an insert
will have no effect. The implementor may desire different behavior.

Perform skew and then split. The conditionals that determine whether or
not a rotation will occur or not are inside of the procedures, as given
above.
T := skew(T)
T := split(T)

return T
end function
```

## 刪除

1. 如果可以的話，減少其level
2. Skew其level.
3. Split其level.
```function delete is
input: X, the value to delete, and T, the root of the tree from which it should be deleted.
output: T, balanced, without the value X.

if nil(T) then
return T
else if X > value(T) then
right(T) := delete(X, right(T))
else if X < value(T) then
left(T) := delete(X, left(T))
else
If we're a leaf, easy, otherwise reduce to leaf case.
if leaf(T) then
return Nil
else if nil(left(T)) then
L := successor(T)
right(T) := delete(value(L), right(T))
value(T) := value(L)
else
L := predecessor(T)
left(T) := delete(value(L), left(T))
value(T) := value(L)
end if
end if

Rebalance the tree. Decrease the level of all nodes in this level if
necessary, and then skew and split all nodes in the new level.
T := decrease_level(T)
T := skew(T)
right(T) := skew(right(T))
if not nil(right(T))
right(right(T)) := skew(right(right(T)))
end if
T := split(T)
right(T) := split(right(T))
return T
end function
```
```function decrease_level is
input: T, a tree for which we want to remove links that skip levels.
output: T with its level decreased.

should_be = min(level(left(T)), level(right(T))) + 1
if should_be < level(T) then
level(T) := should_be
if should_be < level(right(T)) then
level(right(T)) := should_be
end if
end if
return T
end function
```

## 效能

AA樹的性能和紅黑樹是很類似的。儘管AA樹比紅黑樹做較多次旋轉，卻較容易實做，故二者效能相似。但是AA樹高度較淺，故查找時間較快[1]