AVL Trees - The Art of Staying Balanced in a Dynamic World of Data

January 21, 2023 — #DSA #Trees

Hey everyone, and welcome back to the blog! When we talk about efficient data storage and retrieval, Binary Search Trees (BSTs) are often one of the first data structures that come to mind. They can be wonderfully fast... if they are balanced. But what happens when they become lopsided? Performance can degrade significantly. This is where self-balancing BSTs save the day, and the pioneering hero in this category is the AVL Tree.

Named after its inventors, Adelson-Velsky and Landis (hence A-V-L), AVL trees were the first data structure to be described as a self-balancing binary search tree. Even today, understanding them is crucial for any developer where efficient data handling is key. Let's explore what makes AVL trees tick!

What Makes an AVL Tree Special? The Balancing Act

An AVL tree isn't just any binary search tree; it's a BST with an extra rule that keeps it in shape. This rule ensures that the tree remains "balanced," preventing it from becoming too skewed to one side, which could turn search operations into slow linear scans.

Here are its defining properties:

Height-Balance Property: For every node in an AVL tree, the heights of its left and right subtrees can differ by at most 1. This difference is often called the "balance factor" of a node.
Logarithmic Height: Because of this strict balancing, the height of an AVL tree with n nodes is always O(log n). This is the magic that guarantees fast operations.
Recursive AVL Property: Both the left and right subtrees of any node in an AVL tree are also AVL trees themselves.

This self-balancing act ensures that operations like search, insertion, and deletion maintain their efficiency.

The Core Mechanics: Keeping the Balance with Rotations

To maintain the height-balance property after an insertion or deletion might have disturbed it, AVL trees perform operations called rotations. These are localized restructuring operations that change the arrangement of nodes to restore balance without violating the BST property.

Before we look at rotations, let's define some helper functions often used with AVL trees:

class Node:
    key     // The value stored in the node
    left    // Pointer to the left child
    right   // Pointer to the right child
    height  // Height of the subtree rooted at this node

// Function to get the height of a node
// (Handles null nodes gracefully)
function height(node):
    if node is null:
        return 0 // Height of a null tree is 0
    return node.height

// Function to calculate the balance factor of a node
// Balance Factor = height(left subtree) - height(right subtree)
function get_balance(node):
    if node is null:
        return 0
    return height(node.left) - height(node.right)

// Function to get the node with the minimum key value found in that tree
// (Used in deletion)
function get_min_value_node(node):
    current = node
    // Loop down to find the leftmost leaf
    while current.left is not null:
        current = current.left
    return current

Now, for the rotations. There are two basic types of rotations:

Right Rotate: Performed when a tree becomes "left-heavy."

function right_rotate(y):
    x = y.left          // x is y's left child
    T2 = x.right        // T2 is x's right child (subtree)

    // Perform rotation
    x.right = y         // y becomes x's right child
    y.left = T2         // T2 becomes y's left child

    // Update heights (order matters: y first, then x)
    y.height = 1 + max(height(y.left), height(y.right))
    x.height = 1 + max(height(x.left), height(x.right))

    // Return the new root of this rotated subtree
    return x

A right rotation effectively pulls x up and pushes y down to the right, rebalancing a left-heavy situation around y.

Left Rotate: Performed when a tree becomes "right-heavy."

function left_rotate(x):
    y = x.right         // y is x's right child
    T2 = y.left         // T2 is y's left child (subtree)

    // Perform rotation
    y.left = x          // x becomes y's left child
    x.right = T2        // T2 becomes x's right child

    // Update heights (order matters: x first, then y)
    x.height = 1 + max(height(x.left), height(x.right))
    y.height = 1 + max(height(y.left), height(y.right))

    // Return the new root of this rotated subtree
    return y

A left rotation pulls y up and pushes x down to the left, rebalancing a right-heavy situation around x.

These rotations, sometimes combined (like a Left-Right or Right-Left rotate), are the key to an AVL tree's self-balancing prowess.

Working with AVL Trees: Key Operations

The standard BST operations are adapted for AVL trees with an additional step: after an insertion or deletion, the tree checks for balance and performs rotations if necessary.

Insertion

Goal: Insert a new node with a given key while maintaining the AVL property.
Process: The insertion initially follows the standard BST insertion logic. After the node is inserted, we traverse back up the tree from the inserted node to the root, updating the heights of the nodes. At each node, we check its balance factor. If a node becomes unbalanced (balance factor > 1 or < -1), appropriate rotations are performed to restore balance.
Time Complexity: O(log n) because the tree height is O(log n), and the rebalancing (rotations) also takes logarithmic time in the worst case.
Space Complexity: O(log n) for the recursion stack.

function insert(root, key):
    // 1. Perform standard BST insertion
    if root is null:
        return Node(key) // Create new node, height is 1 by default if Node constructor sets it.
                        // Assuming Node() sets height = 1 for a new leaf.
 
    if key < root.key:
        root.left = insert(root.left, key)
    else if key > root.key:
        root.right = insert(root.right, key)
    else: // Duplicate keys are not allowed (or handled as per specific AVL policy)
        return root

    // 2. Update height of this ancestor node
    root.height = 1 + max(height(root.left), height(root.right))

    // 3. Get the balance factor of this ancestor node to check if it became unbalanced
    balance = get_balance(root)

    // 4. If unbalanced, then there are 4 cases for rotation

    // Left Left Case (LL)
    if balance > 1 and key < root.left.key:
        return right_rotate(root)

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

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

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

    // If balanced, return the (unchanged) node pointer
    return root

Deletion

Goal: Delete a node with a given key while maintaining the AVL property.
Process: Deletion starts like standard BST deletion (finding the node, and if it has two children, replacing it with its in-order successor or predecessor). After deletion, we trace back up the tree, updating heights and checking balance factors at each node. If an imbalance is detected, appropriate rotations are performed.
Time Complexity: O(log n) due to the balanced nature of the AVL tree.
Space Complexity: O(log n) for the recursion stack.

function delete(root, key):
    // 1. Perform standard BST delete
    if root is null:
        return root

    if key < root.key:
        root.left = delete(root.left, key)
    else if key > root.key:
        root.right = delete(root.right, key)
    else: // Node to be deleted found
        // Node with only one child or no child
        if root.left is null or root.right is null:
            temp = root.left if root.left is not null else root.right
   
            if temp is null: // No child case
                temp = root
                root = null
            else: // One child case
                root = temp // Copy the contents of the non-empty child
        else:
            // Node with two children: Get the inorder successor (smallest in the right subtree)
            temp = get_min_value_node(root.right)
            // Copy the inorder successor's data to this node
            root.key = temp.key
            // Delete the inorder successor
            root.right = delete(root.right, temp.key)

    // If the tree had only one node then return
    if root is null:
        return root

    // 2. Update height of the current node
    root.height = 1 + max(height(root.left), height(root.right))

    // 3. Get the balance factor
    balance = get_balance(root)

    // 4. If unbalanced, perform rotations (4 cases similar to insertion, but conditions depend on balance factors of subtrees)

    // Left Left Case (LL)
    if balance > 1 and get_balance(root.left) >= 0:
        return right_rotate(root)

    // Left Right Case (LR)
    if balance > 1 and get_balance(root.left) < 0:
        root.left = left_rotate(root.left)
        return right_rotate(root)

    // Right Right Case (RR)
    if balance < -1 and get_balance(root.right) <= 0:
        return left_rotate(root)

    // Right Left Case (RL)
    if balance < -1 and get_balance(root.right) > 0:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

Search

Goal: Find a node with a given key.
Process: This operation is exactly the same as in a standard Binary Search Tree. You compare the key with the current node's key and decide whether to go left or right.
Time Complexity: O(log n) due to the balanced nature of the AVL tree.
Space Complexity: O(log n) for the recursion stack (or O(1) for an iterative version).

function search(root, key):
    // Base Cases: root is null or key is present at root
    if root is null or root.key == key:
        return root

    // Key is greater than root's key
    if key > root.key:
        return search(root.right, key)
 
    // Key is smaller than root's key
    return search(root.left, key)

Where Do AVL Trees Shine? Real-World Applications

AVL trees, with their guarantee of O(log n) performance for search, insertion, and deletion, are valuable in scenarios where:

Frequent lookups are necessary.
The data changes often (insertions and deletions), and maintaining search efficiency is critical.
A guaranteed worst-case performance for dictionary operations is required.

Some common applications include:

Database Indexing: AVL trees (or more commonly, their disk-based cousins like B-trees) are used to index data in databases to speed up search and query operations. The self-balancing ensures that index lookups remain fast even as data is added or removed.
Compiler Implementations: Used in compilers to efficiently store and manage symbol tables (which map identifiers like variable names to their attributes).
File Systems: Can be used in file systems to maintain directory structures and manage file metadata, ensuring efficient file lookups.
Network Routers: Used in network routers to store routing tables, allowing for efficient packet forwarding based on destination addresses.

They are also used in various other applications where efficient dynamic dictionary operations (search, insert, delete) are required, and the overhead of maintaining balance is acceptable for the guaranteed performance.

Key Takeaways

AVL trees are self-balancing binary search trees that maintain a height difference of at most 1 between left and right subtrees of any node.
This balance is achieved through rotations (single or double) performed after insertions or deletions that might cause an imbalance.
They guarantee O(log n) time complexity for search, insertion, and deletion operations, making them highly efficient and predictable.
AVL trees are foundational in computer science and have practical applications in databases, compilers, and networking.

While other self-balancing trees like Red-Black trees exist (which might have slightly less strict balancing but can sometimes be faster for insertions/deletions due to fewer rotations on average), AVL trees remain a classic and important example of how to maintain performance in dynamic tree structures.