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

Need a 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

Need a 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

Need a 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

Need a hint?

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