AVL Trees

Mathematical Definition: If T is a nonempty binary search tree, then T is an AVL tree if and only if its left and right subtrees are AVL trees and |left height – right height| < 1.

"In English" definition: A binary search tree that is almost balanced, but not completely balanced.

The AVL tree was discovered by two Russian mathematicians, Adelson-Velskii and Landis, in 1962.

Representation of an AVL tree

AVL trees are normally represented using the linked representation. To make insertion and deletion easier, a balance factor bf is associated with each node. The balance factor of a node x (bf(x)) is defined as:

bf(x)  =  height left subtree of x  –  height of right subtree of x

The possible balance factors are –1, 0, and 1.

Insertion into an AVL Search Tree

If the logic that was used previously to insert a node into a binary search tree is used to try and insert a node into an AVL tree, the tree may no longer be AVL.

For example, assume the following tree:

Now suppose that the node DUS is inserted using the old logic. The resulting tree is:

It contains nodes with balance factors other than –1, 0, and 1, therefore it is no longer an AVL tree. This new tree is unbalanced.

In order to restore balance, some of the subtrees will be rotated.

There are 4 types of rotations:

1. Single left rotation
2. Single right rotation
3. Right-Left rotation
4. Left-Right rotation

Single Left rotation

This rotation is used when a node is inserted in the right subtree of the right child (B) of the nearest ancestor (A) with balance factor -2.

In order to apply this rotation:

1. Change the parent of A to point to B
2. Set the right link of A equal to the left link of B
3. Set the left link of B to point to A

Single Right rotation

This rotation is used when a node is inserted in the left subtree of the left child (B) of the nearest ancestor (A) with balance factor +2.

In order to apply this rotation:

1. Change the parent of A to point to B
2. Set the left link of A equal to the right link of B
3. Set the right link of B to point to A

Right-Left rotation

This rotation is used when a node is inserted in the left subtree of the right child (B) of the nearest ancestor (A) with balance factor -2.

In order to apply this rotation:

1. Set the right link of A to point to the root (C) of the left subtree of B
2. Set the left link of B equal to the right link of C
3. Set the right link of C to point to B
4. Change the parent of A to point to C
5. Set the right link of A equal to the left link of C
6. Set the left link of C to point to A

Left-Right rotation

This rotation is used when a node is inserted in the right subtree of the left child (B) of the nearest ancestor (A) with balance factor +2.

In order to apply this rotation:

1. Set the left link of A to point to the root (C) of the right subtree of B
2. Set the right link of B equal to the left link of C
3. Set the left link of C to point to B
4. Change the parent of A to point to C
5. Set the left link of A equal to the right link of C
6. Set the right link of C to point to A

Building an AVL tree using insertions and rotations:

Insert the keys: ORY, JFK, BRU, DUS, ZRH, MEX, ORD, NRT, ARN, GLA, HAD, ABC, GCM and ACE in the order given.