31  Balanced Trees — AVL and Red-Black

32 Balanced Trees — AVL and Red-Black

Week 5, Session 1. CSS 343.

32.1 Warmup

Validate Binary Search Tree (#98). Verify a tree satisfies the BST property.

class Solution {
 public:
  bool isValidBST(TreeNode* root) {
    return check(root, LLONG_MIN, LLONG_MAX);
  }
 private:
  bool check(TreeNode* node, long long lo, long long hi) {
    if (node == nullptr) return true;
    if (node->val <= lo || node->val >= hi) return false;
    return check(node->left, lo, node->val)
        && check(node->right, node->val, hi);
  }
};

Pass min/max bounds down. Each node’s value must lie strictly between them. Note the use of long long for bounds — the problem allows INT_MIN and INT_MAX as values, so the bounds must be wider.

32.2 Learning objectives

1. Calculate the balance factor of every node after an insertion into an AVL tree.
2. Identify which rotation case (LL, RR, LR, RL) is required and execute it.
3. State the four Red-Black tree properties and explain the O(log n) guarantee.
4. Choose between AVL and Red-Black trees for a given use case.
5. Use std::map and std::set correctly, knowing their O(log n) guarantees.

32.3 Motivation

Plain BSTs degenerate. AVL trees and red-black trees do not — they keep height O(log n) by rotating during insert and delete. The cost is slightly more work per operation. The payoff is that the worst case is the average case.

32.4 AVL trees

An AVL tree is a BST with the invariant that for every node, the heights of its left and right subtrees differ by at most 1.

int balanceFactor(Node* node) {
  return height(node->left) - height(node->right);
}

A balance factor in {-1, 0, +1} is fine. Outside that range, the tree is unbalanced and must be rotated.

32.4.1 The four rotation cases

When an imbalance occurs after insert at node X:

Case	Description	Fix
LL	Inserted in left subtree of left child	Right rotation at X
RR	Inserted in right subtree of right child	Left rotation at X
LR	Inserted in right subtree of left child	Left rotation at left child, then right rotation at X
RL	Inserted in left subtree of right child	Right rotation at right child, then left rotation at X

32.4.2 Right rotation (LL case)

      30                      20
     /                       /  \
    20          →           10   30
   /
  10

Node* rotateRight(Node* y) {
  Node* x = y->left;
  Node* T2 = x->right;
  x->right = y;
  y->left = T2;
  updateHeight(y);
  updateHeight(x);
  return x;          // new subtree root
}

32.4.3 Left rotation (RR case)

The mirror image.

Node* rotateLeft(Node* x) {
  Node* y = x->right;
  Node* T2 = y->left;
  y->left = x;
  x->right = T2;
  updateHeight(x);
  updateHeight(y);
  return y;
}

32.4.4 Double rotations (LR, RL)

LR: rotate left at the left child to convert to LL, then right rotate at the imbalanced node.

    30          30          20
   /           /           /  \
  10    →    20    →     10   30
   \         /
    20      10

RL: mirror.

32.4.5 AVL insert

Node* insert(Node* node, int value) {
  if (node == nullptr) return new Node(value);
  if (value < node->data) node->left = insert(node->left, value);
  else if (value > node->data) node->right = insert(node->right, value);
  else return node;          // no duplicates

  updateHeight(node);
  int bf = balanceFactor(node);

  // LL
  if (bf > 1 && value < node->left->data) return rotateRight(node);
  // RR
  if (bf < -1 && value > node->right->data) return rotateLeft(node);
  // LR
  if (bf > 1 && value > node->left->data) {
    node->left = rotateLeft(node->left);
    return rotateRight(node);
  }
  // RL
  if (bf < -1 && value < node->right->data) {
    node->right = rotateRight(node->right);
    return rotateLeft(node);
  }

  return node;
}

The rotations happen on the way up the recursion. By the time you return to the root, the entire tree is balanced.

AVL trees were the first self-balancing BST, invented in 1962. They are stricter than red-black trees — balance factor must be in {-1, 0, +1}. Stricter balance means faster lookups but more rotations on insert.

32.5 Red-Black trees

A red-black tree is a BST where each node is colored red or black, satisfying:

1. The root is black.
2. Every leaf (nullptr) is black.
3. A red node’s children are both black. (No two reds in a row.)
4. Every path from a node to its descendant leaves contains the same number of black nodes.

These properties together guarantee that the longest path is at most twice the shortest, so height is O(log n).

32.5.1 Insert and rebalancing

After a normal BST insert, color the new node red. If its parent is also red, you have a violation. Fix it by:

• Recoloring if the uncle is red.
• Rotating if the uncle is black.

The case analysis is gnarly. For 343 you should know the properties and that O(log n) is guaranteed. The full implementation is a CLRS-grade exercise.

32.6 AVL vs. Red-Black: which to use?

	AVL	Red-Black
Balance	Strict (≤1 height diff)	Loose (≤2× shortest)
Lookup	Slightly faster	Slightly slower
Insert / delete rotations	More	Fewer
Best for	Read-heavy workloads	Write-heavy workloads
In the wild	Some database indexes	std::map, Linux completely fair scheduler, Java TreeMap

std::map and std::set are red-black trees. You have been using a red-black tree the entire course.

32.7 STL map / set patterns

map<int, int> m;
m[5] = 100;
m[2] = 50;
m[8] = 200;

for (auto& [k, v] : m) cout << k << " ";     // 2 5 8  sorted

auto it = m.lower_bound(4);     // first key >= 4 → 5
auto it2 = m.upper_bound(8);    // first key > 8 → end

// Find first key in range [a, b]:
auto r = m.lower_bound(a);
if (r != m.end() && r->first <= b) { /* found */ }

lower_bound and upper_bound are the killer features. They are O(log n) and they are the reason you sometimes want map over unordered_map.

32.8 Try it

Insert {30, 20, 10} into an empty AVL tree. After inserting 30 and 20, the tree is fine (heights 1 and 0). After inserting 10, node 30 has balance factor 2 (left height 1, right height -1). LL case. Rotate right at 30.

Draw the before and after.

32.9 Self-check

1. std::map<int, int> is implemented as:

• a. Hash table
• b. AVL tree
• c. Red-black tree
• d. Skip list

c. Standard library implementations use red-black trees for the ordered associative containers.

2. After inserting {10, 30, 20} into an empty AVL tree, the case is:

• a. LL
• b. LR
• c. RR
• d. RL

b. 30 goes right of 10. 20 goes left of 30. Imbalance at 10 with offender in the right-left direction. Left-right (LR) case. Rotate left at 30, then right at 10.

32.10 Challenges

1. Implement AVL insert end-to-end. Test with sorted-insertion sequence to confirm balancing.
2. Convert Sorted Array to Binary Search Tree (#108) — produces a balanced tree from sorted input.
3. Balanced Binary Tree (#110) — verify AVL property.

32.11 Where this fits

You can now build a tree that never degenerates. The midterm comes next; afterward we leave data structures and enter algorithm design — divide-and-conquer, greedy, DP.

You are here	Coming up
AVL rotations, Red-Black properties, STL map/set internals	Chapter 30: midterm review