AVL Trees

We're going to learn about two types of self-balancing trees in this class, defined as "trees that always meet some definition of balanced." There's a wide variety of these, and I think they're pretty cool.

AVL Trees define "balanced" as "the heights of the subtrees of any node can differ by at most one." Note, this is NOT the same as "the tree is as short as possible." For example, consider this tree:

This tree is NOT complete (meaning totally filled in). However, by the definition of AVL trees, it IS balanced. The height of an AVL tree is still \(O(\log(n))\).

Rotations

AVL trees work by identifying when to make rotations. The following two illustrations demonstrate a left rotation at the light red node.

The triangles represent entire subtrees; note that the red subtree contains values less than the pink node, the blue subtree contains values greater than the blue node, and the purple triangle contains values smaller than the blue, but larger than the pink.

The important thing is that in both of these images, that is still true; both are valid binary search trees. The code for a left rotation is as follows:

Node lRotate(Node n) { // n is the red node above
  Node right = n.getRight(); // right is the blue node above
  Node temp = right.getLeft(); // temp is the root of the purple subtree
  right.setLeft(n);
  n.setRight(temp);
  return right;
}

To see a right rotation, view the images above in backwards order. To implement it, take the code for lRotate, and swap right and left.

Adding to an AVL tree

The idea that makes AVL trees possible to quickly implement is that nodes are modified to include the height of the subtree rooted at that node. So, leaves have a height of 1, and all other nodes have a height of \(\max(n.left.height, n.right.height)+1\).

We also define balance, where balance = n.right.height-n.left.height.

If, at any point, balance becomes -2 or 2, we must perform at least one rotation to rebalance the tree. There are four cases to consider:

(balance(n) == 2 && balance(n.right) == 1) Left rotate at n.

(balance(n) == 2 && balance(n.right) == -1) Right rotate at n.right, then left rotate at n.

The other two cases are the mirror images of the above two.

Getting an element of an AVL Tree

This is no different from find or get in any other binary search tree.

Removing an element from an AVL Tree

The basic algorithm is identical to that of removing from other binary search trees. However, just before returning a node, that node should be checked to see if it is balanced. If it is not, balance it.

There are two additional cases that might occur with removal in an AVL tree that will not occur with insertion:

(balance(n) == 2 && balance(n.right) == 0) Left rotate at n.

(balance(n) == -2 && balance(n.left) == 0) Right rotate at n.