DSA - AVL Trees

Context & Motivation

• Problem: The worst-case height of a standard Binary Search Tree (BST) is $n-1$, causing operations (search, insert, delete) to degrade to $O(n)$ time.
• Goal: Keep the tree height bounded by $O(\log n)$ to ensure efficient operations.
• Solution: AVL Trees (Adelson-Velsky and Landis), a self-balancing binary search tree where the height difference between left and right subtrees is strictly controlled.

---

AVL Tree Definition

An AVL tree is a BST that satisfies the Height-Balance Property:

• For every node, the height difference between its left and right subtrees is at most 1.

• Height Definition: The height of a node is the number of edges to the deepest leaf. The height of an empty tree is defined as -1.

• Balance Factor: Checks if a node is balanced.

  • $|Height(Left)-Height(Right)|[cit{e}_{s}tart]\le 1$: Balanced.
  • Difference $\ge 2$: Unbalanced, requires rotation.

Height Analysis

The strict balance ensures the tree remains shallow (logarithmic height).

• Minimum Nodes Formula: The minimum number of nodes $N_h$ required for an AVL tree of height $h$ follows the recurrence relation:

$$N_h=1+N_{h-1}+N_{h-2}$$

(Base cases: $N_0=1$, $N_1=2$) .

• Complexity: Because height is $O(\log n)$, Search, Insert, and Delete operations take O(logn) time.

---

3. Operations & Rebalancing

We maintain balance using Rotations. A rotation is a local change to the tree structure that preserves the BST ordering property while adjusting heights.

A. Insertion

1. Insert: Insert the new key as a leaf (standard BST insertion).

2. Trace Up: Trace the path from the new leaf back towards the root.

3. Check & Fix: For every node encountered, check the height difference. If unbalanced, perform the appropriate rotation.

   • Note: For insertion, one rebalancing operation (single or double rotation) at the deepest unbalanced node is sufficient to fix the entire tree.

B. Deletion (Distinct from Insertion)

Deletion is more complex because fixing one imbalance might create a new imbalance higher up the tree.

1. Delete: Remove the node using standard BST deletion logic (e.g., replace with successor if two children).

2. Trace Up: Trace the path from the deletion point (parent of the deleted node) to the root.

3. Check & Fix: Check balance at each node on the path.

   • If unbalanced, perform rotation.
   • Crucial Difference: After a rotation during deletion, we must continue tracing upward to the root, as the parent node might now become unbalanced.

---

Rotation Cases (The 4 Scenarios)

When a node $\alpha$ becomes unbalanced, we identify the case based on the relative location of the "heavy" side .

Case	Description	Location Type	Fix
1. Left-Left (LL)	Insertion into the left subtree of the left child	"Outside"	Single Right Rotation
2. Left-Right (LR)	Insertion into the right subtree of the left child	"Inside"	Double Rotation (Left-Right)
3. Right-Left (RL)	Insertion into the left subtree of the right child	"Inside"	Double Rotation (Right-Left)
4. Right-Right (RR)	Insertion into the right subtree of the right child	"Outside"	Single Left Rotation

Special Case for Deletion

In deletion, a node might become heavy on one side (e.g., Right heavy), but its child is perfectly balanced (Left and Right subtrees of the child are equal height).

• Handling: Treat this as the "Outside" case (Case 1 or Case 4) because it is easier. A single rotation solves it.

---

Visualizing Rotations

Single Right Rotation (Fixes LL)

• Scenario: Node k2 is left-heavy, and its left child k1 is left-heavy (or balanced).
• Action: k1 moves up, k2 moves down to become k1's right child. k1's original right subtree (Y) becomes k2's left subtree .

2. Single Left Rotation (Fixes RR)

• Scenario: Node k1 is right-heavy, and its right child k2 is right-heavy.
• Action: k2 moves up, k1 moves down to become k2's left child.

3. Double Rotation (Fixes LR & RL)

Single rotations fail for "inside" cases because moving the child up doesn't reduce the depth of the inner subtree.

• LR (Left-Right):

  1. Left Rotate the left child (k1) to convert the shape into LL.
  2. Right Rotate the unbalanced node (k3/root).

• RL (Right-Left):

  1. Right Rotate the right child (k3) to convert shape into RR.
  2. Left Rotate the unbalanced node (k1/root).

---

6. Implementation Details

Storing Height

To maintain $O(\log n)$ complexity, we cannot calculate height recursively every time.

• Strategy: Keep a height field in every node.
• Update: Update the height field whenever the subtree is modified (insertion, deletion, or rotation).
• Calculation: node.height = max(left.height, right.height) + 1.

Updating Height During Rotation

When rotating, pointers change, so heights must be updated immediately.

• Order: Update the deeper (lower) node first (the new child), then update the new root.

---

7. Quick Reference: Unbalance Situations

Insert/Delete Strategy Summary:

• LL (Left-Left): Imbalance is on the Left child's Left subtree.

  • Fix: Single Right Rotation on the unbalanced node.

• LR (Left-Right): Imbalance is on the Left child's Right subtree.

  • Fix: Left Rotation on the child, then Right Rotation on the unbalanced node.

• RL (Right-Left): Imbalance is on the Right child's Left subtree.

  • Fix: Right Rotation on the child, then Left Rotation on the unbalanced node.

• RR (Right-Right): Imbalance is on the Right child's Right subtree.

  • Fix: Single Left Rotation on the unbalanced node.

Special Note for Deletion:

• If the heavy child is perfectly balanced, treat it as LL (if Left heavy) or RR (if Right heavy) and perform a Single Rotation.

Practice

Q1

What is the maximum AVL Tree height of 90 nodes?

The maximum AVL tree height for 90 nodes is 8.

Derivation:

Let $N_h$ be the minimum number of nodes required for an AVL tree of height $h$. Formula: $N_h=N_{h-1}+N_{h-2}+1$

• h=0: $N_0=1$
• h=1: $N_1=2$
• h=2: $1+2+1=4$
• h=3: $2+4+1=7$
• h=4: $4+7+1=12$
• h=5: $7+12+1=20$
• h=6: $12+20+1=33$
• h=7: $20+33+1=54$
• h=8: $33+54+1=\mathbf{88}$
• h=9: $54+88+1=143$

Conclusion: Since $88\le 90<143$, the maximum reachable height is 8.

Q2

Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL Tree.

Here is the step-by-step insertion process into the AVL Tree for the sequence: 2, 1, 4, 5, 9, 3, 6, 7.

Step 1: Insert 2, 1, 4

• Insert 2: Root.
• Insert 1: Left of 2. Balanced.
• Insert 4: Right of 2. Balanced.
• Result: The tree is perfectly balanced.

Step 2: Insert 5

• Insert 5: Right of 4.
• Balance Check: Node 4 (Balance -1), Node 2 (Balance -1).
• Result: Balanced.

Step 3: Insert 9 (Rebalance)

• Insert 9: Right of 5.

• Imbalance: Node 4 becomes unbalanced (Right-Right Case).

  • Node 4 balance: -2 (Height Left -1, Height Right 1).
  • Right child (5) balance: -1.

• Action: Single Left Rotation at Node 4.

  • 5 becomes the parent of 4 and 9.

Step 4: Insert 3 (Rebalance)

• Insert 3: Left of 4.

• Imbalance: Node 2 becomes unbalanced (Right-Left Case).

  • Node 2 balance: -2 (Height Left 0, Height Right 2).
  • Right child (5) balance: +1 (Left Heavy).

• Action: Double Rotation (RL).

  1. Right Rotation at Node 5 (Child 4 moves up).
  2. Left Rotation at Node 2 (Child 4 moves up to root).

Step 5: Insert 6 (Rebalance)

• Insert 6: Left of 9.

• Imbalance: Node 5 becomes unbalanced (Right-Left Case).

  • Node 5 balance: -2 (Height Left -1, Height Right 1).
  • Right child (9) balance: +1 (Left Heavy).

• Action: Double Rotation (RL) at Node 5.

  1. Right Rotation at Node 9 (6 moves up).
  2. Left Rotation at Node 5 (6 moves up to become parent).

Step 6: Insert 7 (Rebalance)

• Insert 7: Left of 9.

• Imbalance: Node 6 becomes unbalanced (Right-Left Case).

  • Node 6 balance: -2 (Height Left 0, Height Right 2).
  • Right child (9) balance: +1 (Left Heavy).

• Action: Double Rotation (RL) at Node 6.

  1. Right Rotation at Node 9 (7 moves up).
  2. Left Rotation at Node 6 (7 moves up to become parent).

Final Result

The resulting AVL Tree has 4 as the root, with left child 2 and right child 7.

• Root: 4
• Left Subtree: 2 (Children: 1, 3)
• Right Subtree: 7 (Left Child: 6 with child 5; Right Child: 9)