C/C++ の AA ツリーとは何ですか?

コンピュータ サイエンスでは、AA ツリーは、順序付けされたデータを効率的に保存および取得するためのバランスのとれたツリー実装として定義されます。 AA ツリーは、エントリの効率的な追加と削除をサポートする二分探索ツリーである赤黒ツリーの変形とみなされます。赤黒ツリーとは異なり、AA ツリー上の赤ノードは右側の子ノードとしてのみ追加でき、左側の子ノードとして追加できません。この操作の結果、2-3-4 ツリーではなく 2-3 ツリーがシミュレートされるため、メンテナンス操作が簡素化されます。赤黒木のメンテナンス アルゴリズムでは、木のバランスを正しく保つために 7 つの異なる形状を想定または考慮する必要があります。

#赤黒ツリーとは対照的に、AA ツリーは 2 つの形状を仮定または考慮するだけで済みます。右のリンクは赤色になる場合があります。

#バランスの取れた回転

赤黒ツリーには、ノードごとに 1 つのバランス メタデータ ビット (色) が必要です。一方、AA ツリーの各ノードには、整数「レベル」の形式で O(log(log(N))) 個のメタデータ ビットが必要です。次の不変式が AA ツリーに適用されます:

各リーフ ノードのレベルは 1 とみなされます。
左の各子ノードのレベルは、親ノードより 1 低くなります。
右の各子ノードのレベルは、その親ノードと同じか 1 つ低くなります。
各右孫ノードのレベルは、その祖父母ノードのレベルよりも厳密に小さくなります。
レベルが 1 より大きいすべてのノードには 2 つの子ノードがあります。
AA ツリーのリバランスは、赤黒ツリーのリバランスよりもはるかに簡単です。

AA ツリーでは、バランスを回復するために必要な操作は 2 つだけです。「スキュー」と「スプリット」です。スキューは右回転として扱われ、左の水平リンクで構成されるサブツリーが右の水平リンクに置き換えられます。分割の場合、左回転してレベルを上げ、連続性の低い 2 つの右水平リンクを含むサブツリーを 2 つ以上の連続する右水平リンクに置き換えます。以下では、「スキュー」と「スプリット」の 2 つの操作について説明します。

関数スキューの定義は次のとおりです:

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(left(t)) then
return t
else if level(left(t)) == level(t) then
   Exchange the pointers of horizontal left links.
   l = left(t)
left(t) := right(l)
right(l) := t
return l
else
return t
end if
end function

#関数分割の変換は次のとおりです

は:

関数分割は

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
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
We have two horizontal right links. The middle node is taken, elevate it, and return it.
      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-# です##

以上がC/C++ の AA ツリーとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。