AVL Trees: Visualizing Self-Balancing BSTs

AVL Trees: Visualizing Self-Balancing BSTs

Binary Search Trees (BSTs) are fundamental data structures, offering efficient search, insertion, and deletion operations. However, their performance degrades to O(n) in the worst-case scenario when the tree becomes skewed. AVL trees, named after their inventors Adelson-Velsky and Landis, solve this problem by being self-balancing BSTs.

What is Self-Balancing?

Self-balancing means that the structure of the tree is automatically adjusted during insertions and deletions to maintain a balanced state. This ensures that the height of the tree remains logarithmic, guaranteeing O(log n) performance for most operations.

The Balance Factor

The core of AVL tree balancing lies in the balance factor. For each node, the balance factor is calculated as the difference between the height of its left subtree and the height of its right subtree: balanceFactor = height(leftSubtree) - height(rightSubtree). An AVL tree maintains balance by ensuring that the balance factor of every node in the tree is either -1, 0, or 1.

Rotations: The Balancing Act

When an insertion or deletion violates the balance factor criteria, AVL trees use rotations to re-balance the tree locally. There are four primary types of rotations:

• Right Rotation: Used when a node's balance factor becomes -2, and its right child has a balance factor of -1 or 0.
• Left Rotation: Used when a node's balance factor becomes 2, and its left child has a balance factor of 1 or 0.
• Left-Right Rotation: A combination of a left rotation on the left child followed by a right rotation on the unbalanced node. Used when a node's balance factor becomes 2, and its left child has a balance factor of -1.
• Right-Left Rotation: A combination of a right rotation on the right child followed by a left rotation on the unbalanced node. Used when a node's balance factor becomes -2, and its right child has a balance factor of 1.

Visualizing the Rotations

Let's illustrate with some basic scenarios:

Right Rotation

Imagine a subtree where Node A's balance factor is 2, and its left child Node B's balance factor is 1. B has left child C.

Before rotation (A, balance factor = 2 ):

        A
       / 
      B   ...
     / 
    C
  

After Right Rotation on A:

       B
      / \
     C   A
         \
          ...
  

Left Rotation

Imagine a subtree where Node A's balance factor is -2, and its right child Node B's balance factor is -1. B has right child C.

Before rotation (A, balance factor = -2 ):

        A
         \
          B
           \
            C
  

After Left Rotation on A:

        B
       / \
      A   C
     /
    ...
  

Left-Right Rotation

Imagine a subtree where Node A's balance factor is 2, and its left child Node B's balance factor is -1.

Before Rotation:

          A
         / 
        B   ...
         \
          C
            

First a Left Rotation at B (B's right child C is pivoted):

          A
         / 
        C   ...
       / \
      B    
     

Then a Right Rotation on A (C is pivoted up):

          C
         / \
        B   A
           \
            ...
     

Right-Left Rotation

Imagine Subtree where Node A Balance Factor is -2, and Right Child B Balance Factor is 1. B has left child C.

Before Rotation:

          A
           \
            B
           / 
          C
     

First a Right Rotation on B node, and C becames the pivoted node.

          A
           \
            C
           / \
          B   
     

Finally do a Left Rotation on A node, and C becames the pivoted node in this operation

          C
         / \
        A  B
       /
          

Why Use AVL Trees?

AVL trees provide a significant advantage in scenarios where frequent insertions and deletions are performed, and guaranteed O(log n) time complexity is crucial. They are more balanced than other search trees like BSTs, however, they might involve more rotations than splay trees or red-black trees. Knowing your typical workload is important for optimal data structure choice.

Further Exploration

Understanding AVL trees is an important step in mastering data structures and algorithms. Check out other helpful resources at DSA Beginner Sheet. Consider practice problems on various coding platforms to build your fluency. And don't miss our flashcards to enhance your spaced repetition learning of these concepts. Also, consider mentorship to boost you up!