Lecture 9 - Height-Balanced Binary Search Trees

3.2. Height-Balanced Binary Search Trees

called AVL trees after their Russian inventors Adelson-Velskii and Landis.

It can be proved that in AVL trees: Height < 1.5logN

So if we restrict ourselves to AVL trees the crucial operations of searching, inserting, and deleting are absolutely guaranteed to be O(logN) - providing that height-balance can be maintained in O(logN) time. It can!

In working with AVL trees, operations must preserve two properties:

(height balanced) heights of left and right subtrees are within 1
(BST) values in left subtree are smaller than root value, which is smaller than the values in the right subtree.

We will look at the INSERTION operation briefly in this lecture. Deletion follows a similar strategy. For the interested student, a full description of the INSERTION algorithm is given below, after the end of the lecture material.

The INSERTION strategy is this:

Add the new value in the tree where it belongs (normal BST insertion).
Check if all subtrees are still height-balanced. If they are not, re-balance the tree by changing its shape (i.e. moving around nodes or even whole subtrees).

This is very typical of operations on balanced structures: first you do the operation without regard for the balance, then you check the balance and repair it if necessary.

Let's look at some simple examples. Suppose we start with the empty tree.

Insert 3:

Insert 6:

Insert 2:

So far things have been easy! Insert 1:

Insert 0:

The subtrees under `2' are not height balanced. Compute the balance at each node to see this. This is the deepest `unbalanced' node. Fix it.

When we have an imbalance, one of the subtrees is tall or long the other subtree is short. To re-balance, we need to shorten the tall side and/or lengthen the short side. This can be done by what is called a rotation. In our example, `1' rotates up into `2's position, `2' goes down on the opposite side:

Now the left side is 1 shorter and the right side is 1 taller. This re-balanced subtree is joined back to its place in the main tree.

Continuing on, suppose we now insert -1.

Computing the balance at each node, we see that everything is balanced except the top node... so we rotate the tall subtree up and the root down in the opposite direction.

But what do we do with `1's right subtree?

Answer: it becomes the left subtree of the node that rotated down.

Rotation is the operation that is used to restore balance in an AVL tree. For INSERTION, it can be shown that you never need to do more than two rotations (one rotation is not always enough) to restore balance, no matter how large the tree is. For DELETE, rotation is also used to restore balance, but in this case there are circumstances in which fixing the balance in one part of the tree creates an imbalance higher up in the tree. So, in the worst case, you might have to do O(height) rotations during a single DELETE operation.

That is all we have time to say about height-balanced binary search trees. The rotation operation itself is very fast and simple, and is an excellent illustration of the usefulness of the PRUNE and JOIN operations.