AVL Tree

Introduction

An AVL Tree is a type of self-balancing binary search tree (BST), named after its inventors Adelson-Velsky and Landis. Introduced in 1962, it was the first dynamic data structure designed to maintain balance during insertions and deletions, thereby ensuring efficient operations with O(log n) time complexity.

Like all binary search trees, an AVL tree maintains a strict ordering rule: for any given node, values in the left subtree are smaller, and values in the right subtree are larger. What sets AVL trees apart is their balance condition — the difference in height between left and right subtrees must not exceed 1.

Why AVL Trees?

Binary search trees are efficient — if they are balanced. Without self-balancing, a BST can degrade into a linked list in the worst case, with O(n) lookup time.

AVL trees ensure:

• Faster lookups, insertions, deletions
• Guaranteed logarithmic depth
• Consistency across operations

They are ideal in systems where reads and writes are interleaved frequently and consistent performance is critical (e.g., databases, memory indexing, caches).

Balance Factor

The balance factor of a node in an AVL tree is calculated as:

balanceFactor = height(left subtree) - height(right subtree)

Valid values are:

• -1 → right-heavy
• 0 → balanced
• +1 → left-heavy

If a node’s balance factor becomes less than -1 or greater than 1, the tree must rebalance using rotations.

Rotations in AVL Trees

Rotations are local operations that restore balance by restructuring subtrees.

There are four types of rotations:

1. Right Rotation (LL Case)

Occurs when a node is inserted into the left subtree of the left child.

      z
     /
    y
   /
  x

Rotated:

    y
   / \
  x   z

2. Left Rotation (RR Case)

Occurs when a node is inserted into the right subtree of the right child.

  z
   \
    y
     \
      x

Rotated:

    y
   / \
  z   x

3. Left-Right Rotation (LR Case)

Insertion into the right subtree of the left child.

      z
     /
    y
     \
      x

Rotated:

1. Left Rotation on y
2. Right Rotation on z

Result:

    x
   / \
  y   z

4. Right-Left Rotation (RL Case)

Insertion into the left subtree of the right child.

  z
   \
    y
   /
  x

Rotated:

1. Right Rotation on y
2. Left Rotation on z

Result:

    x
   / \
  z   y

AVL Tree Operations

Insertion

1. Perform regular BST insertion.
2. Update heights going up the tree.
3. Recalculate balance factors.
4. Apply appropriate rotation(s) if balance factor exceeds ±1.

Deletion

1. Perform regular BST deletion.
2. Recalculate balance factors moving upward.
3. Apply rotations to restore balance if needed.

Deletion is more complex, as it can trigger multiple rebalances along the path back to the root.

AVL Tree Implementation in 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)
    if 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)

    if balance > 1 and key < node.left.key:
        return right_rotate(node)
    if balance < -1 and key > node.right.key:
        return left_rotate(node)
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

AVL Tree vs Other Trees

AVL Tree Use Cases

• Databases: Indexing and range queries
• Memory allocators: Tracking free/used blocks
• Networking: Routing tables and prefix trees
• Real-time systems: Deterministic performance for insert/delete
• Compiler/interpreter internals: Symbol tables, lookup structures

Performance Summary

AVL Tree Visualization (Conceptual)

Initial Insertion (10):
    10

Insert 20:
    10
      \
      20

Insert 30 (Triggers RR Rotation):
    10
      \
      20
        \
        30

Becomes:

    20
   /  \
  10  30

Understanding tree rotations visually helps in learning how AVL trees rebalance after insertions or deletions.

Drawbacks of AVL Trees

• More complex than plain BST or Red-Black Trees
• More frequent rotations (especially insert-heavy workloads)
• May be overkill for read-only or append-only datasets
• Slightly higher memory overhead (height field)

When to Use AVL Trees

Use AVL Trees when:

• You need fast lookups
• Your data set changes dynamically (not static)
• You want consistent worst-case performance
• You’re building memory-sensitive structures

Avoid if:

• Insert/delete patterns are highly unbalanced
• Simpler trees suffice
• You need more cache-friendly structures (e.g., B-Trees for disk)

Conclusion

The AVL Tree is a foundational data structure in computer science, combining the binary search property with self-balancing logic to ensure fast, reliable access to dynamic data. With O(log n) performance across insertions, deletions, and lookups, AVL trees are invaluable in scenarios where performance and balance are non-negotiable.

While more complex than basic BSTs, and requiring more rotations than Red-Black Trees, AVL Trees offer superior balance guarantees — making them a smart choice in latency-sensitive and search-intensive applications.

Related Keywords

• Binary Tree
• Binary Search Tree
• Unbalanced Tree
• Inorder Traversal
• Red Black Tree
• Self Balancing Tree
• Tree Traversal
• Tree