|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
AA木（英: AA tree）は、平衡2分探索木の一種であり、順序のあるデータを効率的に格納し検索する。Arne Andersson が1993年に発表した〔 Arne Andersson （1993年）, "Balanced Search Trees Made Simple" PREPRINT. In Proc. Workshop on Algorithms and Data Structures, pages 60-71.〕。名称は考案者の名前のイニシャルに由来する。 赤黒木とは異なり、AA木では右の子ノードだけが赤となる。逆に言えば、左の子ノードは赤にはならない。結果として2-3-4木ではなく2-3木に相当したものとなり、操作時の処理が大幅に簡略化される。赤黒木では、平衡を保つために以下のような木構造の断片をそれぞれ異なるものとして扱う必要がある。 これに対してAA木では、右のリンクだけが赤になりうるため、以下の2種類だけを考慮すればよい。 == 平衡回転 == AA木は、赤黒木とは異なり、色ではなくレベルの概念を使って実装される。各ノードにはレベルが格納され、常に以下の条件が成り立つようになっている。 # 葉ノードのレベルは1である。 # 左の子ノードのレベルは親ノードのレベルより必ず１つ小さい。 # 右の子ノードのレベルは親ノードのレベルと等しいか１つ小さい。 # 右の孫ノードのレベルは祖父（祖母）ノードのレベルより必ず小さい。 # レベルが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 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 Skew: 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 Split: 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「AA木」の詳細全文を読む スポンサード リンク
|