NoteVerse

AVL Tree

Comprehensive study notes, diagrams, and exam preparation for AVL Tree.

AVL Tree

Definition

An AVL Tree is a self-balancing Binary Search Tree in which, for every node, the difference between the heights of the left and right subtrees is at most 1.

This difference is called the balance factor:

Balance Factor = Height of Left Subtree − Height of Right Subtree

  • For an AVL tree, the balance factor of every node must be -1, 0, or +1

If any node violates this condition after insertion or deletion, the tree is rebalanced using rotations.

Main Content

1. Binary Search Tree Property

An AVL tree is first and foremost a Binary Search Tree, so it follows all BST rules.

  • The left subtree of a node contains only keys smaller than the node’s key.
  • The right subtree of a node contains only keys greater than the node’s key.

This ordering makes searching efficient because at each step, half of the remaining possibilities can be ignored.

Example:

        30
       /  \
     20    40
    /  \     \
   10  25     50

In this tree:

  • All values in the left subtree of 30 are less than 30
  • All values in the right subtree of 30 are greater than 30
  • The same rule applies recursively to every node

Because AVL trees preserve BST ordering, they support:

  • Fast searching
  • Ordered traversal
  • Efficient minimum/maximum finding

However, a normal BST can become unbalanced. For example, inserting 10, 20, 30, 40, 50 in order can create a chain:

10
  \
  20
    \
    30
      \
      40
        \
         50

This makes search time linear instead of logarithmic. AVL trees prevent this by maintaining balance.

2. Balance Factor and Height Balance

The most important feature of an AVL tree is height balance.

For every node, we compute:

  • Height of left subtree
  • Height of right subtree
  • Balance factor = left height − right height

Possible balance factors:

0

  • → perfectly balanced

+1

  • → left subtree is one level taller

-1

  • → right subtree is one level taller

If the balance factor becomes +2 or -2, the node is considered unbalanced and rebalancing is required.

Example of a balanced tree:

        30
       /  \
     20    40
    /        \
   10         50

Balance factors:

  • Node 30 → left height = 2, right height = 2, BF = 0
  • Node 20 → left height = 1, right height = 0, BF = +1
  • Node 40 → left height = 0, right height = 1, BF = -1

This tree is AVL-balanced.

Example of imbalance:

      30
     /
   20
   /
 10

Balance factors:

  • Node 30 → BF = +2
  • Node 20 → BF = +1
  • Node 10 → BF = 0

This is not allowed in an AVL tree, so rotations are needed.

Why this matters:

  • A balanced tree has height close to log n
  • Search, insertion, and deletion remain efficient
  • Worst-case performance is controlled

3. Rotations and Rebalancing

When an insertion or deletion causes imbalance, AVL trees restore balance using rotations. Rotations are local restructuring operations that preserve the BST property while reducing height.

There are four main rotation cases:

a) Left-Left (LL) Case

This happens when a node becomes unbalanced because a new node is inserted into the left subtree of the left child.

Example:

        30
       /
     20
    /
   10

To fix this, perform a right rotation on 30:

      20
     /  \
   10    30

b) Right-Right (RR) Case

This happens when a node becomes unbalanced because insertion occurs in the right subtree of the right child.

Example:

  10
    \
     20
       \
        30

To fix this, perform a left rotation on 10:

      20
     /  \
   10    30

c) Left-Right (LR) Case

This happens when insertion occurs in the right subtree of the left child.

Example:

      30
     /
   10
     \
      20

Fix:

  1. Left rotate 10
  2. Right rotate 30

Result:

      20
     /  \
   10    30

d) Right-Left (RL) Case

This happens when insertion occurs in the left subtree of the right child.

Example:

   10
     \
      30
     /
   20

Fix:

  1. Right rotate 30
  2. Left rotate 10

Result:

      20
     /  \
   10    30

Why rotations are important:

  • They restore height balance quickly
  • They preserve sorted order
  • They keep tree height logarithmic

Working / Process

1. Insert a node using BST rules

  • Start from the root
  • Move left if the new key is smaller
  • Move right if the new key is larger
  • Place the node at the appropriate leaf position

2. Update heights and check balance factors

  • After insertion or deletion, move back up the tree
  • Recalculate height of each affected node
  • Compute balance factor to detect imbalance

3. Perform the required rotation

  • If balance factor becomes +2 or -2, identify the case:
    • LL → right rotation
    • RR → left rotation
    • LR → left rotation on child, then right rotation
    • RL → right rotation on child, then left rotation
  • After rotation, update heights again

Example of insertion process:

Insert: 10, 20, 30

  • Insert 10 → tree is just one node
  • Insert 20 → 20 becomes right child of 10
  • Insert 30 → causes RR imbalance at 10
  • Left rotate 10

Final tree:

   20
  /  \
10    30

This process ensures the tree remains balanced after every modification.

Advantages / Applications

Guaranteed logarithmic time operations

  • : Search, insert, and delete all take O(log n) in the worst case.

Better balance than ordinary BSTs

  • : The tree remains height-balanced automatically, preventing degeneration into a linked list.

Useful in systems requiring frequent searching

  • : AVL trees are appropriate where search performance is critical and the dataset changes dynamically.

Applications include:

  • Database indexing
  • Memory management systems
  • File systems
  • Compilers and interpreters
  • Symbol tables
  • Dictionary and lookup operations

Summary

  • AVL Tree is a self-balancing BST.
  • It keeps balance using balance factor and rotations.
  • Important terms to remember: Balance Factor, Rotation, LL, RR, LR, RL
← Prev: Search
Next: Heap →