Information about Aa Tree

An Arne Andersson tree (AA tree) in computer science is a red-black tree with one additional rule. Unlike red-black trees, RED nodes on an AA tree can only be added as a right subchild. In other words, no RED node can be a left subchild. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which greatly simplifies the maintenance operations. The maintenance algorithms for a red-black tree need to consider seven different shapes to properly balance the tree:



An AA tree on the other hand only needs to consider two shapes due to the strict requirement that only right links can be red:



For the discussion below (which is also the traditional way to implement AA trees), we are going to assume every node has a variable called 'level' which stores the number of left links that must be followed until we reach the 'null' pointer. This means the level of each leaf is one. A complete set of the requirements for an AA tree can now be defined :

1. Every node of level greater than one must have a right child with its level either being equal to, or being one less than the level of the node.
2. When a node has a grandchild, it may not have the same level.

Only two operations are needed for maintaining balance in an AA tree. These operations are called skew and split. Skew is a right rotation when an insertion or deletion creates a left red link. Split is a conditional left rotation when an insertion or deletion creates two consecutive red links.

void Skew (struct node *oldparent) { struct node *newp = oldparent->left;

if (oldparent->parent->left == oldparent) oldparent->parent->left = newp; else oldparent->parent->right = newp; newp->parent = oldparent->parent; oldparent->parent = newp;

oldparent->left = newp->right; if (oldparent->left) oldparent->left->parent = oldparent; newp->right = oldparent;

oldparent->level = oldparent->left ? oldparent->left->level + 1 : 1; }

int Split (struct node *oldparent) { struct node *newp = oldparent->right;

if (newp && newp->right && newp->right->level == oldparent->level) { if (oldparent->parent->left == oldparent) oldparent->parent->left = newp; else oldparent->parent->right = newp; newp->parent = oldparent->parent; oldparent->parent = newp;

oldparent->right = newp->left; if (oldparent->right) oldparent->right->parent = oldparent; newp->left = oldparent; newp->level = oldparent->level + 1; return 1; } return 0; }

Insertion

Insertion starts with a normal basic binary search tree insertion, after which rebalancing is performed. If a right child increases in level (either because the new node was inserted to its left, or because its left child's level increased, or because it got a new left child with a higher level) then the possibility of 2 consecutive red nodes is handled with split (which may in turn cause the level of the new parent to increase).

If a node's level should increase, a skew is performed. Then care must be taken because either the node's old parent (now child) or its old sibling (new grandchild) could have been a red node. Then we are back to the above situation where a split must be performed. It can all be handled nicely with a loop :

void RebalanceAfterLeafAdd (struct node *n) { // n is a node that has just been inserted and is now a leaf node. n->level = 1; n->left = NULL; n->right = NULL; for (n = n->parent; n != &root; n = n->parent) { if (n->level != (n->left ? n->left->level + 1 : 1)) { Skew (n); if (!n->right || n->level != n->right->level) n = n->parent; } if (!Split (n->parent)) break; } }

AA trees are easier to implement with a sentinel node at the end of the tree rather than a null pointer because there are fewer cases to test for, but it is relatively simple to convert sentinel code to null terminated code. Whatever is used, it only affects the implementation of skew and split.

Deletion

If the node is not a leaf node, we find one that appears just before or just after it in the ordering. The properties of an AA tree guarantees that it is possible. Then we swap the two and delete the leaf. For a left child, its parent's level needs to decrease and for a right child, we must make sure there are no double red nodes.

The difficult case occurs when seven elements (a-b-c-d-e-f-g) are stored in the tree below and we want to delete 'a'.

b,2 / a,1 e,2 / c,1 f,1 \ d,1 g,1

The numbers indicate the levels. After removing 'a', we split b-e-f and get

e,2 / b,1 f,1 \ c,1 g,1 d,1

Then we split b-c-d and get

e,2 / c,2 f,1 / \ b,1 d,1 g,1

Then we finish by skewing c-e-f : c,2 / b,1 e,2 / d,1 f,1 g,1

The complete algorithm in C looks like this :

void Remove (struct node *n) { struct node *leaf = n, *tmp;

if (n->left) { for (leaf = n->left; leaf->right; leaf = leaf->right) {} } else if (n->right) leaf = n->right;

tmp = leaf->parent == n ? leaf : leaf->parent; if (leaf->parent->left == leaf) leaf->parent->left = NULL; else leaf->parent->right = NULL;

if (n != leaf) { if (n->parent->left == n) n->parent->left = leaf; else n->parent->right = leaf; leaf->parent = n->parent; if (n->left) n->left->parent = leaf; leaf->left = n->left; if (n->right) n->right->parent = leaf; leaf->right = n->right; leaf->level = n->level; }

for (; tmp != &root; tmp = tmp->parent) { if (tmp->level > (tmp->left ? tmp->left->level + 1 : 1)) { tmp->level--; if (Split (tmp)) { if (Split (tmp)) Skew (tmp->parent->parent); break; } } else if (tmp->level <= (tmp->right ? tmp->right->level + 1 : 1)) break; else { Skew (tmp); if (tmp->level > tmp->parent->level) { Skew (tmp); Split (tmp->parent->parent); break; } tmp = tmp->parent; } } }

Performance

The performance of an AA tree is equivalent to the performance of a red-black tree. While an AA tree makes more rotations than a red-black tree, the simpler algorithms tend to be faster, and all of this balances out to result in similar performance. A red-black tree is more consistent in its performance than an AA tree, but an AA tree tends to be flatter, which results in slightly faster search times.

See also

• Red-black tree
• B-tree
• AVL tree

References

• Complete sourcecode for the above
• A. Andersson. Balanced search trees made simple
• A. Andersson. A note on searching in a binary search tree

External links

• AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
• Thorough tutorial with lots of code
• Practical implementation
• Object Oriented implementation with tests
• Comparison of AA trees, red-black trees, treaps, skip lists, and radix trees