AA木

AA木は、平衡2分探索木の一種であり、順序のあるデータを効率的に格納し検索する。Arne Andersson が1993年に発表した。名称は考案者の名前のイニシャルに由来する。

赤黒木とは異なり、AA木では右の子ノードだけが赤となる。逆に言えば、左の子ノードは赤にはならない。結果として2-3-4木ではなく2-3木に相当したものとなり、操作時の処理が大幅に簡略化される。赤黒木では、平衡を保つために以下のような木構造の断片をそれぞれ異なるものとして扱う必要がある。

これに対してAA木では、右のリンクだけが赤になりうるため、以下の2種類だけを考慮すればよい。

1. 平衡回転
-------

AA木は、赤黒木とは異なり、色ではなくレベルの概念を使って実装される。各ノードにはレベルが格納され、常に以下の条件が成り立つようになっている。

葉ノードのレベルは1である。
左の子ノードのレベルは親ノードのレベルより必ず１つ小さい。
右の子ノードのレベルは親ノードのレベルと等しいか１つ小さい。
右の孫ノードのレベルは祖父ノードのレベルより必ず小さい。
レベルが1より大きいノードは、必ず2つの子ノードを持つ。AA木では平衡を保つための操作は skew と split の2つだけである。skew は、挿入・削除によって水平左リンクが生じたときに、右回転させる操作である。split は、挿入・削除によって水平右リンクが2つ生じたときに、条件付きで左回転させる操作である。水平リンクとは、子ノードが親ノードと同じレベルであることを意味する。

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

if nil thenreturn Nilelse if nil) thenreturn Telse if level) == level then//水平左リンクのポインタを入れ替える。// L = left left := right right := Treturn Lelsereturn Tend ifend function

Skew: ファイル:AA Tree Skew2.svg

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

if nil thenreturn Nilelse if nil) or nil)) thenreturn Telse if level == level)) then//水平右リンクが2つある場合。真ん中を持ち上げて、それを返す。// R = right right := left left := T level := level + 1return Relsereturn Tend ifend function

Split: ファイル:AA Tree Split2.svg

2. 挿入
-----

挿入は、まず通常の2分木の探索と挿入を行う。そして、コールスタックを戻る際に木構造の妥当性をチェックし、必要に応じて回転を行う。水平左リンクが生じた場合、skew を行い、2つの水平右リンクが生じた場合、split を行う。そして、その時点の部分木の根ノードのレベルを必要に応じて上げる。レベルを上げる操作は、ここでの擬似コードでは上の skew で行われている。したがって新たに水平リンクが生じる場合があるので、木構造の妥当性チェックは、葉ノードから根に向かって戻る際に各ステップで毎回行う必要がある。

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

//まず、通常の2分木の挿入操作を行う。新たなノードが作成されたか////部分木の根が変わった場合、再帰呼び出しの結果を正しい子ノードに設定する。//X に対応する新たな葉ノードを生成//X == value の場合がない点に注意。その場合、挿入は行われない。////場合によっては、違う動作が望ましいこともある。//

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

return Tend function

3. 削除
-----

多くの平衡2分探索木と同様、内部ノードの削除は、最も近い先行また後続のノードと入れ替えることで、葉ノードの削除に帰着される。先行ノードの検索は、単に左のリンクをたどり、後は右のリンクをたどっていけばよい。同様に後続ノードは右に1回たどって、左をたどっていけばよい。AA木の特徴として2つの子ノードを持つノードのレベルは1より大きいので、先行または後続ノードはレベルが1であり、削除が簡単である。

木構造を再平衡化する方法はあまりバリエーションがない。Andersson が最初の論文で記述した方法が最も単純であり、以下でもそれを説明している。もちろん実際に実装する際には、様々な最適化を施す余地がある。削除後、木の妥当性を保持するため、あるノードと子ノードのレベル差が2以上の場合、そのノードのレベルを下げる。また、子ノードがないのにレベルが1でないノードもレベルを下げる。そして、全体的なレベルの調整を skew と split で行う。この手法は以下のような3つの単純なステップで構成できるため、わかりやすい。

必要ならレベルを下げる。
そのレベルで skew を行う。
そのレベルで split を行う。ただし、以下のコードでは skew と split は1つのノードに対してだけでなく、レベル全体について行う必要があり、コードを複雑化させている。

function delete isinput: X は削除したい値、T は削除元となる木構造の根output: T から X を削除し、平衡化したもの

if nil then return Telse if X > value then right := delete)else if X < value then left := delete)else//葉ノードであれば単純に復帰し、それ以外は再帰する。//if leaf then return Nilelse if nil) then L := successor right := delete, right) value := valueelse L := predecessor left := delete, left) value := valueend ifend if

//再平衡化。必要なら現在のレベルにある全ノードのレベルを下げて、////新たなレベルの全ノードについて skew と split を行う。// T := decrease_level T := skew right := skew)if not nil) then right) := skew))end if T := split right := split) return Tend function

function decrease_level isinput: T はリンクを削除しようとしている木output: T のレベルを下げたもの

should_be = min), level)) + 1if should_be < level then level := should_beif should_be < level) then level) := should_beend ifend if return Tend function

4. 性能
-----

AA木の性能は赤黒木と同等である。AA木は赤黒木よりも回転が多いが、アルゴリズムが単純であるため高速であり、全体としてはほぼ同等な性能となる。安定性は赤黒木のほうがよいが、AA木のほうが平坦になる傾向が強く、結果として検索が若干早くなる。

5. 関連項目
-------

赤黒木
B木
AVL木

6. 脚注
-----

7. 参考文献
-------

[1]

8. 外部リンク
--------

[2] by Kubo Kovac
[3]
[4]
[5]
[6]
[7]
[8]