CodeBlanks Logo Icon CodeBlanks
Login Register

Rotation

Single and double rotations restore balance.

Rotation

When the balance breaks in AVL a rotation is done. Right rotation: in a left-heavy case, brings the left child up.

In a right rotation: y = x.left, x.left = y.right, y.right = x. Now y is the new root, x its right child.

The rotation preserves the BST property and reduces height. It is O(1).

Four cases

AVL has four imbalance cases: left-left (right rotate), left-right (left then right rotate), right-right (left rotate), right-left (right then left rotate).

Left-right and right-left need double rotation: first a sub-rotation, then the main one. This fixes complex skews.

In every case the result: balance factor returns to -1,0,+1; the BST property is preserved.

Practice Right rotation

Write rotate_right(x). y = x.left, x.left = y.right, y.right = x, return y. Print 2 3 with root = Node(3); root.left = Node(2); root.left.left = Node(1); new_root = rotate_right(root); print(new_root.val, new_root.right.val).

Starter code

solution.py
def rotate_right(x):
    # Right rotation

Sample solution

solution.py
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def rotate_right(x):
    # Right rotation
    y = x.left
    x.left = y.right
    y.right = x
    return y
root = Node(3)
root.left = Node(2)
root.left.left = Node(1)
new_root = rotate_right(root)
print(new_root.val, new_root.right.val)

Expected output

2 3

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Right rotation

Question 
y = x.left
x.left = y.____
y.right = x
Answer 
y = x.left
x.left = y.right
y.right = x

Explanation: right is right.

2 Rotation: match the terms

Term Meaning
Left-left Right rotate
Right-right Left rotate
Left-right Left first
Right-left Right first

3 Which case does right rotation fix?

  • Right-right
  • Left-right
  • Left-left Correct answer
  • Right-left

Explanation: Left-left

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4