AVL Trees

Keeping Binary Search Trees balanced

Overview

The \( O( \log n ) \) behavior of a binary search tree is only possible if the tree is balanced. Each element added to a BST increases the length of one branch. If the same branch is continually extended, we end up with an unbalanced tree. In order to keep the tree balanced, we may need to reconfigure the tree.

The order in which we add elements to the BST will determine the branch structure.

Tree Rotations

If the smallest or largest element is added to the BST first, both remaining elements must be added to the same side of the tree. We can reconfigure the tree by "rotating" around a given node. A rotation involves modifying the child and parent references of the appropriate nodes.

Here

• w is a subtree where all the values are less than A
• x is a subtree where all the values are greater than A and less than B
• y is a subtree where all the values are greater than B and less than C
• z is a subtree where all the values are greater than C

To complete the rotation, the following references must be updated:

• C's parent and left child references
• B's parent and right child references
• The parent reference for the root of y (if it exists)
• The left or right child reference of C's parent (if it exists)

We call this a "right rotate on C."

We can develop rotations for all possible configurations of a BST.

Notice that in order to get from the "bent" branch to the balanced tree we need to do two rotations — first to get a straight branch, and then to balance.

AVL Trees

An AVL tree is BST with rules to help keep the tree balanced. We introduce the concept of a balance factor which is defined as \( bf = h_r - h_l \) where \( h_r \) is the height of the right subtree and the meaning of \( h_l \) is easy to guess. The balance factor can be calculated for each node in the tree.

In an AVL tree, \( | bf | \le 1 \) , i.e., every node has a balance factor of -1, 0, or 1. Whenever we add or remove from an AVL tree, we must ensure that the balance factor remains in range for all nodes in the tree.

Rebalancing an AVL Tree

Consider all permutations of adding A, B, and C to an empty AVL tree. Which permutations require rebalancing?

Assuming subtrees w, x, y, and z are all the same height, we can show all possible configurations that may require rotations.

• Left-Left Tree — Right rotate on C
• Right-Right Tree — Left rotate on A
• Left-Right Tree — Left rotate on A folled by right rotate on C
• Right-Left Tree — Right rotate on C folled by left rotate on A

Adding to an AVL Tree

We find the location where the element should be added exactly the same way as a BST. Once added, we calculate the balance factor for the node's parent, grand parent, great grand parent, ..., all the way up to the root. Upon the first encounter of a balance factor out of range, we perform the appropriate rotations.

Whenever a rotation is needed, repeat balance factor checks all the way up to the root. Since each rotation requires a constant amount of work and the total number of rotations is no more than two per level of the tree, rebalancing an AVL tree is \( O( \log n ) \).