AA树
AA
AA
旋轉 平衡
[编辑]所有 葉 節點 的 level都 是 1每 個 左 孩子的 level恰好 為 其父親 的 level減 一 每 個 右 孩子的 level等 於其父親 的 level或 為 其父親 的 level減 一 每 個 右 孫子 的 level嚴格 小 於其祖父 節點 的 level每 一 個 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
刪除
[编辑]- 如果
可 以的話 ，減少 其level - Skew其level.
- 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
參 見
[编辑]引用
[编辑]- ^ A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75) (PDF). [2015-03-17]. （
原始 内容 (PDF)存 档于2014-03-27）.
外部 連結
[编辑]- A. Andersson. Balanced search trees made simple（页面
存 档备份，存 于互联网档案 馆） - A. Andersson. A note on searching in a binary search tree（页面
存 档备份，存 于互联网档案 馆） - AA-Tree Applet（页面
存 档备份，存 于互联网档案 馆） by Kubo Kovac - BSTlib - Open source AA tree library for C by trijezdci
- AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
- Thorough tutorial Julienne Walker with lots of code, including a practical implementation
- Object Oriented implementation with tests（页面
存 档备份，存 于互联网档案 馆） - A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75) - Comparison of AA trees, red-black trees, treaps, skip lists, and radix trees
- An example C implementation
- An Objective-C implementation（页面
存 档备份，存 于互联网档案 馆）
| |||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||