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つ少ない連続する右水平リンクを含むサブツリーに置き換えるのは、左回転とレベルの増加です。 「スキュー」と「スプリット」の操作について、以下で説明します-

関数スキューは

   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

分割-