AVL Trees Intro

AVL Trees Intro video (15 minutes) (Spring 2021)

AVL trees are named for their creators, Adelson-Velskii and Landis.

AVL trees are binary search trees with a "balance condition".

Motivation

As we have noted before, unbalanced binary trees are not ideal. If you insert pre-sorted data, you end up with a linked list. All individual operations become O(n). You lose all benefits of O(log(n)) behavior that balanced BSTs offer.

Balance condition

For every node in an AVL tree, the height of the left and right subtrees can differ at most by 1.

This ensures that most tree operations (such as contains(), or find()) are O(log(n)).

Since this balance condition needs to be maintained as the BST changes, insert() and delete() may not always be O(log(n)).

Maintaining the balance condition involves changing the tree through a process called rotation. More info about this to come!

Visual examples

This tree is an AVL tree. For each node, the left and right subtrees differ in height by no more than 1. For example, 2's left subtree is of height 1. 2's right subtree is of height 2. 2 - 1 = 1.

            5
          /   \
         2      8
        / \    /
       1   4  7
          /
         3

This tree is NOT an AVL tree. The root node 7, has a left subtree of height 1, and a right subtree of height 3. 3 - 1 = 2. The difference in subtree heights is more than 1.

            7
          /   \
         2      8
        / \    
       1   4  
          / \
         3   5

Cases of Imbalance

Since each node has two children, there are a total of 4 cases of imbalance that may occur. We will demonstrate two cases. The other cases are mirror symmetrical versions of these two.

In these pictures, consider a, b, and c as nodes. Consider 1, 2, 3, and 4 as entire subtrees, from size 1 (a single node) to size n.

In each case, the following relations are true:

1 < a
a < 2 < b
b < 3 < c
c < 4

In other words, 1 < a < 2 < b < 3 < c < 4.

The "Left-Left" case (left subtree of left child grows)

In this case, c's left subtree has a height of 3, and c's right subtree has a height of 1. This is imbalanced. C is the node at which the imbalance occurs. B is the left child. A is the left subtree of B. Hence, left-left case.

        c
       / \
      b   4
     / \
    a   3
   / \
  1   2

The "Left-Right" case (right subtree of left child grows)

In this case, c's left subtree has a height of 3, and c's right subtree has a height of 1. This is imbalanced. C is the node at which the imbalance occurs. A is the left child. B is the right subtree of A. Hence, left-right case.

        c
       / \
      a   4
     / \
    1   b
       / \
      2   3

The balanced end goal for both cases:

        b
      /   \
    a       c
   / \     / \
  1   2   3   4

The other two cases of imbalance are:

"Right Right" case (right subtree of right child grows)

This mirrors the left-left case

"Right-Left" case (left subtree of right child grows)

This mirrors the left-right case

Thanks

Thanks to Brian Foster for writing up these notes based on the video lectures.