AVL tree rotations in Data Structures Theory - Full Explanation

Introduction

Balancing a tree is crucial to keep searching fast. When a tree becomes uneven, it slows down operations. AVL tree rotations fix this by rearranging nodes to keep the tree balanced.

Explanation

Why Balance Matters

A balanced tree keeps its height small, so searching, inserting, and deleting happen quickly. If one side grows too tall, these operations slow down. AVL trees use rotations to restore balance after changes.

Keeping the tree balanced ensures fast operations.

Single Right Rotation (LL Rotation)

This rotation fixes a left-heavy imbalance caused by inserting into the left child’s left subtree. It moves the left child up and the root down to the right, restoring balance.

Single right rotation corrects left-left imbalances.

Single Left Rotation (RR Rotation)

This rotation fixes a right-heavy imbalance caused by inserting into the right child’s right subtree. It moves the right child up and the root down to the left, restoring balance.

Single left rotation corrects right-right imbalances.

Left-Right Rotation (LR Rotation)

This double rotation fixes a left-right imbalance caused by inserting into the left child’s right subtree. It first rotates the left child to the left, then the root to the right.

Left-right rotation fixes left-right imbalances with two steps.

Right-Left Rotation (RL Rotation)

This double rotation fixes a right-left imbalance caused by inserting into the right child’s left subtree. It first rotates the right child to the right, then the root to the left.

Right-left rotation fixes right-left imbalances with two steps.

Real World Analogy

Imagine a seesaw with kids on both sides. If one side gets too heavy, the seesaw tips. To fix it, kids move around or swap places to balance it again. AVL rotations are like these moves to keep the seesaw level.

Why Balance Matters → Seesaw tipping when one side is heavier

Single Right Rotation (LL Rotation) → A kid on the left side moves closer to the center to balance

Single Left Rotation (RR Rotation) → A kid on the right side moves closer to the center to balance

Left-Right Rotation (LR Rotation) → A kid on the left side first moves right, then the seesaw adjusts

Right-Left Rotation (RL Rotation) → A kid on the right side first moves left, then the seesaw adjusts

Diagram

Diagram

Before LL Rotation:
    z
   /
  y
 /
x

After LL Rotation:
    y
   / \
  x   z

Before RR Rotation:
  x
   \
    y
     \
      z

After RR Rotation:
    y
   / \
  x   z

LR Rotation:
  z
 /
x
 \
  y

After LR Rotation:
    y
   / \
  x   z

RL Rotation:
  x
   \
    z
   /
  y

After RL Rotation:
    y
   / \
  x   z

Shows how nodes move during each AVL rotation to restore balance.

Key Facts

AVL Tree → A self-balancing binary search tree that maintains height balance using rotations.

Balance Factor → The height difference between left and right subtrees of a node.

Single Rotation → A rotation that fixes simple left-left or right-right imbalances.

Double Rotation → A two-step rotation that fixes left-right or right-left imbalances.

LL Rotation → Single right rotation to fix left-left imbalance.

RR Rotation → Single left rotation to fix right-right imbalance.

Code Example

Data Structures Theory

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def get_height(self, node):
        return node.height if node else 0

    def get_balance(self, node):
        return self.get_height(node.left) - self.get_height(node.right) if node else 0

    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def left_rotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y

    def insert(self, root, key):
        if not root:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        balance = self.get_balance(root)

        # LL
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        # RR
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        # LR
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # RL
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def pre_order(self, root):
        return [] if not root else [root.key] + self.pre_order(root.left) + self.pre_order(root.right)

avl = AVLTree()
root = None
for key in [10, 20, 30, 40, 50, 25]:
    root = avl.insert(root, key)
print(avl.pre_order(root))

Common Confusions

Thinking all rotations are single-step.

Thinking all rotations are single-step. Some imbalances need two rotations (double rotations) to fix, not just one.

Believing rotations change the binary search tree order.

Believing rotations change the binary search tree order. Rotations only rearrange nodes to balance the tree but keep the search order intact.

Assuming balance factor is always zero after rotation.

Assuming balance factor is always zero after rotation. Balance factors after rotation can be -1, 0, or 1, all indicating a balanced node.

Summary

AVL tree rotations keep the tree balanced to ensure fast searching and updating.

Single rotations fix simple imbalances, while double rotations fix more complex ones.

Rotations rearrange nodes without changing the binary search tree order.