AA tree

An AA tree is a balanced tree structure for efficiently storing and retrieving ordered data. Professor Arne Andersson introduced it in his 1993 paper "Balanced search trees made simple" in 1993; it was designed to reduce the number of cases considered by red-black trees. An AA tree supports search, insertion, and deletion in $O(\log N)$ time. The following is an example of an AA tree.

An AA tree is a variant of a red-black tree. Unlike in a red-black tree, red nodes in an AA tree can only be right children. Thus, an AA tree models a 2-3 tree rather than a 2-3-4 tree, greatly simplifying maintenance. A red-black tree's maintenance algorithm must consider seven different cases to balance the tree correctly.

Because red nodes can only be right children, an AA tree needs to consider only two cases.

Definition

An AA tree follows the same rules as a red-black tree, with one additional rule: a red node cannot be a left child.

1. Every node can be red or black.
2. The root is always black.
3. Leaf nodes (NULL) are always black.
4. Both children of a red node must be black; in other words, two adjacent red nodes are not allowed.
5. Every path from the root to a NULL node contains the same number of black nodes.
6. A red node can only be a right child.

Maintaining balance

Each node of an AA tree maintains a level field, just as each node of a red-black tree maintains a color field ("RED" or "BLACK"). The level satisfies the following five conditions:

1. The level of every leaf is 1.

2. The level of every left child is its parent's level minus 1.

3. The level of every right child is either its parent's level or its parent's level minus 1.

4. The level of every right grandchild is strictly less than its grandparent's level.

5. Every node whose level is greater than 1 has two children.

Horizontal link

A link whose child's level equals its parent's level is called a horizontal link, analogous to a red link in a red-black tree. A single right horizontal link is allowed, but consecutive right horizontal links are not; left horizontal links are not allowed. These restrictions are stricter than those of red-black trees, so balancing an AA tree is considerably simpler to implement.

Insertion and deletion may temporarily make an AA tree unbalanced (that is, violate an AA-tree invariant). Restoring balance requires only two operations: "skew" and "split". "Skew" performs a right rotation on a subtree containing a left horizontal link, replacing it with a subtree containing a right horizontal link. "Split" performs a left rotation and increases the level, replacing a subtree containing two or more consecutive right horizontal links with one containing fewer consecutive right horizontal links. Balanced insertion and deletion become simpler because they rely on "skew" and "split" to modify the tree only when necessary, rather than making the caller decide whether to perform either operation.

split (left rotation)

A consecutive rightward horizontal chain appears (three consecutive right children have the same level, and nodes R and X are both red).

Now rotate node T to the left, treating the nodes at or below this level as a subtree.

1. The subtree root's right child becomes the new subtree root;
2. The original subtree root becomes the new subtree root's left child;
3. The new subtree root's level is increased by 1.

Pseudocode implementation

$$\begin{array}{ll} 1 & \textbf{function } \text{split}(\text{root}) \\ 2 & \qquad \textbf{if } \text{root}\rightarrow\text{right}\rightarrow\text{right}\rightarrow\text{level} == \text{root}\rightarrow\text{level} \\ 3 & \qquad\qquad \text{rotate\_left}(\text{root}) \\ 4 & \textbf{end function} \end{array}$$

skew (right rotation)

A leftward horizontal chain appears (two consecutive left children have the same level).

Rotate node T to the right, treating the nodes at or below this level as a subtree.

1. The subtree root's left child becomes the new subtree root;
2. The original subtree root becomes the new subtree root's right child.

Pseudocode implementation

$$\begin{array}{ll} 1 & \textbf{function } \text{skew}(\text{root}) \\ 2 & \qquad \textbf{if } \text{root}\rightarrow\text{left}\rightarrow\text{level} == \text{root}\rightarrow\text{level} \\ 3 & \qquad\qquad \text{rotate\_right}(\text{root}) \\ 4 & \textbf{end function} \end{array}$$

Operations on an AA tree

An AA tree is itself a binary search tree, so searching is the same as in other binary search trees. Insertion and deletion are similar to those in an AVL tree: first insert or delete the key, then backtrack along the search path to the root and reconstruct the tree along the way.

Insertion

Pseudocode implementation

$$\begin{array}{ll} 1 & \textbf{function } \text{insert}(\text{root}, \text{add}) \\ 2 & \qquad \textbf{if } \text{root} == \text{NULL} \\ 3 & \qquad\qquad \text{root} \gets \text{add} \\ 4 & \qquad \textbf{else if } \text{add}\rightarrow\text{key} < \text{root}\rightarrow\text{key} \qquad //如果允许重复<= \\ 5 & \qquad\qquad \text{insert}(\text{root}\rightarrow\text{left}, \text{add}) \\ 6 & \qquad \textbf{else if } \text{add}\rightarrow\text{key} > \text{root}\rightarrow\text{key} \\ 7 & \qquad\qquad \text{insert}(\text{root}\rightarrow\text{right}, \text{add}) \\ 8 & \qquad \textbf{end if} \\ 9 & \qquad \text{//如果不允许重复，在每一level上进行skew和split} \\ 10 & \qquad \text{skew}(\text{root}); \\ 11 & \qquad \text{split}(\text{root}); \\ 12 & \textbf{end function} \end{array}$$

Deletion

Deletion is similar to deletion in other balanced binary trees: first convert deletion of an internal node into deletion of a leaf. Replace the internal node with its closest predecessor or successor. Since every AA-tree node with level greater than 1 has two children, the predecessor or successor is at level 1, whose deletion is relatively simple.

Pseudocode implementation

$$\begin{array}{ll} 1 & \text{//To rebalance the tree} \\ 2 & \textbf{if} \ \text{root->left->level} < \text{root->level} -1 \ \textbf{or} \ \text{root->right->level} < \text{root->level} -1 \\ 3 & \{ \\ 4 & \qquad \textbf{if} \ \text{root->right->level} > \text{--root->level} \\ 5 & \qquad \{ \\ 6 & \qquad\qquad \text{root->right->level} \gets \text{root->level} \\ 7 & \qquad \} \\ 8 & \qquad \text{skew}(\text{root}) \\ 9 & \qquad \text{skew}(\text{root->right}) \\ 10 & \qquad \text{skew}(\text{root->right->right}) \\ 11 & \qquad \text{split}(\text{root}) \\ 12 & \qquad \text{split}(\text{root->right}) \\ 13 & \} \\ \end{array}$$

Performance

The performance of an AA tree is comparable to that of a red-black tree. Although an AA tree performs more rotations, its algorithms are simpler, resulting in similar performance. Red-black trees have more consistent performance across cases, while AA trees are often flatter, giving them slightly faster searches.

References

1. AA tree - Wikipedia
2. Introduction to AA trees
3. AA tree - Visualization
4. CMSC 420 Lecture 6: 2-3, Red-black, and AA trees