AA木
AA木は、赤黒木とは異なり、色ではなくレベルの概念を使って実装される。各ノードにはレベルが格納され、常に以下の条件が成り立つようになっている。
葉ノードのレベルは1である。
左の子ノードのレベルは親ノードのレベルより必ず1つ小さい。
右の子ノードのレベルは親ノードのレベルと等しいか1つ小さい。
右の孫ノードのレベルは祖父(祖母)ノードのレベルより必ず小さい。
レベルが1より大きいノードは、必ず2つの子ノードを持つ。
AA木では平衡を保つための操作は skew と split の2つだけである。skew は、挿入・削除によって水平左リンクが生じたときに(赤黒木で言えば、左の赤リンクに相当する)、右回転させる操作である。split は、挿入・削除によって水平右リンクが2つ生じたときに(赤黒木で言えば、赤ノードが2つ連続する状態に相当する)、条件付きで左回転させる操作である。水平リンクとは、子ノードが親ノードと同じレベルであることを意味する。
Skew:
Split: