AA木
AA木の性能は赤黒木と同等である。AA木は赤黒木よりも回転が多いが、アルゴリズムが単純であるため高速であり、全体としてはほぼ同等な性能となる。安定性は赤黒木のほうがよいが、AA木のほうが平坦になる傾向が強く、結果として検索が若干早くなる。
AA木(英: AA tree)は、平衡2分探索木の一種であり、順序のあるデータを効率的に格納し検索する。Arne Andersson が1993年に発表した。名称は考案者の名前のイニシャルに由来する。
赤黒木とは異なり、AA木では右の子ノードだけが赤となる。逆に言えば、左の子ノードは赤にはならない。結果として2-3-4木ではなく2-3木に相当したものとなり、操作時の処理が大幅に簡略化される。赤黒木では、平衡を保つために以下のような木構造の断片をそれぞれ異なるものとして扱う必要がある。

これに対してAA木では、右のリンクだけが赤になりうるため、以下の2種類だけを考慮すればよい。