introduction to algorithms - aa trees

May 30, 2009

aa trees are a form of balanced trees similar to red-black trees. they're invented by arne anderson(that's why they're called aa trees). original paper can be found here. they're considered as variant of red-black trees. however unlike red-black trees, they're implemented with the idea of a level(think about it as a balance factor of an avl tree) instead of a color. they have the following properties:

- the level of a leaf node is 1
- the level of a left node is less than its root
- the level of a right node is less than or equal to its root
- the level of a right node's node is less than its root's root
- every node of level greater than one must have two children.

the advantage of an aa-tree compared to red-black trees is that the half of the restructuring cases are eliminated, so the deletion operation is considerably simplified.

to balance an aa-tree, two methods named split, and skew are needed. compared to red-black trees it's much simpler. skew rotates to right when an insertion or deletion operation creates a left horizontal link.

the key methods of aa trees are skew, and split methods. let's start with skew method;

  Node skew(Node root) {
    if(root.left.getLevel() == root.getLevel()) {
      root = rotateLeft(root);
    }
    return root;
  }

  Node rotateLeft(Node root) {
    Node temp = root.left;
    root.left = temp.right;
    temp.right = root;
    return temp;    
  }

and here's the split method;

  Node split(Node root) {
    if(root.right.right.getLevel() == root.getLevel()) {
      root = rotateRight(root);
      root.setLevel(root.getLevel()+1);
    }
    return root;
  }

  Node rotateRight(Node root) {
    Node temp = root.right;
    root.right = temp.left;
    temp.left = root;
    return temp;
  }

insertion

insertion begins with the same procedures of a binary search tree. if a horizontal node appears, skew method will be performed, and if two horizontal right nodes appears, split method will be performed.

so here's the insertion method;

  Node insertRec(Node root, int data) {
    if(root == null) {
      return new Node(data);
    } else if(data < root.getData()) {
      root.left = insertRec(root.left, data);
    } else if(data > root.getData()) {
      root.right = insertRec(root.right, data);
    } else {
      throw new DuplicateItemException(data);
    }
    
    root = skew(root);
    root = split(root);
    return root;
  }

  void insert(int data) {
    root = insertRec(root, data);
  }

insert is similar to bst's insert method, unlike bst we need to balance the tree.

searching

search function is similar to bst's as well

  Node search(Node root, int data) {
    if(root == null) return null;
    if(data == root.getData())
      return root;
    else if(data <  root.getData())
      return search(root.left, data);
    else
      return search(root.right, data);
  }

aa trees and red-black trees are almost use identical number of rotation when inserting into tree. however, the remove process of red-black tree uses less rotation than aa tree.

aa tree is a simple balanced tree, it's not as famous as red-black trees or avl trees but it's simpler to implement.

further study can be found here.

faruk akgul

introduction to algorithms - aa trees

insertion

searching