C++UCS301
Trees & ApplicationsC++17

AVL Tree

An AVL tree maintains a balance factor of −1, 0, or 1 at every node using rotations after updates.

What to understand

  • Height maintenance
  • LL, RR, LR, and RL cases
  • Single and double rotations
  • Guaranteed logarithmic height

Remember this

  1. 1Balance factor = left height − right height
  2. 2Rotations preserve BST order
  3. 3Update heights bottom-up

Detailed notes

AVL trees strengthen the BST invariant with a height-balance condition at every node. Because imbalance after one insertion first appears along the search path, local rotations can restore balance without changing inorder key order.

LL and RR are outside cases repaired by one rotation. LR and RL are inside cases repaired by rotating the child toward the outside and then rotating the unbalanced node.

How it works

  1. 1Perform ordinary BST insertion.
  2. 2Update stored heights while recursion unwinds.
  3. 3Compute balance and identify the heavy child direction.
  4. 4Apply the matching single or double rotation and return its new root.

Worked trace

Left-right imbalance

Insert 30, then 10, then 20
  1. 130 becomes root and 10 its left child.
  2. 220 enters as the right child of 10.
  3. 3Node 30 has balance +2, but insertion was inside the left subtree.
  4. 4Rotate left at 10, then rotate right at 30.
Result: 20 becomes root with children 10 and 30

Where it is used

  • Read-heavy ordered dictionaries
  • In-memory indexes needing strict lookup guarantees
  • Teaching local rebalancing and rotations

Common mistakes

  • Updating heights in the wrong order after rotation
  • Choosing a case only from balance without examining child/key direction
  • Forgetting that deletion may rebalance multiple ancestors

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(log n)O(log n)O(log n)O(1)
InsertO(log n)O(log n)O(log n)O(1)
DeleteO(log n)O(log n)O(log n)O(1)

C++ implementation

C++17 reference
main.cpp

AVL insertion with four rotation cases

Recompute height before checking balance; double rotations repair inside-heavy shapes.

struct Node { int key, height; Node* left; Node* right; };
int height(Node* n) { return n ? n->height : 0; }
void update(Node* n) { n->height = 1 + max(height(n->left), height(n->right)); }

Node* rotateRight(Node* y) {
    Node* x = y->left; Node* middle = x->right;
    x->right = y; y->left = middle;
    update(y); update(x); return x;
}
Node* rotateLeft(Node* x) {
    Node* y = x->right; Node* middle = y->left;
    y->left = x; x->right = middle;
    update(x); update(y); return y;
}

Node* insert(Node* root, int key) {
    if (!root) return new Node{key, 1, nullptr, nullptr};
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    else return root;
    update(root);
    int balance = height(root->left) - height(root->right);
    if (balance > 1 && key < root->left->key) return rotateRight(root);
    if (balance < -1 && key > root->right->key) return rotateLeft(root);
    if (balance > 1) { root->left = rotateLeft(root->left); return rotateRight(root); }
    if (balance < -1) { root->right = rotateRight(root->right); return rotateLeft(root); }
    return root;
}
28 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.