AA Tree

AA tree (named after its inventor, Swedish computer scientist Arne Andersson, who introduced the structure in 1993 under the title "Balanced Search Trees Made Simple") is a self-balancing binary search tree (BST) in computation and algorithms that guarantees O(log N) worst-case time for lookups, insertions, and deletions. An AA tree is mathematically isomorphic to a restricted red–black tree (and specifically a binary representation of a 2–3 B-tree) in which red nodes may only appear as right children of their parents—an invariant that eliminates half of the restructuring cases that complicate traditional red–black tree implementations.

Instead of storing explicit red/black color bits and handling symmetric left-versus-right uncle configurations, each node x in an AA tree stores a small integer level level(x) ≥ 1 (representing the black-height of x in the corresponding 2–3 tree). Rebalancing after any insertion or deletion is reduced to two elementary, five-line rotation primitives: Skew (a single right rotation that converts an illegal left horizontal link into a legal right horizontal link) and Split (a single left rotation with a level increment that resolves two consecutive right horizontal links).

Correspondence with 2–3 Trees and Red–Black Trees

In a standard red–black tree (Guibas and Sedgewick, 1978), a 2–3–4 B-tree is encoded as a binary tree by coloring internal B-tree node links red (horizontal links at the same B-tree depth) and inter-level B-tree links black (vertical links stepping down one B-tree level). Because a 3-node in a standard red–black tree can lean either to the left (a red left child) or to the right (a red right child), deletion and insertion routines must handle numerous mirrored rotation cases.

Arne Andersson eliminated this ambiguity by restricting the representation to 2–3 trees in which every 3-node is oriented with its extra key as a right-leaning horizontal child (later revisited by Robert Sedgewick in 2008 as a left-leaning red–black tree, which flips the orientation).

The Five AA Tree Level Invariants

Let every node x in an AA tree carry an integer attribute level(x) ∈ {1, 2, …, ⌊log₂ N⌋ + 1}, with the null sentinel nil defined to have level(nil) = 0. An AA tree maintains five structural invariants at all times:

1. Leaf Level Invariant: The level of every leaf node (a node with two nil children) is 1: level(x) = 1.
2. Left-Child Strict Descent (No Left Horizontal Links): The level of every left child is strictly less than the level of its parent:

(Equivalently, in red–black terminology, no left child may be red.)

1. Right-Child Non-Strict Descent (Single Right Horizontal Link Allowed): The level of every right child is either equal to or 1 less than the level of its parent:

When level(x.*right*) = level(x), the edge (x, x.*right*) is called a right horizontal link (forming a 3-node (x, x.*right*) at the same level).

1. Grandchild Strict Descent (No Consecutive Right Horizontal Links): The level of every right grandchild is strictly less than the level of its grandparent:

This forbids three nodes from lying at the same horizontal level (forbidding 4-nodes).

1. Internal Two-Child Invariant: Every node of level level(x) > 1 has two non-nil children (x.*left* ≠ nil and x.*right* ≠ nil).

Logarithmic Height Bound

Within computational complexity theory, these five invariants guarantee that a subtree rooted at a node x of level k = level(x) contains at least 2^k − 1 nodes:

• Consequently, the maximum level at the root r of an N-node AA tree satisfies level(r) ≤ ⌊log₂(N + 1)⌋.
• Because at most one right horizontal link can occur at each level along any root-to-leaf path (Invariant 4), the worst-case physical height of an N-node AA tree is at most 2 ⌊log₂(N + 1)⌋, guaranteeing O(log N) worst-case search time.

Skew(T): Eliminating a Left Horizontal Link

Whenever an insertion or deletion temporarily creates a left horizontal link where level(T.*left*) = level(T) (violating Invariant 2), the Skew(T) operation performs a single right rotation around T and its left child L = T.*left*:

• Check condition: If T ≠ nil and level(T.*left*) == level(T):
  • Set L ← T.*left*, T.*left* ← L.*right*, and L.*right* ← T.
  • Return L as the new subtree root (whose level remains unchanged, while the former left horizontal link becomes a legal right horizontal link from L to T).

Note that while Skew(T) restores Invariant 2, converting a left horizontal link into a right horizontal link can create two consecutive right horizontal links if T already had a right horizontal child—which is immediately repaired by Split.

Split(T): Eliminating Consecutive Right Horizontal Links

Whenever a node T possesses two consecutive right horizontal links—meaning level(T.*right*.*right*) = level(T) (violating Invariant 4 by forming a temporary 4-node)—the Split(T) operation performs a single left rotation around T and its right child R = T.*right* and promotes R to the next higher level:

• Check condition: If T ≠ nil and T.*right* ≠ nil and level(T.*right*.*right*) == level(T):
  • Set R ← T.*right*, T.*right* ← R.*left*, and R.*left* ← T.
  • Increment the level of the promoted middle node: level(R) ← level(R) + 1.
  • Return R as the new subtree root (now with two strict level-descending children T and R.*right*).

Insertion and Deletion Procedures

Insertion: A new key k is inserted at a leaf at level = 1 via standard recursive BST search. As the recursion unwinds bottom-up along the search path, each ancestor T executes just two calls:

1. T ← Skew(T)
2. T ← Split(T)

before returning T to its parent. No other case analysis is needed for insertion!

Deletion: Deleting an internal node first swaps its key with its in-order predecessor or successor at level 1 and removes the level-1 node. As the recursion unwinds bottom-up at ancestor T:

1. Level Decrement (DecreaseLevel): If either level(T.*left*) < level(T) − 1 or level(T.*right*) < level(T) − 1 (meaning a child dropped two levels below T), lower T's level to shouldBe = min(level(T.*left*), level(T.*right*)) + 1. If T had a right horizontal child R = T.*right* with level(R) > shouldBe, also lower level(R) ← shouldBe (merging up to three horizontal nodes at the lowered level).
2. Three Skew and Two Split Calls: Because lowering T and T.*right* can create up to three horizontal nodes at the same level, execute a fixed five-step sequence in O(1) time:
   • T ← Skew(T)
   • T.*right* ← Skew(T.*right*)
   • T.*right*.*right* ← Skew(T.*right*.*right*)
   • T ← Split(T)
   • T.*right* ← Split(T.*right*)

Comparison of AA Trees with Other Balanced BSTs

1. Formal Verification and Verified Software Kernels: Because the entire rebalancing logic of an AA tree reduces to the two algebraic operators Skew and Split without asymmetric parent/uncle pointer inspection, AA trees are widely used in formally verified operating-system kernels, theorem provers (Coq, Isabelle/HOL, Lean), and functional programming languages.
2. Persistent and Concurrent Functional Data Structures: Because AA trees operate cleanly in a purely recursive bottom-up path-copying fashion without parent pointers, each insertion or deletion allocates at most O(log N) immutable path nodes, providing persistent ordered maps and sets alongside scapegoat trees and splay trees.

How does an AA tree differ from Sedgewick's left-leaning red–black (LLRB) tree?

Sedgewick's 2008 left-leaning red–black (LLRB) tree is a direct structural dual of Andersson's 1993 AA tree: whereas an AA tree stores an explicit integer level and places horizontal (red) links on the right child, an LLRB tree stores a 1-bit color flag and places horizontal (red) links on the left child.

How many bits are required to store the level field in an AA tree node?

Because the maximum level of an AA tree on N nodes never exceeds ⌊log₂(N + 1)⌋, even a 64-bit address space (N ≤ 2⁶⁴) requires only a 6-bit (or 1-byte unsigned integer) field per node to store level(x).

1. Andersson, A. (1993). "Balanced search trees made simple." Proceedings of the Third Workshop on Algorithms and Data Structures (WADS 1993), Lecture Notes in Computer Science, 709, 60–71. https://doi.org/10.1007/3-540-57155-8_236
2. Bayer, R. (1972). "Symmetric binary B-trees: Data structure and maintenance algorithms." Acta Informatica, 1(4), 290–306. https://doi.org/10.1007/BF00289509
3. Guibas, L. J., & Sedgewick, R. (1978). "A dichromatic framework for balanced trees." Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS), 8–21. https://doi.org/10.1109/SFCS.1978.3
4. Sedgewick, R. (2008). "Left-leaning red–black trees." Department of Computer Science Technical Report, Princeton University, 1–17. https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf