AVL Tree Algorithm: Height-Balanced Binary Tree Explained with Examples

An AVL Tree is a type of self-balancing binary search tree (BST) where the difference in height between the left and right subtrees of any node is always at most one. This difference is known as the balance factor. Invented by Adelson-Velsky and Landis in 1962, the AVL tree was the first data structure to automatically maintain balance, ensuring efficient operations like insertion, deletion, and search.

Table of Contents

Why AVL Tree?

In a regular binary search tree, the complexity of operations can degrade to O(n) in the worst case when the tree becomes skewed. By enforcing height balance through rotations, AVL trees guarantee that operations like search, insert, and delete are performed in O(log n) time.

Properties of AVL Trees

Binary Search Tree property is always maintained.
Balance factor of any node = Height(left subtree) – Height(right subtree).
Balance factor can only be -1, 0, or +1.
Height of an AVL tree with n nodes is restricted to O(log n).

AVL Tree Balance Factor

For any node:

If balance factor = 0 ⇒ Both subtrees have equal height.
If balance factor = +1 ⇒ Left subtree is taller by one.
If balance factor = -1 ⇒ Right subtree is taller by one.

Rotations in AVL Tree

Whenever an insertion or deletion causes imbalance, the tree applies rotations to restore balance. There are four types of rotations:

Right Rotation (LL Rotation) – Occurs when a node is inserted into the left subtree of the left child.
Left Rotation (RR Rotation) – Occurs when a node is inserted into the right subtree of the right child.
Left-Right Rotation (LR Rotation) – Occurs when a node is inserted into the right subtree of the left child.
Right-Left Rotation (RL Rotation) – Occurs when a node is inserted into the left subtree of the right child.

AVL Tree Example

Suppose we insert the sequence: 10, 20, 30 into an empty AVL Tree. After inserting 30, the tree becomes imbalanced and requires a Left Rotation (RR Case).

After applying rotation, the balanced AVL Tree structure looks like:

Visualizing LR Rotation

Consider insertion sequence: 30, 10, 20. After inserting 20, the tree becomes imbalanced, requiring a Left-Right Rotation (LR Case).

After performing rotations, we get a height-balanced tree:

AVL Tree Algorithm (Insertion)

Insert the new node following standard BST insertion.
Update the height of the ancestor nodes.
Check the balance factor of each ancestor.
If an imbalance is found, apply the appropriate rotation (LL, RR, LR, or RL).

AVL Tree Insertion Code Example (Python)


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

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

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

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

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

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

    node.height = 1 + max(height(node.left), height(node.right))
    balance = get_balance(node)

    # LL Rotation
    if balance > 1 and key < node.left.key:
        return right_rotate(node)

    # RR Rotation
    if balance < -1 and key > node.right.key:
        return left_rotate(node)

    # LR Rotation
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # RL Rotation
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

Interactive Example: Constructing an AVL Tree

You can try inserting different sequences of numbers in an AVL Tree visualizer (like a web-based tool) to watch rotations happen automatically. For small examples, tracing balance factors on paper also helps to understand rotations step by step.

Complexity of AVL Tree Operations

Search: O(log n)
Insertion: O(log n)
Deletion: O(log n)

Applications of AVL Trees

Indexing and searching in databases.
Memory indexing in compilers.
Scheduling systems where fast lookups are critical.
Telecommunication routing where balanced lookup times are required.

Conclusion

The AVL Tree Algorithm ensures search and update operations in logarithmic time through strict height balancing. By employing rotations (LL, RR, LR, RL), AVL trees provide a robust solution where balance is critical. Understanding AVL trees is an essential step in mastering advanced data structures and designing efficient systems.