AA木（英: AA tree）は、平衡2分探索木の一種であり、順序のあるデータを効率的に格納し検索する。Arne Andersson が1993年に発表した。名称は考案者の名前のイニシャルに由来する。赤黒木とは異なり、AA木では右の子ノードだけが赤となる。逆に言えば、左の子ノードは赤にはならない。結果として2-3-4木ではなく2-3木に相当したものとなり、操作時の処理が大幅に簡略化される。赤黒木では、平衡を保つために以下のような木構造の断片をそれぞれ異なるものとして扱う必要がある。これに対してAA木では、右のリンクだけが赤になりうるため、以下の2種類だけを考慮すればよい。AA木は、赤黒木とは異なり、色ではなくレベルの概念を使って実装される。各ノードにはレベルが格納され、常に以下の条件が成り立つようになっている。AA木では平衡を保つための操作は skew と split の2つだけである。skew は、挿入・削除によって水平左リンクが生じたときに（赤黒木で言えば、左の赤リンクに相当する）、右回転させる操作である。split は、挿入・削除によって水平右リンクが2つ生じたときに（赤黒木で言えば、赤ノードが2つ連続する状態に相当する）、条件付きで左回転させる操作である。水平リンクとは、子ノードが親ノードと同じレベルであることを意味する。Skew: Split: 挿入は、まず通常の2分木の探索と挿入を行う。そして、コールスタックを戻る際に木構造の妥当性をチェックし、必要に応じて回転を行う。水平左リンクが生じた場合、skew を行い、2つの水平右リンクが生じた場合、split を行う。そして、その時点の部分木の根ノードのレベルを必要に応じて上げる。レベルを上げる操作は、ここでの擬似コードでは上の skew で行われている。したがって新たに水平リンクが生じる場合があるので、木構造の妥当性チェックは、葉ノードから根に向かって戻る際に各ステップで毎回行う必要がある。多くの平衡2分探索木と同様、内部ノードの削除は、最も近い先行(predecessor)また後続(successor)のノードと入れ替えることで、葉ノードの削除に帰着される。先行(predecessor)ノードの検索は、単に左のリンクをたどり、後は右のリンクをたどっていけばよい。同様に後続(successor)ノードは右に1回たどって、左をたどっていけばよい。AA木の特徴として2つの子ノードを持つノードのレベルは1より大きいので、先行(predecessor)または後続(successor)ノードはレベルが1であり、削除が簡単である。木構造を再平衡化する方法はあまりバリエーションがない。Andersson が最初の論文で記述した方法が最も単純であり、以下でもそれを説明している。もちろん実際に実装する際には、様々な最適化を施す余地がある。削除後、木の妥当性を保持するため、あるノードと子ノードのレベル差が2以上の場合、そのノードのレベルを下げる。また、子ノードがないのにレベルが1でないノードもレベルを下げる。そして、全体的なレベルの調整を skew と split で行う。この手法は以下のような3つの単純なステップで構成できるため、わかりやすい。ただし、以下のコードでは skew と split は1つのノードに対してだけでなく、レベル全体について行う必要があり、コードを複雑化させている。AA木の性能は赤黒木と同等である。AA木は赤黒木よりも回転が多いが、アルゴリズムが単純であるため高速であり、全体としてはほぼ同等な性能となる。安定性は赤黒木のほうがよいが、AA木のほうが平坦になる傾向が強く、結果として検索が若干早くなる。

出典:wikipedia