AVL tree rotations in Data Structures Theory - Mini Project: Build & Apply

AVL Tree Rotations

📖 Scenario: You are learning about AVL trees, a type of self-balancing binary search tree. When nodes are inserted or deleted, the tree may become unbalanced. To fix this, rotations are used to restore balance.In this project, you will build a simple representation of an AVL tree node and then apply the four basic rotations used to rebalance the tree.

🎯 Goal: Build a simple AVL tree node structure and implement the four basic AVL tree rotations: left rotation, right rotation, left-right rotation, and right-left rotation.

📋 What You'll Learn

Create a node structure with key and height

Define a balance factor variable

Implement left and right rotation functions

Implement left-right and right-left rotation functions

💡 Why This Matters

🌍 Real World

AVL trees are used in databases and file systems to keep data sorted and allow fast search, insert, and delete operations.

💼 Career

Understanding AVL tree rotations is important for software engineers working with data structures, algorithms, and performance optimization.

1

Create AVL Tree Node Structure

Create a class called AVLNode with an __init__ method that takes key as input and sets self.key = key, self.left = None, self.right = None, and self.height = 1.

Data Structures Theory

# Define AVLNode class with __init__ method
# Your code here

Hint

Define a class with an initializer that sets key, left, right, and height attributes.

2

Define Balance Factor Function

Create a function called get_balance that takes a node n and returns the difference between the height of n.left and n.right. If n is None, return 0. Use a helper function height that returns 0 if the node is None, else returns node.height.

Data Structures Theory

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

# Define height and get_balance functions
# Your code here

Hint

Use a helper function to get height safely, then subtract right height from left height.

3

Implement Left and Right Rotations

Define two functions: left_rotate(z) and right_rotate(z). For left_rotate, set y = z.right, T2 = y.left, then perform rotation by setting y.left = z and z.right = T2. Update heights of z and y accordingly and return y. For right_rotate, do the symmetric steps with y = z.left and T3 = y.right. Update heights and return y.

Data Structures Theory

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

def height(node):
    if node is None:
        return 0
    return node.height

def get_balance(n):
    if n is None:
        return 0
    return height(n.left) - height(n.right)

# Define left_rotate and right_rotate functions
# Your code here

Hint

Follow the rotation steps carefully and update heights after rotation.

4

Implement Left-Right and Right-Left Rotations

Define two functions: left_right_rotate(z) and right_left_rotate(z). For left_right_rotate, first perform left_rotate on z.left, then right_rotate on z. For right_left_rotate, first perform right_rotate on z.right, then left_rotate on z. Return the final rotated node.

Data Structures Theory

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

def height(node):
    if node is None:
        return 0
    return node.height

def get_balance(n):
    if n is None:
        return 0
    return height(n.left) - height(n.right)

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

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

# Define left_right_rotate and right_left_rotate functions
# Your code here

Hint

Combine the basic rotations in the correct order to perform double rotations.

Practice

1. What is the main purpose of rotations in an AVL tree?

easy

A. To keep the tree balanced for faster search and update operations

B. To delete nodes from the tree

C. To increase the height of the tree

D. To sort the nodes in ascending order

Solution

1. Step 1: Understand AVL tree balance

   AVL trees maintain balance by ensuring the height difference between left and right subtrees is at most 1.

2. Step 2: Role of rotations

   Rotations adjust the tree structure to restore balance after insertions or deletions, improving operation speed.

3. Final Answer:

   To keep the tree balanced for faster search and update operations -> Option A

4. Quick Check:

   AVL rotations = balance tree = faster operations [OK]

Hint: Rotations fix balance to keep operations fast [OK]

Common Mistakes:

• Thinking rotations delete nodes
• Believing rotations sort nodes
• Assuming rotations increase tree height

2. Which of the following is the correct syntax to perform a right rotation on a node x in an AVL tree?

easy

A. rightRotate(x)

B. x.rightRotate()

C. rotateRight(x)

D. rotate(x, 'right')

Solution

1. Step 1: Identify common function naming

   In AVL tree implementations, the function to rotate right is commonly named rotateRight(node).

2. Step 2: Check options

   rotateRight(x) matches the common syntax. rightRotate(x) and x.rightRotate() are less standard, and rotate(x, 'right') is a generic call not typical in AVL code.

3. Final Answer:

   rotateRight(x) -> Option C

4. Quick Check:

   Right rotation function = rotateRight(node) [OK]

Hint: Look for 'rotateRight' as standard right rotation function name [OK]

Common Mistakes:

• Using method calls on node objects incorrectly
• Confusing rightRotate with rotateRight
• Using generic rotate function without direction

3. Given the following AVL tree insertion sequence: Insert 10, then 20, then 30. Which rotation will be performed to balance the tree?

medium

A. Left rotation

B. Right rotation

C. Left-Right rotation

D. Right-Left rotation

Solution

1. Step 1: Analyze insertion order and imbalance

   Inserting 10, then 20, then 30 creates a right-heavy chain (10 -> 20 -> 30), causing imbalance at 10.

2. Step 2: Determine rotation type

   This is a Right-Right case, fixed by a single left rotation at node 10.

3. Final Answer:

   Left rotation -> Option A

4. Quick Check:

   Right-heavy imbalance = left rotation [OK]

Hint: Right-heavy chain = left rotation to balance [OK]

Common Mistakes:

• Choosing right rotation for right-heavy imbalance
• Confusing Left-Right with Right-Right cases
• Ignoring the order of insertions

4. You implemented a left-right rotation but the AVL tree remains unbalanced after insertion. What is the most likely error?

medium

A. Performed rotations in wrong order

B. Used right rotation instead of left rotation

C. Inserted duplicate keys

D. Forgot to update node heights after rotation

Solution

1. Step 1: Understand rotation steps

   Left-right rotation requires two rotations and updating node heights to maintain AVL properties.

2. Step 2: Identify common mistake

   Not updating heights after rotations causes incorrect balance checks, leaving tree unbalanced.

3. Final Answer:

   Forgot to update node heights after rotation -> Option D

4. Quick Check:

   Update heights after rotations to keep balance [OK]

Hint: Always update heights after rotations [OK]

Common Mistakes:

• Doing rotations in wrong order
• Mixing up left and right rotations
• Ignoring height updates

5. After inserting nodes 30, 20, 25 into an empty AVL tree, which rotation(s) will balance the tree?

hard

A. Single left rotation at 20

B. Left-Right rotation at 30

C. Single right rotation at 30

D. Right-Left rotation at 20

Solution

1. Step 1: Analyze insertion sequence and imbalance

   Inserting 30, then 20, then 25 creates a left-right case: 30 has left child 20, which has right child 25.

2. Step 2: Identify correct rotation

   Left-right imbalance requires a left rotation on 20 followed by a right rotation on 30, called a left-right rotation.

3. Final Answer:

   Left-Right rotation at 30 -> Option B

4. Quick Check:

   Left-right case = left-right rotation [OK]

Hint: Left child with right-heavy subtree = left-right rotation [OK]

Common Mistakes:

• Choosing single rotations instead of double
• Confusing left-right with right-left cases
• Rotating wrong nodes