AA木

AA木とは

AA木（英: AA tree）は、アルネ・アンダーソンによって1993年に考案された平衡二分探索木の一種です。名前は考案者のイニシャルに由来します。AA木は、順序付けられたデータを効率的に格納し、検索するためのデータ構造です。

AA木の特徴

AA木は、赤黒木と同様に、ノードのバランスを保つことで、最悪の場合でも効率的な検索を可能にします。しかし、赤黒木とは異なり、AA木では、右の子ノードのみが赤になるという制約があります。これは、左の子ノードが赤になることはないことを意味します。

この制約により、AA木は2-3木と同等になり、操作時の処理が大幅に簡略化されます。赤黒木では、平衡を保つために複数の異なる木構造を考慮する必要がありますが、AA木では、右リンクのみが赤であるという制約により、考慮すべきケースが大幅に削減されます。

レベルの概念

AA木では、赤黒木とは異なり、色ではなくレベルの概念を使って実装されます。各ノードはレベルを持ち、以下の条件を満たすように構造が維持されます。

葉ノードのレベルは1です。
左の子ノードのレベルは、親ノードのレベルより必ず1つ小さくなります。
右の子ノードのレベルは、親ノードのレベルと同じか、1つ小さくなります。
右の孫ノードのレベルは、祖父（祖母）ノードのレベルより必ず小さくなります。
レベルが1より大きいノードは、必ず2つの子ノードを持ちます。

平衡化操作

AA木では、平衡を保つための操作は`skew`と`split`の2つだけです。

skew

`skew`は、挿入や削除によって水平左リンクが発生した場合（赤黒木でいう左の赤リンクに相当）、右回転を行う操作です。水平リンクとは、子ノードが親ノードと同じレベルを持つことを意味します。


function skew is
input: T, 再平衡化が必要なAA木を表すノード
output: 平衡化されたAA木を表すノード

if nil(T) then
return Nil
else if nil(left(T)) then
return T
else if level(left(T)) == level(T) then
水平左リンクのポインタを入れ替える。
L = left(T)
left(T) := right(L)
right(L) := T
return L
else
return T
end if
end function

split

`split`は、挿入や削除によって水平右リンクが2つ連続した場合（赤黒木でいう赤ノードが2つ連続する状態に相当）、条件付きで左回転を行う操作です。


function split is
input: T, 再平衡化が必要なAA木を表すノード
output: 平衡化されたAA木を表すノード

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
水平右リンクが2つある場合。真ん中を持ち上げて、それを返す。
R = right(T)
right(T) := left(R)
left(R) := T
level(R) := level(R) + 1
return R
else
return T
end if
end function

挿入操作

挿入操作は、まず通常の二分探索木と同様に挿入を行います。その後、コールスタックを戻る際に、木の構造がAA木のルールに従っているかをチェックし、必要に応じて`skew`や`split`を実行します。水平左リンクが発生した場合は`skew`を、水平右リンクが2つ連続した場合は`split`を実行します。


function insert is
input: X は挿入したい値、T は挿入先となる木構造の根
output: T に X を挿入して平衡化させたもの

まず、通常の2分木の挿入操作を行う。新たなノードが作成されたか
部分木の根が変わった場合、再帰呼び出しの結果を正しい子ノードに設定する。
if nil(T) then
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
X == value(T) の場合がない点に注意。その場合、挿入は行われない。
場合によっては、違う動作が望ましいこともある。

skew を行い、次いで split を行う。実際に回転をするかどうかは
上掲のようにこれら手続き内で判断する。
T := skew(T)
T := split(T)

return T
end function

削除操作

削除操作は、多くの平衡二分探索木と同様に、内部ノードの削除を、最も近い先行ノードまたは後続ノードとの置き換えによって、葉ノードの削除に帰着させます。AA木では、2つの子ノードを持つノードのレベルは1より大きいため、先行または後続ノードはレベルが1になり、削除が容易です。

削除後、木の構造を再平衡化するために、あるノードとその子ノードのレベル差が2以上の場合、そのノードのレベルを下げます。また、子ノードがないにもかかわらずレベルが1でないノードもレベルを下げます。

再平衡化は、以下の3つのステップで行われます。

1. 必要に応じてレベルを下げる。
2. そのレベルで`skew`を行う。
3. そのレベルで`split`を行う。


function delete is
input: X は削除したい値、T は削除元となる木構造の根
output: T から 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 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

再平衡化。必要なら現在のレベルにある全ノードのレベルを下げて、
新たなレベルの全ノードについて skew と split を行う。
T := decrease_level(T)
T := skew(T)
right(T) := skew(right(T))
if not nil(right(T)) then
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 はリンクを削除しようとしている木
output: T のレベルを下げたもの

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木はより平坦な構造になりやすく、検索がわずかに速くなる傾向があります。

関連項目

赤黒木
B木
AVL木

参考文献

A. Andersson. A note on searching in a binary search tree

外部リンク

AA-Tree Applet by Kubo Kovac
AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
Thorough tutorial with lots of code
Practical implementation（ZIP形式）
Object Oriented implementation with tests
Comparison of AA trees, red-black trees, treaps, skip lists, and radix trees
An example C implementation

もう一度検索