AA木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

Red Black Shape Cases.svg

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

AA Tree Shape Cases.svg

平衡回転[編集]

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

  1. 葉ノードのレベルは1である。
  2. 左の子ノードのレベルは親ノードのレベルより必ず小さい。
  3. 右の子ノードのレベルは親ノードのレベル以下である。
  4. 右の孫ノードのレベルは祖父(祖母)ノードのレベルより必ず小さい。
  5. レベルが1より大きいノードは、必ず2つの子ノードを持つ。

AA木では平衡を保つための操作は skew と split の2つだけである。skew は、挿入・削除によって水平左リンクが生じたときに(赤黒木で言えば、左の赤リンクに相当する)、右回転させる操作である。split は、挿入・削除によって水平右リンクが2つ生じたときに(赤黒木で言えば、赤ノードが2つ連続する状態に相当する)、条件付きで左回転させる操作である。水平リンクとは、子ノードが親ノードと同じレベルであることを意味する。

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

    if nil(T) then
        return Nil
    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

Skew: AA Tree Skew2.svg

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

    if nil(T) then
        return Nil
    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

Split: AA Tree Split2.svg

挿入[編集]

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

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

削除[編集]

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

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

  1. 必要ならレベルを下げる。
  2. そのレベルで skew を行う。
  3. そのレベルで split を行う。

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

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

    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(L, right(T))
            value(T) := L
        else
            L := predecessor(T)
            left(T) := delete(L, left(T))
            value(T) := L
        end if
    end if

    再平衡化。必要なら現在のレベルにある全ノードのレベルを下げて、
    新たなレベルの全ノードについて skew と split を行う。
    T := decrease_level(T)
    T := skew(T)
    right(T) := skew(right(T))
    right(right(T)) := skew(right(right(T)))
    T := split(T)
    right(T) := split(right(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木のほうが平坦になる傾向が強く、結果として検索が若干早くなる[2]

関連項目[編集]

脚注[編集]

  1. ^ a b Arne Andersson (1993年), "Balanced Search Trees Made Simple" PREPRINT. In Proc. Workshop on Algorithms and Data Structures, pages 60-71.
  2. ^ A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75)”. 2011年4月1日閲覧。

参考文献[編集]

外部リンク[編集]