AAツリー

コンピュータサイエンスにおけるAAツリーは、順序付けられたデータを効率的に保存および取得するために使用されるバランスツリーの一種です。AAツリーは、その考案者であるスウェーデンのコンピュータ科学者アルネ・アンダーソンにちなんで名付けられました。[ 1 ]

AA木は、赤黒木（二分探索木の一種で、エントリの効率的な追加と削除をサポートする）のバリエーションです。赤黒木とは異なり、AA木上の赤いノードは右の子としてのみ追加できます。つまり、赤いノードは左の子になることはできません。これにより、2-3-4木ではなく2-3木がシミュレートされ、保守操作が大幅に簡素化されます。赤黒木の保守アルゴリズムでは、木のバランスを適切に取るために、以下の7つの異なる形状を考慮する必要があります。

一方、AA ツリーでは、右のリンクのみが赤になるという厳格な要件があるため、考慮する必要があるのは 2 つの形状のみです。

回転のバランスをとる

赤黒木ではノード（色）ごとに1ビットのバランスメタデータが必要ですが、AA木ではノードごとにO(log(log(N)))ビットのメタデータ（整数「レベル」の形式）が必要です。AA木には以下の不変条件が成り立ちます。

  1. すべてのリーフ ノードのレベルは 1 です。
  2. 左の子のレベルは、その親のレベルよりちょうど 1 低くなります。
  3. すべての右の子のレベルは、その親のレベルと等しいか、それよりも 1 つ低くなります。
  4. すべての右孫のレベルは、その祖父母のレベルよりも厳密に低くなります。
  5. レベルが 1 より大きいすべてのノードには 2 つの子があります。

子ノードのレベルが親ノードのレベルと等しいリンクは水平リンクと呼ばれ、赤黒木における赤リンクに類似しています。個々の右水平リンクは許可されますが、連続するリンクは禁止されます。また、すべての左水平リンクは禁止されます。これらは、赤黒木における類似の制約よりも厳しい制約であり、その結果、AA木の再バランス調整は赤黒木の再バランス調整よりも手続き的にはるかに単純になります。

挿入と削除は、AAツリーを一時的にアンバランスにする（つまり、AAツリーの不変条件に違反する）可能性があります。バランスを回復するには、「skew」と「split」という2つの異なる操作のみが必要です。skewは、左水平リンクを含むサブツリーを、右水平リンクを含むサブツリーに置き換えるための右回転です。splitは、2つ以上の連続する右水平リンクを含むサブツリーを、連続する右水平リンクが2つ少ないサブツリーに置き換えるための左回転とレベルの増加です。バランスを維持した挿入と削除の実装は、skew操作とsplit操作を使用して、呼び出し元がskewまたはsplitを行うかどうかを決定せずに、必要な場合にのみツリーを変更することで簡素化されます。 

関数skew の入力は 、再バランス調整が必要な AA ツリーを表すノード T です。 出力は、再バランス調整された AA ツリーを表す別のノードです。nil(T)の場合は Nil を返し、そうでない場合はnil(left(T))の場合は T を返し、そうでない場合はlevel(left(T)) == level(T)の場合は水平左リンクのポインターを交換します。 L = 左(T) 左(T) := 右(L) 右(L) := T L を返す、そうでない場合 はT を返す、もしそうなら終了、関数終了

スキュー:

関数split の入力は 、再バランス調整が必要な AA ツリーを表すノード T です。 出力は、再バランス調整された AA ツリーを表す別のノードです。nil(T)の場合は Nil を返し、そうでない場合はnil(right(T))またはnil(right(right(T))) の場合は T を返します。そうでない場合はlevel(T) == level(right(right(T)))の場合は2 つの水平方向の右リンクがあります。中央のノードを取得し、それを昇格させて返します。 R = 右(T) 右(T) := 左(R) 左(R) := T レベル(R) := レベル(R) + 1 R を返す、そうでない場合 はT を返す、もしそうなら終了、関数終了

スプリット：

挿入

挿入は、通常の二分木探索と挿入手順から始まります。その後、コールスタックが展開されるにつれて（探索が再帰的に実装されていると仮定）、ツリーの妥当性を容易に確認し、必要に応じて回転を実行できます。水平左リンクが発生した場合は傾斜が実行され、水平右リンクが2つ発生した場合は分割が実行され、現在のサブツリーの新しいルートノードのレベルがインクリメントされる可能性があります。上記のコードでは、level(T) がインクリメントされていることに注意してください。これにより、リーフから変更がバブルアップするにつれて、ツリーの妥当性を確認し続ける必要があります。 

関数insert の入力は 、挿入する値 X と、それを挿入するツリーのルート T です。 出力は、 X を含むバランスの取れたバージョン T です。通常の二分木挿入手順を実行します。新しいノードが作成された場合、またはサブツリーのルートが変更された場合に備えて、再帰呼び出しの結果を正しい子ノードに設定します。if nil ( T ) then Xを持つ新しいリーフノードを作成します 。return node(X, 1, Nil, Nil) else if X < value(T) then 左(T) := 挿入(X, 左(T)) そうでなければ、X > value(T)ならば 右(T) := 挿入(X, 右(T)) end if X == value(T) の場合のケースは未規定であることに注意してください。指定されているとおり、挿入は何も効果がありません。実装者は異なる動作を望むかもしれません。傾斜させてから分割します。回転が発生するかどうかを決定する条件は、上記の手順の中にあります。 T := skew(T) T := 分割(T) Tを返す終了関数

削除

ほとんどのバランス型二分木と同様に、内部ノードの削除は、内部ノードを最も近い先行ノードまたは後続ノードと入れ替えることで、リーフノードの削除に変換できます。これは、ツリー内のノード数または実装者の意図に応じて行われます。先行ノードを取得するには、左リンクを1つたどり、残りの右リンクをすべてたどるだけです。同様に、後続ノードは、右リンクを1つたどり、ヌルポインタが見つかるまで左リンクをたどることで見つけることができます。レベル1以上のすべてのノードは2つの子ノードを持つというAAプロパティにより、後続ノードまたは先行ノードはレベル1に配置されるため、削除は簡単です。

ツリーのバランスを再調整するには、いくつかのアプローチがあります。Anderssonが元の論文で説明した方法が最も単純であり、ここでも説明しますが、実際の実装ではより最適化されたアプローチが採用される可能性があります。ノードの削除後、ツリーの妥当性を維持するための最初のステップは、子ノードが2レベル下に存在するノード、または子ノードが存在しないノードのレベルを下げることです。次に、レベル全体を歪ませて分割する必要があります。このアプローチが支持されたのは、概念的に定義すると、3つの分かりやすい個別のステップに分かれているためです。

  1. 必要に応じてレベルを下げます。
  2. レベルを歪めます。
  3. レベルを分割します。

ただし、今回はノードだけではなくレベル全体を傾斜させて分割する必要があり、コードが複雑になります。 

関数delete の入力は 、削除する値 X と、その値を削除するツリーのルート T です。 出力は、バランスのとれた、値 X を含まない T です。nil(T)の場合 Tを返す そうでなければ、X > value(T)ならば 右(T) := 削除(X, 右(T)) そうでなければ、X < value(T)ならば 左(T) := 削除(X, 左(T)) else葉の場合は簡単、そうでない場合は葉の場合に簡約する。if leaf (T then 右に戻る(T) そうでなければnil(left(T))なら L := 後継者(T) 右(T) := 削除(値(L), 右(T)) 値(T) := 値(L) それ以外 L := 前任者(T) 左(T) := 削除(値(L), 左(T)) 値(T) := 値(L) 終了の場合終了の場合ツリーのバランスを調整します。必要に応じて、このレベルのすべてのノードのレベルを下げ、新しいレベルのすべてのノードを傾斜させて分割します。 T := 減少レベル(T) T := skew(T) 右(T) := skew(右(T)) nilでない場合(右(T)) 右(右(T)) := 斜め(右(右(T))) 終了の場合 T := 分割(T) 右(T) := 分割(右(T)) Tを返す 終了関数
関数decrease_level の入力は 、レベルをスキップするリンクを削除するツリー T です。 出力は、レベルが減少した T です。 should_be = min(レベル(左(T)), レベル(右(T))) + 1 should_be < レベル(T)の場合 レベル(T) := should_be should_be < レベル(right(T))の場合 レベル(右(T)) := should_be 終了の場合終了の場合 Tを返す 終了関数

このアルゴリズムによる削除の良い例は、Andersson の論文に記載されています。

パフォーマンス

AA木の性能は赤黒木と同等です。AA木は赤黒木よりも回転回数が多いものの、より単純なアルゴリズムの方が高速になる傾向があり、これらがバランスして同様の性能になります。赤黒木はAA木よりも性能が安定していますが、AA木はより平坦な構造になる傾向があるため、探索時間はわずかに速くなります。[ 2 ]

参照

参考文献

  1. ^ Andersson, Arne (1993). 「Balanced search trees made simple」(PDF) . Dehne, Frank KHA; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (編).アルゴリズムとデータ構造, 第3回ワークショップ, WADS '93, モントリオール, カナダ, 1993年8月11日～13日, Proceedings . Lecture Notes in Computer Science. Vol. 709. Springer. pp.  60– 71. doi : 10.1007/3-540-57155-8_236 .
  2. ^ Heger, Dominique A. (2004年10月). 「二分探索木データ構造の性能挙動に関する考察」(PDF) .アップグレード. 5 (5). 欧州専門情報学会協議会: 67–75 . 2014年3月27日時点のオリジナル(PDF)からのアーカイブ。
「 https://en.wikipedia.org/w/index.php?title=AA_tree&oldid=1290444271」から取得