AVL Trees

Example: work it out

Look at node 20: its left child 10 has height 0, and its right child 30 has height 0. So its balance factor is 0 − 0 = 0.

Look at node 40: its left subtree (starting at 20) has height 1. Its right subtree (starting at 60) has height 0. So 1 − 0 = +1. It leans left a little, but that is allowed.

Look at leaf 60: both children are empty (height −1). So −1 − (−1) = 0. Every leaf has balance factor 0.

Example 2: a missing child counts as −1

Insert 10, 20, 30 into a plain BST. You get this chain (you will meet it again in Part 4 as the RR case):

Work from the bottom up. The table shows each node's left height, right height, and balance factor:

Node 10 is −2: unbalanced, because its right side is two levels taller than its left. Notice that 10's balance factor (−2) is not its height (2): the height measures one side going down, the balance factor compares two sides.

A right rotation, slowly

Here is a tree that needs a fix. 10 was just inserted, and now 40 has a balance factor of +2: its left side is two levels taller than its right. A right rotation at 40 fixes it in three moves:

1. 30 moves up into 40's old spot.
2. 40 moves down to become 30's right child.
3. But 30's right spot already held 35. Now 40 is there, so 35 is left floating and needs a new spot. It goes to 40's left, which is empty (40 lost its left child, 30, in move 1).

Why 40's left, and nowhere else? Find 35's spot the same way as BST insertion : 35 is bigger than 30, so go right to 40; 35 is smaller than 40, so look left: empty, so 35 goes there. It is the only spot that keeps the BST rule, so there is exactly one correct place.

In the Java code (Part 7), 35 is not inserted again from the top. One line moves it, together with anything under it, straight to 40's left. It lands in the same spot.

Check: the in-order list before is 10, 20, 30, 35, 40, 50. After, it is still 10, 20, 30, 35, 40, 50. And the balance factors are back in −1 to +1.

A left rotation

A left rotation is the same three moves with left and right swapped. Here, 50 was just inserted, and 20 has a balance factor of −2: its right side is two levels taller. A left rotation at 20 fixes it:

1. Its right child, 30, moves up into 20's spot.
2. 20 moves down to become 30's left child.
3. 30's old left child, 25, moves to 20's empty right spot (25 is bigger than 20 and smaller than 30).

Check: the in-order list is 10, 20, 25, 30, 40, 50 before and after, and every balance factor is back in −1 to +1.

The four cases

When a node becomes unbalanced, we look at the path from that node toward the value we just inserted. The first two moves on that path give the case its name. There are four types of cases:

In the small trees: red = the unbalanced node (±2), orange = the value just inserted.

Why a zigzag needs two rotations

Take the LR case: insert 30, 10, 20. The path from 30 goes left, then right: a zigzag. One right rotation at 30 does not work here: it only flips the zigzag the other way, and the tree is still unbalanced.

So the fix starts one level lower, at the child 10. Rotation 1 is a normal left rotation , only done at 10: 20 (10's right child) moves up into 10's spot, and 10 moves down to become 20's left child. With just two nodes, it looks like 20 and 10 swapped places, but it is the same three moves. The BST rule decides the result: 10 < 20 < 30, so after the rotation the three values sit in a straight line going left. That is the LL case, and LL needs one right rotation:

RL is the same with left and right swapped: a right rotation at the child, then a left rotation at the unbalanced node. The panel below shows all four cases step by step.

1. The node remembers its height

class TreeNode {
  int data;
  int height;   // NEW: height of this node
  TreeNode left;
  TreeNode right;

  TreeNode(int value) {
    data = value;
    height = 0;  // a new node is a leaf
  }
}

2. Three small helpers

// height of a node; an empty spot is -1
static int height(TreeNode node) {
  if (node == null) {
    return -1;
  }
  return node.height;
}

// recompute height from the two children
static void updateHeight(TreeNode node) {
  node.height = 1 + Math.max(height(node.left),
                             height(node.right)); // the bigger one
}

// balance factor = left height - right height
static int balance(TreeNode node) {
  return height(node.left) - height(node.right);
}

These match Part 2 exactly: a leaf is 0, an empty spot is −1, and the balance factor is left minus right.

3. The right rotation

static TreeNode rotateRight(TreeNode z) {
  TreeNode y = z.left;      // y will move up
  TreeNode moved = y.right; // changes parent
  y.right = z;              // z goes down, right
  z.left = moved;
  updateHeight(z);          // z first: it is lower now
  updateHeight(y);
  return y;                 // y is the new top
}

Compare rotateRight with the right rotation picture in Part 4 : z is 40, y is 30, and moved is 35. The method returns the new top, so whoever called it can connect it back to the tree.

rotateLeft is the same code with every left and right swapped (a mirror image), and insertRec below calls it too. You will write it yourself in the coding task at the end of this part.

4. Insert, then fix on the way back up

static TreeNode insertRec(TreeNode node, int value) {
  // Step 1: normal BST insert
  if (node == null) {
    return new TreeNode(value);
  }
  if (value < node.data) {
    node.left = insertRec(node.left, value);
  } else if (value > node.data) {
    node.right = insertRec(node.right, value);
  } else {
    return node;  // duplicate: do nothing
  }

  // Step 2: update height, check balance
  updateHeight(node);
  int b = balance(node);

  // Steps 3-4: name the case and rotate
  if (b > 1 && value < node.left.data) {   // LL
    return rotateRight(node);
  }
  if (b < -1 && value > node.right.data) { // RR
    return rotateLeft(node);
  }
  if (b > 1 && value > node.left.data) {   // LR
    node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  if (b < -1 && value < node.right.data) { // RL
    node.right = rotateRight(node.right);
    return rotateLeft(node);
  }
  return node;  // balanced: nothing to fix
}

You call it the same way as before: root = insertRec(root, 25);