Course contentsShow
← Computer Science
Lesson 535 of 2,87213. Balanced TreesFree lesson

Single Right Rotation

Perform a right rotation to restore balance in the Left-Left case while maintaining BST property.

Single Right Rotation

What you'll learn: You'll discover how to fix a Left-Left imbalance in an AVL tree using a single right rotation that restores balance while preserving the BST property.


The Problem

When you insert a node into an AVL tree, you might create a Left-Left case: a node becomes unbalanced (balance factor = +2) because its left child's left subtree is too tall. Picture a tree leaning heavily to the left like the Leaning Tower of Pisa.

The Solution: Right Rotation

A right rotation is like grabbing the left child and promoting it upward, making the original parent "rotate" down to become the right child. Think of it as straightening a bent elbow by pivoting at the joint.

Here's what happens step-by-step:

  1. Identify the unbalanced node (let's call it z)
  2. Its left child (call it y) becomes the new root of this subtree
  3. z becomes y's right child
  4. y's right subtree (if any) becomes z's new left subtree

Why It Works

The rotation maintains the BST property because:

  • Everything in y's left subtree stays smaller than y
  • Everything in y's original right subtree fits between y and z
  • Everything in z's right subtree stays larger than z

The heights change: z drops one level, y rises one level, and balance is restored. The balance factors after rotation become 0 for both nodes in the typical case.

The Analogy

Imagine three people standing in a line: small, medium, tall. They're leaning left. You pivot around the middle person, moving them to the center position—now everyone stands balanced!

Key Takeaway: A single right rotation fixes Left-Left imbalances by promoting the left child upward while preserving BST order—it's a local restructuring that costs O(1) time.