• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python AVL Trees

← Previous Next →

An AVL Tree is a self-balancing Binary Search Tree (BST). It ensures that the height difference between left and right subtrees (called the balance factor) is never more than 1.

Why AVL?

In regular BSTs, inserting data in sorted order can cause the tree to become skewed, degrading performance to O(n).
AVL Trees guarantee O(log n) performance by automatically balancing themselves.

🔹 Balance Factor

For every node:

Balance Factor = Height(left subtree) - Height(right subtree)

  • Must be -1, 0, or 1

  • If not, the tree rotates to fix itself

🔹 Node Structure

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

🔹 AVL Tree Insert Function

def get_height(node):
    return node.height if node else 0

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

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

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

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

    # Update height
    root.height = 1 + max(get_height(root.left), get_height(root.right))

    # Get balance factor
    balance = get_balance(root)

    # Balancing cases
    if balance > 1 and key < root.left.key:  # Left Left
        return right_rotate(root)

    if balance < -1 and key > root.right.key:  # Right Right
        return left_rotate(root)

    if balance > 1 and key > root.left.key:  # Left Right
        root.left = left_rotate(root.left)
        return right_rotate(root)

    if balance < -1 and key < root.right.key:  # Right Left
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

🔹 Inorder Traversal (Sorted Output)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=' ')
        inorder(root.right)
Example
root = None
for val in [10, 20, 30, 40, 50, 25]:
    root = insert(root, val)

inorder(root)  # Output: 10 20 25 30 40 50

✅ The AVL Tree self-balances as elements are inserted.

🔹 Rotations Summary

Type Rotation Needed
Left-Left Single Right Rotate
Right-Right Single Left Rotate
Left-Right Left + Right Rotate
Right-Left Right + Left Rotate

🔹 Use Cases of AVL Trees

  • Search-intensive applications

  • Indexing and databases

  • Memory-constrained systems

  • Auto-balancing tree structures

Practice Questions

Q1. Write a Python program to create an AVL Tree using values: 50, 30, 70, 20, 40.

Q2. Write a Python program to insert value 25 and check if the tree balances itself.

Q3. Write a Python program to perform and print Inorder traversal of the AVL Tree.

Q4. Write a Python program to modify your AVL Tree code to count the total number of nodes.

Q5. Write a Python program to display the balance factor of each node during insertions.

Q6. Write a Python program to perform a right rotation manually and print the updated tree.

Q7. Write a Python program to add print statements inside rotation functions to trace when and what type of rotation happens.

Q8. Write a Python program to delete a node from the AVL Tree and ensure it remains balanced.

Q9. Write a Python program to compare basic insertion time between an AVL Tree and a regular BST.

Q10. Write a Python program to count and print the number of leaf nodes in the AVL Tree.

← Previous Next →

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top