AVL rotations: LL, RR, LR and RL

Why this matters

A binary search tree is fast only while it stays bushy. If keys arrive in sorted order, the tree becomes a chain, and a search has to walk through every node. The lesson "Why sorted input makes a BST a chain" in this module shows how that happens.

An AVL tree is a binary search tree that repairs itself. It was invented in 1962 by two Soviet mathematicians, Georgy Adelson-Velsky and Evgenii Landis, and the name comes from their initials. After each insert or delete, the tree checks the nodes on the way back up and rotates a few of them when one side has grown too tall. A rotation is a local rearrangement of three or four pointers that keeps the keys in sorted order.

This lesson does the repairs by hand, one step at a time. The C++ program at the end of the lesson printed every trace shown here, except the examples in the Mistakes section, so you can compare your hand trace with its output line by line.

The balance factor

The height of a node is the number of nodes on the longest path from that node down to a leaf. A leaf has height 1. An empty tree has height 0. The height of any node is one more than the taller of its two children.

The balance factor of a node is the height of its left subtree minus the height of its right subtree. It is written bf. A leaf has bf 0, because both sides are empty. A node with only a left child has bf +1, because the left side has height 1 and the right side has height 0.

An AVL tree keeps the balance factor of every node at -1, 0 or +1. When an insert or delete pushes one node to +2 or -2, the tree is out of balance at that node, and a rotation fixes it.

The program prints each tree in this form:

(key:bf left right)

An empty child is printed as a dot. So (30:1 (20:0 . .) .) means: the root is 30, its balance factor is +1, its left child is 20 with bf 0 and no children, and it has no right child. A reader can rebuild the shape from this text alone.

Rotations

A right rotation at a node y moves its left child x up to take y's place. Node y becomes the right child of x. The right subtree of x moves across to become the left subtree of y. Those keys are between x and y in sorted order, so they still fit in their new place.

A left rotation is the mirror image. The right child moves up, the node becomes its left child, and the left subtree of the child moves across to become the right subtree of the node.

The four cases

When a node becomes unbalanced, look at two things. The first is the sign of its balance factor, which says which side is too tall. The second is the balance factor of the child on that side, which says where the extra height is. The two letters in each case name those two sides.

In LL and RR the new key went down the outside of the tree, the same side as the child's own heavy side. One rotation is enough.

In LR and RL the new key went down the inside of the tree. A single rotation would leave the tree still unbalanced, so the child is rotated first to turn the bent shape into a straight one. Then the root is rotated.

The program follows the same rule. When it finds a root with bf +2, it looks at the left child. If the child's bf is negative, the program first does a left rotation on that child, which is the LR case. Then it does a right rotation on the root. If the child's bf is 0 or positive, it does only the right rotation, which is LL. The messages LL at ...: no first step and RR at ...: no first step mean the program skipped the first rotation.

Worked example 1: LL with the keys 30, 20, 10

Insert the keys 30, 20 and 10 in that order.

LL
  insert 30
  tree: (30:0 . .)
  insert 20
  tree: (30:1 (20:0 . .) .)
  insert 10
    unbalanced at 30, bf 2: (30:2 (20:1 (10:0 . .) .) .)
    LL at 30: no first step
        rotate right at 30
  tree: (20:0 (10:0 . .) (30:0 . .))

Read it one step at a time.

After 30 the tree is one node, so bf is 0. After 20 the tree is 30 with a left child. The root has bf +1, which is still allowed.

After 10 the new node goes to the left of 20. Now node 20 has bf +1, and node 30 has bf +2. The root is out of balance. The program prints unbalanced at 30, bf 2.

The root's left child, 20, has bf +1, which is not negative. So this is the LL case, and no first step is needed. One right rotation at 30 moves 20 up. Node 30 becomes the right child of 20. The final tree has 20 at the root, with bf 0, and both children are leaves.

The rotation kept the keys in order. Before, the walk was 10, 20, 30. After, it is still 10, 20, 30.

The mirror case is RR. Insert 10, 20 and 30 and the same steps run with left and right swapped.

RR
  insert 10
  tree: (10:0 . .)
  insert 20
  tree: (10:-1 . (20:0 . .))
  insert 30
    unbalanced at 10, bf -2: (10:-2 . (20:-1 . (30:0 . .)))
    RR at 10: no first step
        rotate left at 10
  tree: (20:0 (10:0 . .) (30:0 . .))

The root 10 has bf -2, and its right child 20 has bf -1. One left rotation at 10 lifts 20 to the top.

Worked example 2: LR with the keys 30, 10, 20

Insert 30, 10 and 20.

LR
  insert 30
  tree: (30:0 . .)
  insert 10
  tree: (30:1 (10:0 . .) .)
  insert 20
    unbalanced at 30, bf 2: (30:2 (10:-1 . (20:0 . .)) .)
    LR at 30: rotate left at 10
        subtree now: (30:2 (20:1 (10:0 . .) .) .)
        rotate right at 30
  tree: (20:0 (10:0 . .) (30:0 . .))

After 10 the root is 30 with bf +1. Node 10 is a left child and a leaf.

The key 20 is larger than 10, so it goes to the right of 10. Node 10 now has bf -1, because its right side is taller. Node 30 has bf +2. The program says unbalanced at 30, bf 2.

The left child of 30 is 10, and its bf is -1, which is negative. That makes this the LR case. Check the shape: the new key 20 went down the inside of the bent path 30, 10, 20. A single right rotation at 30 would give 10 at the top with 30 on its right and 20 stuck on the left of 30. That tree has bf -2 at the root, so it is still wrong.

The first step is a left rotation at 10. Node 20 moves up to replace 10, and 10 becomes the left child of 20. The program prints the subtree now: (30:2 (20:1 (10:0 . .) .) .). The root still has bf +2, but the bent path has become a straight line, 30, 20, 10.

The second step is a right rotation at 30. Node 20 moves up, and 30 becomes its right child. The final tree is (20:0 (10:0 . .) (30:0 . .)). Every node has bf 0.

Worked example 3: RL with the keys 10, 30, 20

Insert 10, 30 and 20. This is the mirror of example 2.

RL
  insert 10
  tree: (10:0 . .)
  insert 30
  tree: (10:-1 . (30:0 . .))
  insert 20
    unbalanced at 10, bf -2: (10:-2 . (30:1 (20:0 . .) .))
    RL at 10: rotate right at 30
        subtree now: (10:-2 . (20:-1 . (30:0 . .)))
        rotate left at 10
  tree: (20:0 (10:0 . .) (30:0 . .))

The key 20 goes to the left of 30. Node 30 now has bf +1, and root 10 has bf -2. The right child, 30, has bf +1, which is positive. That is the RL case.

The first step rotates 30 to the right. Node 20 moves up to become the right child of 10, and 30 becomes the right child of 20. The subtree now reads (10:-2 . (20:-1 . (30:0 . .))). It is a straight line again, 10, 20, 30.

The second step rotates 10 to the left. Node 20 moves to the top, with 10 on its left and 30 on its right. The final tree is balanced.

Worked example 4: a fix below the root

The root does not always need the repair. The imbalance can happen at a lower node, and the rotation stays inside that part of the tree. Insert 8, 4, 12, 2 and 1.

LL below the root
  insert 8
  tree: (8:0 . .)
  insert 4
  tree: (8:1 (4:0 . .) .)
  insert 12
  tree: (8:0 (4:0 . .) (12:0 . .))
  insert 2
  tree: (8:1 (4:1 (2:0 . .) .) (12:0 . .))
  insert 1
    unbalanced at 4, bf 2: (4:2 (2:1 (1:0 . .) .) .)
    LL at 4: no first step
        rotate right at 4
  tree: (8:1 (2:0 (1:0 . .) (4:0 . .)) (12:0 . .))

The new key 1 makes node 4 have bf +2. The program fixes node 4 first, because it works back up from the new key. Node 4's left child 2 has bf +1, so this is the LL case at node 4. One right rotation at 4 lifts 2 up. Node 2 now has bf 0, and the root 8 is checked last. Its left side has height 2 again, so the root keeps bf +1 and is not rotated.

The program checks the tree at each node on the way back up from the new key, so a repair can happen at a node several levels below the root.

Delete

A delete removes a node and then checks the nodes on the path back to the root, exactly as insert does. The difference is the rule for choosing a case.

After an insert, the heavy child always has a nonzero balance factor. The new key made that child taller, so its two sides differ. After a delete, the heavy child can have balance factor 0. The removed key was on the lighter side, so the heavy child now has the same height on both sides.

The rule for delete is this:

• Look at the root's bf, which is +2 or -2.
• Look at the child on the taller side.
• If the child's bf has the same sign as the root's, or is 0, do one rotation. A child with bf 0 is possible only after a delete.
• If the child's bf has the opposite sign, do two rotations, as in LR or RL.

The program uses this same rule. Its test is balance(n->left) < 0 for the left side and balance(n->right) > 0 for the right side. A child with bf 0 fails both tests, so the program does one rotation.

The program removes a node with two children by copying the smallest key in its right subtree into that node, then deleting that smallest node. The smallest key in a right subtree is the leftmost node of that subtree, which is the successor of the removed key.

Worked example 5: a single rotation after a delete

Build the tree from the keys 20, 10, 30, 25 and 40, then delete 10.

delete, single RR (child bf 0)
  before: (20:-1 (10:0 . .) (30:0 (25:0 . .) (40:0 . .)))
  delete 10
    unbalanced at 20, bf -2: (20:-2 . (30:0 (25:0 . .) (40:0 . .)))
    RR at 20: no first step
        rotate left at 20
  after: (30:1 (20:-1 . (25:0 . .)) (40:0 . .))

Before the delete, the root 20 has bf -1, because the right side is taller. Node 30 has two leaf children, so its bf is 0.

Deleting 10 leaves the left side of 20 empty. The root's bf becomes -2. Its right child, 30, has bf 0. That is a case the insert never produces, so the rule above applies. Node 30 has the same height on both sides, and one left rotation at 20 is enough.

The rotation lifts 30. Node 20 becomes its left child, and 25 moves across to become the right child of 20. The final root is 30 with bf +1. Left of it, node 20 has bf -1 because 25 is its only child. The keys still read 20, 25, 30, 40 in order.

Worked example 6: a double rotation after a delete

Build the tree from the keys 20, 10, 30 and 25, then delete 10.

delete, double RL (child bf +1)
  before: (20:-1 (10:0 . .) (30:1 (25:0 . .) .))
  delete 10
    unbalanced at 20, bf -2: (20:-2 . (30:1 (25:0 . .) .))
    RL at 20: rotate right at 30
        subtree now: (20:-2 . (25:-1 . (30:0 . .)))
        rotate left at 20
  after: (25:0 (20:0 . .) (30:0 . .))

Before the delete, the root 20 has bf -1. Its right child 30 has bf +1, because 25 is on its left.

Deleting 10 gives 20 bf -2. The taller side is the right side, and the right child 30 has bf +1, which is the opposite sign. This is the RL case, so two rotations are needed.

The first step rotates 30 to the right, which lifts 25. The subtree now reads (20:-2 . (25:-1 . (30:0 . .))). The bent path 20, 30, 25 has become the straight path 20, 25, 30.

The second step rotates 20 to the left. Node 25 moves to the top. The final tree is balanced, with 25 at the root and 20 and 30 as leaves.

Mistakes

Copying a tree by copying its root. The tree is built from std::unique_ptr, which can have only one owner. A copy like this one does not compile:

Tree root = insert(nullptr, 5);
Tree copy = root;

The compiler reports:

mistake5.cpp:6:17: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]’

The fix is to move the tree with std::move, or to write a separate function that builds a new copy node by node.

Testing the wrong side for LR. The LR test looks for a negative balance factor on the left child. If the test is written with > 0 instead, the program takes the single rotation in the LR case. The printed result shows the problem. For the keys 30, 10, 20 the mutant (a copy of the program with one deliberate change) printed:

LR mutant
  insert 30
  tree: (30:0 . .)
  insert 10
  tree: (30:1 (10:0 . .) .)
  insert 20
    unbalanced at 30, bf 2: (30:2 (10:-1 . (20:0 . .)) .)
    LL at 30: no first step
        rotate right at 30
  tree: (10:-2 . (30:1 (20:0 . .) .))

The root 10 now has bf -2. The tree is still out of balance after the repair. In a correct run, every bf in the printed trees is from -1 to +1 after the repair. When a trace shows -2 or +2 after a repair, the case was chosen wrongly.

Rotating a node with no child on that side. A left rotation moves the right child up, so the node must have a right child. The function then reads y->left from that child. With no right child, that read goes through a null pointer. This program calls rotate_left on a single node:

Tree leaf = std::make_unique<Node>(10);
Tree bad = rotate_left(std::move(leaf));

Without the sanitizer, the program stops with exit code 139, which means a segmentation fault. Built with -fsanitize=address, the message is (the process id and the addresses after pc, bp and sp change on each run):

ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x5d0058fe201a bp 0x7fffbb0e6e40 sp 0x7fffbb0e6e20 T0)

The rotation functions in this lesson assume the child exists. The rebalance function only calls them when the balance factor shows that the child is there.

The full program

This is the program that produced every output in this lesson. It compiles with g++ -std=c++20 -Wall -Wextra -pedantic without warnings.

#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <memory>
#include <string>
 
struct Node {
    int key;
    int height = 1;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int k) : key(k) {}
};
 
using Tree = std::unique_ptr<Node>;
 
int height(const Node* n) { return n ? n->height : 0; }
 
int balance(const Node* n) {
    return n ? height(n->left.get()) - height(n->right.get()) : 0;
}
 
void update(Node* n) {
    n->height = 1 + std::max(height(n->left.get()), height(n->right.get()));
}
 
void show(const Node* n, std::ostream& os) {
    if (!n) {
        os << ".";
        return;
    }
    os << "(" << n->key << ":" << balance(n) << " ";
    show(n->left.get(), os);
    os << " ";
    show(n->right.get(), os);
    os << ")";
}
 
// Right rotation: the left child moves up and becomes the new root.
Tree rotate_right(Tree y) {
    Tree x = std::move(y->left);
    y->left = std::move(x->right);
    update(y.get());
    x->right = std::move(y);
    update(x.get());
    return x;
}
 
// Left rotation: the right child moves up and becomes the new root.
Tree rotate_left(Tree x) {
    Tree y = std::move(x->right);
    x->right = std::move(y->left);
    update(x.get());
    y->left = std::move(x);
    update(y.get());
    return y;
}
 
Tree rebalance(Tree n) {
    update(n.get());
    int bf = balance(n.get());
    if (bf > 1 || bf < -1) {
        std::cout << "    unbalanced at " << n->key << ", bf " << bf << ": ";
        show(n.get(), std::cout);
        std::cout << "\n";
    }
    if (bf > 1) {
        if (balance(n->left.get()) < 0) {
            std::cout << "    LR at " << n->key << ": rotate left at " << n->left->key << "\n";
            n->left = rotate_left(std::move(n->left));
            std::cout << "        subtree now: ";
            show(n.get(), std::cout);
            std::cout << "\n";
        } else {
            std::cout << "    LL at " << n->key << ": no first step\n";
        }
        std::cout << "        rotate right at " << n->key << "\n";
        n = rotate_right(std::move(n));
    } else if (bf < -1) {
        if (balance(n->right.get()) > 0) {
            std::cout << "    RL at " << n->key << ": rotate right at " << n->right->key << "\n";
            n->right = rotate_right(std::move(n->right));
            std::cout << "        subtree now: ";
            show(n.get(), std::cout);
            std::cout << "\n";
        } else {
            std::cout << "    RR at " << n->key << ": no first step\n";
        }
        std::cout << "        rotate left at " << n->key << "\n";
        n = rotate_left(std::move(n));
    }
    return n;
}
 
Tree insert(Tree n, int key) {
    if (!n) return std::make_unique<Node>(key);
    if (key < n->key) n->left = insert(std::move(n->left), key);
    else if (key > n->key) n->right = insert(std::move(n->right), key);
    else return n;
    return rebalance(std::move(n));
}
 
Tree remove(Tree n, int key) {
    if (!n) return n;
    if (key < n->key) {
        n->left = remove(std::move(n->left), key);
    } else if (key > n->key) {
        n->right = remove(std::move(n->right), key);
    } else {
        if (!n->left) return std::move(n->right);
        if (!n->right) return std::move(n->left);
        Node* s = n->right.get();
        while (s->left) s = s->left.get();
        n->key = s->key;
        n->right = remove(std::move(n->right), s->key);
    }
    return rebalance(std::move(n));
}
 
void print_state(const std::string& label, const Tree& root) {
    std::cout << "  " << label << ": ";
    show(root.get(), std::cout);
    std::cout << "\n";
}
 
void insert_run(const std::string& title, std::initializer_list<int> keys) {
    std::cout << title << "\n";
    Tree root;
    for (int k : keys) {
        std::cout << "  insert " << k << "\n";
        root = insert(std::move(root), k);
        print_state("tree", root);
    }
}
 
void delete_run(const std::string& title, std::initializer_list<int> keys, int victim) {
    std::cout << title << "\n";
    Tree root;
    for (int k : keys) root = insert(std::move(root), k);
    print_state("before", root);
    std::cout << "  delete " << victim << "\n";
    root = remove(std::move(root), victim);
    print_state("after", root);
}
 
int main() {
    insert_run("LL", {30, 20, 10});
    insert_run("RR", {10, 20, 30});
    insert_run("LR", {30, 10, 20});
    insert_run("RL", {10, 30, 20});
    insert_run("LL below the root", {8, 4, 12, 2, 1});
    delete_run("delete, single RR (child bf 0)", {20, 10, 30, 25, 40}, 10);
    delete_run("delete, double RL (child bf +1)", {20, 10, 30, 25}, 10);
}

The program prints the traces shown in the worked examples above.

Practice

Exercise 1. Insert 5, 3 and 1 into an empty AVL tree. Which case happens, and what is the final tree?

Show the answer

The case is LL at 5. After inserting 1, the root 5 has bf +2 and its left child 3 has bf +1. One right rotation at 5 lifts 3 to the root. The final tree is (3:0 (1:0 . .) (5:0 . .)).

Exercise 2. Insert 1, 3 and 2 into an empty AVL tree. Which case happens, and what is the final tree?

Show the answer

The case is RL at 1. The root 1 has bf -2, and its right child 3 has bf +1 because the key 2 went to its left. The first step rotates 3 to the right, and the second step rotates 1 to the left. The final tree is (2:0 (1:0 . .) (3:0 . .)).

Exercise 3. Build the tree from 50, 30, 70, 60 and 80, then delete 30. Which case happens? Give the final tree.

Show the answer

Before the delete the root 50 has bf -1, and its right child 70 has bf 0. After 30 is removed, the root has bf -2 and the child has bf 0. That is the single RR case, so one left rotation at 50 is enough. The final tree is (70:1 (50:-1 . (60:0 . .)) (80:0 . .)).

Exercise 4. Build the tree from 40, 20, 60, 10, 30, 50, 70 and 25, then delete 70. Does a rotation happen? Give the balance factor of the root and of 60 after the delete.

Show the answer

No rotation happens. After the delete, every node has bf -1, 0 or +1. The root 40 has bf +1, and node 60 has bf +1 because its only child is 50. The final tree is (40:1 (20:-1 (10:0 . .) (30:1 (25:0 . .) .)) (60:1 (50:0 . .) .)).

Exercise 5. Build the tree from 8, 4, 12, 2, 6, 10, 14 and 5, then delete 2. Which node is out of balance, which case is it, and what does the final tree look like?

Show the answer

After the delete, node 4 has bf -2, because its left side is empty and its right side has height 2. Its right child 6 has bf +1, because 5 is on its left. That is the RL case at 4. The first step rotates 6 to the right, which lifts 5. The second step rotates 4 to the left, which lifts 5 again. The final tree is (8:0 (5:0 (4:0 . .) (6:0 . .)) (12:0 (10:0 . .) (14:0 . .))).

Summary

• The balance factor of a node is the height of its left subtree minus the height of its right subtree, and an AVL tree keeps every balance factor at -1, 0 or +1.
• The four cases are LL and RR, which need one rotation, and LR and RL, which need two rotations. The two letters name the side of the root and the side of its child.
• After an insert, the heavy child always has a nonzero balance factor. After a delete, the heavy child can have balance factor 0, and then one rotation is enough.
• A rotation moves keys without changing their order, so an in-order walk of the tree gives the same sorted keys before and after.
• When a trace shows a balance factor of -2 or +2 after a repair, the case was chosen wrongly.