AVL Balanced Binary Tree: How Four Rotations Fix BST Degeneration (Python Implementation)

What is an AVL Tree?

AVL tree = Binary Search Tree + automatic balancing mechanism. It must satisfy two rules: 1) Follow BST ordering (left smaller, right larger). 2) Maintain balance rule: the absolute difference between left and right subtree heights must not exceed 1.

Balance Factor

Balance factor = left subtree height - right subtree height. Legal AVL balance factors are only -1, 0, or 1. If the absolute difference is ≥2, the tree is unbalanced and must be repaired via rotation.

Four Rotation Types

LL (Left-Left imbalance) → Right rotation

RR (Right-Right imbalance) → Left rotation

LR (Left-Right imbalance) → Left rotation on left child, then right rotation on node

RL (Right-Left imbalance) → Right rotation on right child, then left rotation on node

Real-World Use Cases

High-frequency read, low-write ordered data storage

Operating system process scheduling trees

Database index balancing concepts

Foundation for Red-Black trees (more advanced balanced trees)

Big data ordered retrieval and binary search optimization

Complete Python Implementation

Below is a full AVL tree implementation with height calculation, balance factor, four rotations, and insertion with automatic rebalancing.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # leaf node default height 1

class AVLTree:
    # Get node height (empty node height 0)
    def get_height(self, node):
        if not node:
            return 0
        return node.height

    # Calculate balance factor
    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    # Update node height
    def update_height(self, node):
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

    # Right rotation for LL imbalance
    def right_rotate(self, y):
        x = y.left
        T3 = x.right

        # Rotation
        x.right = y
        y.left = T3

        # Update heights
        self.update_height(y)
        self.update_height(x)
        return x

    # Left rotation for RR imbalance
    def left_rotate(self, x):
        y = x.right
        T2 = y.left

        # Rotation
        y.left = x
        x.right = T2

        # Update heights
        self.update_height(x)
        self.update_height(y)
        return y

    # Insert node + auto balance
    def insert(self, node, val):
        # 1. Standard BST insertion
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self.insert(node.left, val)
        elif val > node.val:
            node.right = self.insert(node.right, val)
        else:
            return node  # duplicate not inserted

        # 2. Update height
        self.update_height(node)

        # 3. Get balance factor
        balance = self.get_balance(node)

        # LL case
        if balance > 1 and val < node.left.val:
            return self.right_rotate(node)

        # RR case
        if balance < -1 and val > node.right.val:
            return self.left_rotate(node)

        # LR case
        if balance > 1 and val > node.left.val:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        # RL case
        if balance < -1 and val < node.right.val:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        return node

    # In-order traversal (maintains sorted order)
    def in_order(self, node, res):
        if not node:
            return
        self.in_order(node.left, res)
        res.append(node.val)
        self.in_order(node.right, res)

# Test
if __name__ == "__main__":
    avl = AVLTree()
    root = None

    # Intentionally insert in sorted order (BST would degenerate, AVL stays balanced)
    nums = [1, 2, 3, 4, 5, 6, 7]
    for num in nums:
        root = avl.insert(root, num)

    res = []
    avl.in_order(root, res)
    print("AVL tree in-order result:", res)
    print("Perfectly balanced, no skew degeneration!")

Code Output

AVL tree in-order result: [1, 2, 3, 4, 5, 6, 7]

Perfectly balanced, no skew degeneration!

BST vs AVL Comparison

BST: Ordered insertion collapses into a linked list, performance drops to O(n), unstable.

AVL: Maintains permanent balance regardless of insertion order, guaranteeing O(log n) query performance.

Common Pitfalls for Beginners

Must update node heights after rotation, otherwise balance factor calculation becomes incorrect.

Do not confuse the four rotation scenarios; identify imbalance type before applying fix.

AVL excels at queries but insert/delete are slower due to rebalancing overhead.

Balance factor outside ±1 indicates imbalance and must be corrected immediately.