Arne Andersson Tree (AA Tree)

When studying balanced binary search tree, most of us are introduced to the AVL Tree or the Red-Black Tree. However, implementing a Red-Black Tree from scratch can be a nightmare due to numerous edge cases in rebalancing. Enter the AA Tree (named after its inventor, Arne Anderson) - a variation of the Red-Black Tree that is significantly easier to code and maintain.

In this post, we will explore the core concepts of the AA Tree, how to define its structure, and how to implement some operations from scratch using raw C++ pointers.

1. What is AA Tree?

An AA Tree simplifies the Red-Black Tree by eliminating left-leaning red edges. Instead of colors (Red or Black), it uses the concept of a level for each node. We have some definitions when working with AA Tree.

Understanding Levels and Links

In an AA Tree, the level is a specific property assigned to each node.

• The level of every leaf node is one.
• The level of any node lacking a left child is also strictly one.
• The level of a node with a left child is always exactly one greater than the level of that left child.

Nodes are connected by two types of links:

• Normal Link: A connection where the child’s level is one less than the parent’s.
• Horizontal Link: A connection where both the parent and the child share the exact same level.

Strict Properties of an AA Tree

By applying these concepts, an AA Tree must adhere to these precise rules:

1. Only right horizontal links are allowed. The level of a right child can be equal to or one less than its parent. Conversely, the level of a left child must strictly be one less than its parent, meaning left horizontal links are forbidden.
2. There cannot be two consecutive right horizontal links.
3. Any node with a level strictly greater than 1 must possess exactly two children.
4. If a node does not have a right horizontal links, both of its children must be at the same level.

• In the image above, node 30 is the root of the AA tree. The red arrows represent the horizontal links, connecting parent nodes to their right children at the exact same level.
• Nodes 5, 10, 20, 35, 40, 55, 65, 80, and 90 are all leaf nodes; therefore, they have a level of 1.
• Nodes 15, 50, 60, and 85 have a level of 2 because they all have a left child at level 1.
• Similarly, nodes 30 and 70 have a level of 3.

2. Implementing the AA Tree

To maintain the tree, we only need a basic node structure containing pointers to the children, the data, and an integer representing the level. We will handle memory management manually to understand exactly how the nodes are linked.

#include <iostream>

struct TreeNode {
    int data;
    int level;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), level(1), left(nullptr), right(nullptr) {} 
};

To keep the tree balanced, the AA Tree relies on two fundamental utility operations:

• skew: Fixes the issue of a left horizontal link (a left child with the same level as its parent) by performing a right rotation.
• split: Fixes the issue of two consecutive right horizontal links (a right grandchild with the same level as its grandparent) by performing a left rotation and increasing the level of the new root.

Skew

• Node C is the leftchild of node N.
• Node C and node N share the same level, creating a left horizontal link.
• Skew operation is used by right rotation at node C and node N.

❮ ❯

This is the source code of skew operation using C++ pointers:

TreeNode* skew(TreeNode* root) {
  if (root == nullptr || root->left == nullptr) 
    return root;

  if (root->left->level == root->level) {
    TreeNode* leftChild = root->left;
    root->left = leftChild->right;
    leftChild->right = root;
    return leftChild;
  }
  return root;
}

Split

This is the source code of split operation using C++ pointers:

TreeNode* split(TreeNode* root) {
  if (root == nullptr || root->right == nullptr || root->right->right == nullptr) 
    return root;

  if (root->level == root->right->right->level) {
    TreeNode* rightChild = root->right;
    root->right = rightChild->left;
    rightChild->left = root;
    rightChild->level += 1;
    return rightChild;
  }
  return root;
}

3. AA Tree operations

Insertion

Inserting a node is straightforward. We perform a standard BST insertion. As we return from the recursive calls, we apply skew followed by split to restore the AA Tree

Here is the source code of insert operation using C++ pointers (using non-returning function):

void insert(TreeNode*& root, int val) {
  if (root == nullptr)
    return new TreeNode(val);

  //Standard BST insertion
  if (val < root->data) {
    insert(root->left, val);
  } else if (val > root->data) {
    insert(root->right, val);
  } else return root;

  //Rebalance
  root = skew(root);
  root = split(root);
}

Deletion

Deletion is slightly more complex. After removing the node via standard BST deletion rules (using the in-order successor or predecessor), the tree’s levels might be violated. We must adjust the levels and then perform a specific sequence of skew and split operations.

Here is the source code of remove operation using C++ pointers (using non-returning function):

void remove(TreeNode*& root, int val) {
  if (root == nullptr) return root;

  //Standard BST deletion
  if (val < root->data) {
    remove(root->left, val);
  } else if (val > root->data) {
    remove(root->right, val);
  } else {
    if (root->left == nullptr) {
      TreeNode* temp = root;
      root = root->right;
      delete temp;
    } else if (root->right == nullptr) {
      TreeNode* temp = root;
      root = root->left;
      delete temp;
    } else {
      Node* maxLeft = findMax(root->left);
      root->data = maxLeft->data;
      remove(root->left, maxLeft->data);
    }
  }

  //Update levels
  int expectedLevel = 1;
  if (root->left != nullptr && root->right != nullptr) {
    expectedLevel = std::min(root->left->level, root->right->level) + 1;
  }
  
  if (expectedLevel < root->level) {
    root->level = expectedLevel;
    if (root->right != nullptr && expectedLevel < root->right->level) {
      root->right->level = expectedLevel;
    }
  }

  //Rebalance using 3 skews and 2 splits
  root = skew(root);
  if (root->right != nullptr) {
    root->right = skew(root->right);
    if (root->right->right != nullptr) {
      root->right->right = skew(root->right->right);
    }
  }

  root = split(root);
  if (root->right != nullptr) {
    root->right = split(root->right);
  }

  return root;
}