AVL trees: balance factor and rotations

The binary search tree (BST) you saw last week is nice but fragile. If you insert keys in sorted order (1, 2, 3, …), the tree turns into a chain to the right and search becomes O(n). The AVL tree (Adelson-Velsky and Landis) is the first self-balancing BST that solves this problem. Almost every exam has the same question: “Insert these keys in order into an empty AVL tree and draw the final tree.” Someone who knows the four rotations on this page by their logic, not by memory, will not miss this question.

Golden rules:

1. The AVL rule: at every node, the heights of the left and right subtrees differ by at most 1.
2. Height: an empty tree is -1, a leaf is 0. The balance factor is bf = height(left) - height(right).
3. Go up after inserting. Stop at the first (deepest) node whose bf is +2 or -2 and fix it. In insertion one fix is enough.
4. The direction question: which two steps did the new key take from that node? Left-left, right-right, left-right, right-left. The names of the four cases come from here.

Height and balance factor

The height of a node is the number of edges on the path to its farthest leaf. Always compute it from the bottom up:

$height(t) = 1 + \max(height(t.left),\ height(t.right)), \qquad height(null) = -1$

        30  h=2, bf=1-0=1
       /  \
     20    40   h(20)=1 bf=1, h(40)=0
    /
  10            h=0, bf=0

This tree is AVL: all bf values are -1, 0 or 1. If you insert 5 under 10, the bf of 20 becomes 2 and the rule is broken.

PITFALL · do not confuse height with depth. Depth is counted from the root down, height from the leaf up. The bf computation always uses height. Some sources call a leaf 1; then all values shift by 1 but the bf comes out the same. In the exam, check the instructor’s definition.

Why O(log n)?

If you want to build an AVL tree of height h with the fewest nodes, you make one subtree height h-1 and the other h-2 (a difference of 1 is allowed). From this:

$N(h) = N(h-1) + N(h-2) + 1, \qquad N(0)=1,\ N(1)=2$

This sequence grows exponentially like Fibonacci. If the number of nodes grows exponentially with the height, the height grows logarithmically with the number of nodes: $h < 1.44 \log_2 n$. Search, insert and delete take as many steps as the height, so all are O(log n). A rotation changes only a few pointers, O(1).

The four cases and rotations

Insertion is done like a normal BST insertion. Then the ancestors of the inserted leaf are checked going up. Call the first unbalanced node k. The two steps that the new key took after k determine the case.

LL and RR: single rotation

In the LL case the new key went into the left subtree of the left child of k. The left child (k1) moves up and k2 moves down to the right. X, Y, Z are subtrees:

LL: right rotation at k2
        k2                k1
       /  \              /  \
     k1    Z    ==>     X    k2
    /  \                    /  \
   X    Y                  Y    Z

Note: the subtree Y on the right of k1 goes to the left of k2. Every key in Y is larger than k1 and smaller than k2. So the BST order is preserved in its new place. The inorder sequence X, k1, Y, k2, Z is the same in both drawings.

RR is the mirror image: a left rotation at k1, the right child k2 moves up to the root, and the left subtree of k2 goes to the right of k1.

RR: left rotation at 10 (10, 20, 30 inserted)
  10                  20
    \                /  \
     20     ==>    10    30
       \
        30

LR and RL: double rotation

In the LR case the new key went to the right of the left child of k. A single right rotation does not help here; it only moves the slant to the other side. The solution takes two steps: first a left rotation at the left child (which turns the case into LL), then a right rotation at k. In the end the middle node (between k1 and k3) goes to the top.

LR: 30, 10, 20 inserted
    30          30           20
   /           /            /  \
  10    ==>   20    ==>   10    30
    \        /
     20     10
  left at 10   right at 30

RL is the mirror image: first a right rotation at the right child, then a left rotation at k.

TIP · the shortcut for a double rotation. Sort k, its child and its grandchild (the three nodes on the path of the new key). The median value becomes the new root, the smaller goes left, the larger goes right. The old two subtrees of the grandchild are distributed to the left and right sides in order.

AVL insertion in Java

The node stores its own height. Insertion is recursive: on the way back, each node updates its height and rebalances if needed. The balance method compares heights, so it works for both insertion and deletion.

static class AvlNode {
    int key, height;          // leaf: height = 0
    AvlNode left, right;
    AvlNode(int key) { this.key = key; }
}

static int height(AvlNode t) { return t == null ? -1 : t.height; }

static void update(AvlNode t) {
    t.height = 1 + Math.max(height(t.left), height(t.right));
}

static AvlNode rotateRight(AvlNode k2) {   // LL
    AvlNode k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    update(k2);
    update(k1);
    return k1;
}

static AvlNode rotateLeft(AvlNode k1) {    // RR
    AvlNode k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    update(k1);
    update(k2);
    return k2;
}

static AvlNode insert(AvlNode t, int x) {
    if (t == null) return new AvlNode(x);
    if (x < t.key) t.left = insert(t.left, x);
    else if (x > t.key) t.right = insert(t.right, x);
    else return t;                         // duplicates are not inserted
    return balance(t);
}

static AvlNode balance(AvlNode t) {
    update(t);
    int bf = height(t.left) - height(t.right);
    if (bf > 1) {
        if (height(t.left.left) < height(t.left.right))
            t.left = rotateLeft(t.left);   // LR: first turn it into LL
        return rotateRight(t);
    }
    if (bf < -1) {
        if (height(t.right.right) < height(t.right.left))
            t.right = rotateRight(t.right); // RL
        return rotateLeft(t);
    }
    return t;
}

Usage is always of the form root = insert(root, x);. Because a rotation changes the root of the subtree, assigning the returned value is required.

Worked example: 15, 20, 24, 10, 13, 7, 30, 36, 25

Let’s insert these nine keys into an empty AVL tree. At each step follow the path and check bf going up.

+15, +20: no problem. +24: the bf of 15 is -2, the path is right-right: RR, a left rotation at 15.

  15                 20
    \               /  \
     20    ==>    15    24
       \
        24

+10: to the left of 15, balanced. +13: 13 → 20 → 15 → 10 → right. The bf of 15 is 2 (left height 1, right -1). The path is left-right: LR. Left at 10, right at 15. 13 comes to the middle.

       20                   20
      /  \                 /  \
    15    24    ==>      13    24
   /                    /  \
  10                  10    15
    \
     13

+7: 7 → 20 → 13 → 10 → left. Look upward: the bf of 10 is 1, the bf of 13 is 1, the bf of 20 is height(13) - height(24) = 2 - 0 = 2. The path (from 20) is left-left: LL, a right rotation at 20. 13 moves up to the root, and the right child of 13, which is 15, goes to the left of 20.

         13
        /  \
      10    20
     /     /  \
    7    15    24

+30: to the right of 24, balanced. +36: the bf of 24 is -2, right-right: RR, a left rotation at 24, 30 moves up.

         13
        /  \
      10    20
     /     /  \
    7    15    30
              /  \
            24    36

+25: 25 → 13 → 20 → 30 → 24 → right. The bf of 24 is -1, the bf of 30 is 1, the bf of 20 is 0 - 2 = -2. The path (from 20) is right-left: RL. First a right rotation at 30 (24 moves up), then a left rotation at 20 (24 takes the place of 20).

          13
        /    \
      10      24
     /       /  \
    7      20    30
          /     /  \
        15    25    36

Program output (the level order after each insertion and the fix that was made):

+15 -> 15
+20 -> 15 20
+24 -> 20 15 24   [RR at 15]
+10 -> 20 15 24 10
+13 -> 20 13 24 10 15   [LR at 15]
+7 -> 13 10 20 7 15 24   [LL at 20]
+30 -> 13 10 20 7 15 24 30
+36 -> 13 10 20 7 15 30 24 36   [RR at 24]
+25 -> 13 10 24 7 20 30 15 25 36   [RL at 20]

The height of the final tree is 3. The bf of the root is 1 - 2 = -1, so the rule holds.

Deletion in brief

Deletion from an AVL tree is first a normal BST deletion (with two children, the smallest of the right subtree, the inorder successor, takes its place). Then balance is called at every node from the deleted position up to the root. The difference from insertion: in deletion a rotation can reduce the height of the subtree, and the imbalance can move upward. So more than one rotation up to the root may be needed. The choice of case is again made by looking at the heights of the children; the balance method above already does this. The time is again O(log n).

Common mistakes

        20
       /  \
     10    30
    /  \
   5    15
  /
 3

static AvlNode rotateRight(AvlNode k2) {
    AvlNode k1 = k2.left;
    k2.left = k1.right;   // the middle subtree (Y) moves to k2
    k1.right = k2;
    k2.height = 1 + Math.max(height(k2.left), height(k2.right));
    k1.height = 1 + Math.max(height(k1.left), height(k1.right));
    return k1;            // the new root; the caller writes t = rotateRight(t)
}