DSA Basics

Arrays

Linked Lists

Stacks & Queues

Hash Tables

Trees

Graphs

Shortestpath

Minimum spanning tree

DSA Advanced

AVL Trees

❮ Previous Next ❯

AVL Trees

Key Takeaways: The AVL Tree is a type of Binary Search Tree named after two Soviet inventors Georgy Adelson-Velsky and Evgenii Landis who invented the AVL Tree in 1962.

AVL trees are self-balancing, which means that the tree height is kept to a minimum so that a very fast runtime is guaranteed for searching, inserting and deleting nodes, with time complexity O(log n).

In our previous tutorial, we learned about the Binary Search Tree (BST).

A standard BST is incredibly fast, but it has one massive flaw. If you insert data that is already sorted (like 10, 20, 30, 40), the tree never branches out.

It simply forms a long, straight line down the right side!

When a tree becomes a straight line, searching through it drops to O(n) linear time. It essentially just becomes a slow Linked List.

1. The Solution: Self-Balancing Trees

Computer Scientists realized they needed a tree that would fix itself whenever it started to become lopsided.

This led to the creation of the AVL Tree.

An AVL Tree is exactly like a normal Binary Search Tree, but it strictly enforces one mathematical rule: The heights of the left and right subtrees of ANY node cannot differ by more than 1.

If the tree detects that it is becoming lopsided, it instantly triggers a "Rotation" to correct itself.

Visual representation of a balanced AVL tree

An AVL Tree maintains perfect balance, keeping the height as short as possible.

2. The Balance Factor

How does an AVL Tree know when it is lopsided?

Every node in an AVL tree calculates its own Balance Factor.

The formula is very simple: Balance Factor = Height(Left Subtree) - Height(Right Subtree)

A node is considered completely healthy and balanced if its Balance Factor is -1, 0, or 1.

If the Balance Factor ever becomes 2 or -2, an alarm goes off! The tree immediately pauses and reorganizes the nodes to fix the imbalance.

3. Tree Rotations

When an alarm goes off (a Balance Factor hits 2 or -2), the AVL Tree fixes itself using a Rotation.

A rotation is a mechanical step where parent and child nodes swap places while keeping the left-to-right sorting rules intact.

There are four specific situations (cases) where a tree becomes unbalanced, and four specific rotations to fix them:

Case 1: Left-Left (LL)

Case 2: Right-Right (RR)

Case 3: Left-Right (LR)

Case 4: Right-Left (RL)

4. Coding an AVL Tree (Python)

Implementing an AVL tree from scratch is one of the most challenging (but rewarding) tasks for a beginner in Data Structures!

We must write functions to calculate the height, get the balance factor, perform rotations, and then combine it all into our standard Insert function.

AVL Tree Implementation

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # New nodes are added at height 1


class AVLTree:
    def insert(self, root, key):
        # 1. Perform standard BST insert
        if not root:
            return TreeNode(key)
        elif key < root.val:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
        # 2. Update the height of this ancestor node
        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        # 3. Get the balance factor
        balance = self.get_balance(root)
        # 4. If unbalanced, test the 4 cases!
        # Case 1: Left-Left
        if balance > 1 and key < root.left.val:
            return self.right_rotate(root)
        # Case 2: Right-Right
        if balance < -1 and key > root.right.val:
            return self.left_rotate(root)
        # Case 3: Left-Right
        if balance > 1 and key > root.left.val:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # Case 4: Right-Left
        if balance < -1 and key < root.right.val:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)
        return root
    def left_rotate(self, z):
        y = z.right
        T2 = y.left
        # Perform rotation
        y.left = z
        z.right = T2
        # Update heights
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y
    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        # Perform rotation
        y.right = z
        z.left = T3
        # Update heights
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        return y
    def get_height(self, root):
        if not root:
            return 0
        return root.height
    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)
    def pre_order(self, root):
        if not root:
            return
        print(root.val, end=" ")
        self.pre_order(root.left)
        self.pre_order(root.right)


# Let's see the AVL tree dynamically balance itself!
my_tree = AVLTree()
root = None


# We insert data in a completely sorted order
nums = [10, 20, 30, 40, 50, 25]


for num in nums:
    root = my_tree.insert(root, num)


print("Pre-Order Traversal (Shows the root has successfully changed!):")
my_tree.pre_order(root)

Exercise 1 of 1

?

At what point does an AVL tree trigger a rotation to rebalance itself?

❮ Previous Next ❯