AA Tree

An AA tree is a balanced tree structure used for efficient storage and retrieval of ordered data. It was introduced by Professor Arne Andersson in his 1993 paper "Balanced search trees made simple," with the design goal of reducing the different cases considered in red-black trees. AA trees can perform search, insertion, and deletion in \(O(\log N)\) time. Below is an example of an AA tree.

The AA tree is a variant of the red-black tree. Unlike red-black trees, red nodes in an AA tree can only be right children. This causes the AA tree to simulate a 2-3 tree rather than a 2-3-4 tree, greatly simplifying maintenance operations. The maintenance algorithm for red-black trees needs to consider seven different cases to correctly balance the tree.

Because red nodes can only be right children, AA trees only need to consider two cases.

Definition

AA trees follow the same rules as red-black trees but add a new rule: red nodes cannot appear as left children.

1. Every node can be either red or black.
2. The root node is always black.
3. Leaf nodes (NULL) are always black.
4. Both children of a red node must be black, meaning no two adjacent red nodes.
5. Every path from the root to a NULL node has the same number of black nodes.
6. Red nodes can only be right children.

Balance Maintenance

Each node in an AA tree maintains a level field, similar to how each node in a red-black tree maintains a color field ("RED" or "BLACK"). The level must satisfy the following five conditions:

1. The level of every leaf node is 1.
2. The level of every left child is one less than its parent's level.
3. The level of every right child is equal to its parent's level or one less than its parent's level.
4. The level of every right grandchild is strictly less than its grandparent's level.
5. Every node with a level greater than 1 has two children.

Horizontal Link

A link where the child's level equals the parent's level is called a horizontal link, similar 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, making the balancing process of AA trees procedurally much simpler.

Insertion and deletion operations may temporarily cause an AA tree to become unbalanced (i.e., violate AA tree invariants). Restoring balance requires only two different operations: "skew" and "split". "Skew" is a right rotation on a subtree containing a left horizontal link, replacing it with a subtree containing a right horizontal link. "Split" is a left rotation that increases the level, replacing a subtree containing two or more consecutive right horizontal links with one containing two fewer consecutive right horizontal links. Implementing balanced insertion and deletion becomes simpler by relying on "skew" and "split" operations to modify the tree only when necessary, rather than having the caller decide whether to perform a "skew" or "split".

split (Left Rotation)

Occurs when there are consecutive right horizontal links (three consecutive right children at the same level, where nodes R and X are both red nodes).

At this point, perform a left rotation on node T, treating nodes with a level less than or equal to this level as a subtree.

1. The right child of the subtree's root becomes the new subtree root.
2. The original subtree root becomes the left child of the new subtree root.
3. The level of the new subtree root 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)

Occurs when there is a left horizontal link (two consecutive left children at the same level).

Perform a right rotation on node T, treating nodes with a level less than or equal to this level as a subtree.

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

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} \]

AA Tree Operations

The AA tree itself is a binary search tree, so the search operation is the same as in other binary search trees. Insertion and deletion operations are similar to those in AVL trees: first insert or delete the key in the tree, then backtrack along the search path to the root, reconstructing 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 // \text{If duplicates are allowed, use <=} \\ 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{// If duplicates are not allowed, perform skew and split at each level} \\ 10 & \qquad \text{skew}(\text{root}); \\ 11 & \qquad \text{split}(\text{root}); \\ 12 & \textbf{end function} \end{array} \]

Deletion

The deletion process is similar to that of other balanced binary trees. First, convert the deletion of an internal node to the deletion of a leaf node. Specifically, replace the internal node with its closest predecessor or successor. Since all nodes in an AA tree with a level greater than 1 have two children, the predecessor or successor node will be at level 1, making deletion of a level 1 node 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 AA trees is comparable to that of red-black trees. Although AA trees perform more rotations than red-black trees, their algorithm is simpler, ultimately leading to similar performance. Red-black trees have more consistent performance across various scenarios, while AA trees tend to be flatter, giving them a slightly faster search speed.

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

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用