C/C++で学ぶAA木（AA Tree）とは？基本概念と平衡化操作を徹底解説

AA木（AA Tree）とは

コンピュータサイエンスにおいて、AA木（AA Tree）とは、順序付きデータを効率的に格納・検索するために実装された平衡木（バランスドツリー）の一種です。AA木は、赤黒木（Red-Black Tree）の変種として扱われます。赤黒木は二分探索木の一形態であり、要素の追加や削除を効率的にサポートします。

赤黒木と大きく異なる点は、AA木では赤いノードを右の子としてのみ追加でき、左の子としては配置できないという制約があることです。この制約により、2-3-4木ではなく2-3木をシミュレートすることになり、その結果、木の保守操作が大幅に簡素化されます。赤黒木の平衡化アルゴリズムでは、木を適切に平衡させるために7つの異なる形状を想定・考慮する必要があります。

一方、AA木では「赤いリンクは右側のみに存在できる」という厳格な要件があるため、考慮すべき形状はわずか2つだけで済みます。

平衡化のための回転操作

赤黒木がノードごとに1ビットの平衡化メタデータ（色情報）のみを必要とするのに対し、AA木では各ノードに整数型の「レベル（level）」というメタデータが必要となり、そのサイズはO(log(log(N)))ビットになります。AA木には以下の不変条件が成り立ちます。

• すべての葉ノードのレベルは1とみなされる。
• すべての左の子のレベルは、親のレベルより正確に1小さい。
• すべての右の子のレベルは、親のレベルと等しいか、あるいは1小さい。
• すべての右の孫ノードのレベルは、祖父ノードのレベルより厳密に小さい。
• レベルが1より大きいすべてのノードは、必ず2つの子を持つ。

AA木の再平衡化は、赤黒木の再平衡化に比べて、手続き的にはるかにシンプルです。

AA木の場合、平衡を回復するために必要な操作は「skew（スキュー）」と「split（スプリット）」という2つの異なる操作だけです。Skewは右回転に相当し、左水平リンクから構成される部分木を、右水平リンクから構成される部分木へと置き換えます。Splitは左回転とレベルの増加を組み合わせた操作で、2つ以上連続した右水平リンクから構成される部分木を、連続する右水平リンクが2つ少ない部分木へと置き換えます。以下に、それぞれの操作について詳しく説明します。

skew関数

   入力：再平衡化が必要なAA木を表すノード t。
   出力：再平衡化された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

split関数

   入力：再平衡化が必要なAA木を表すノード t。
   出力：再平衡化された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つの右水平リンクが存在する場合、中央のノードを取り上げて
// レベルを1つ上げ、そのノードを返す。
   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操作の流れです。これら2つの操作を組み合わせることで、挿入や削除の際にAA木の不変条件を効率的に維持することができます。