Neural Sync Active

17. AVL Trees — Self-Balancing BSTs

Registry Synced

17. AVL Trees — Self-Balancing BSTs

635 words

3 min read

Reading compass

Now · 1. Balance Factor

17. AVL Trees — Self-Balancing BSTs

What problem does this solve? A BST can degenerate to O(n) height if inserted in sorted order. AVL trees maintain balance by automatically rotating nodes after every insert/delete, guaranteeing O(log n) height.

1. Balance Factor

Balance Factor = height(left subtree) − height(right subtree) An AVL tree requires |balance factor| ≤ 1 for every node. (Diagram)

2. AVL Rotations

When a node becomes unbalanced (bf = ±2), we perform one of four rotations:

Imbalance	Type	Rotation
Left-Left (LL)	Insert into left subtree of left child	Right rotate
Right-Right (RR)	Insert into right subtree of right child	Left rotate
Left-Right (LR)	Insert into right subtree of left child	Left then Right
Right-Left (RL)	Insert into left subtree of right child	Right then Left

(Diagram)

3. Implementation


python
# runnable
class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1
class AVLTree:
    def __init__(self):
        self.root = None
    def height(self, node):
        return node.height if node else 0
    def balance_factor(self, node):
        return self.height(node.left) - self.height(node.right) if node else 0
    def update_height(self, node):
        node.height = 1 + max(self.height(node.left), self.height(node.right))
    def right_rotate(self, z):
        """Right rotate (fixes LL imbalance)."""
        y = z.left
        T2 = y.right
        y.right = z
        z.left = T2
        self.update_height(z)
        self.update_height(y)
        return y
    def left_rotate(self, z):
        """Left rotate (fixes RR imbalance)."""
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        self.update_height(z)
        self.update_height(y)
        return y
    def insert(self, val):
        """Insert val into AVL tree. O(log n)."""
        self.root = self._insert(self.root, val)
    def _insert(self, node, val):
        if node is None:
            return AVLNode(val)
        # Standard BST insert
        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  # No duplicates
        # Update height
        self.update_height(node)
        # Check balance and rotate
        bf = self.balance_factor(node)
        # LL case
        if bf > 1 and val < node.left.val:
            return self.right_rotate(node)
        # RR case
        if bf < -1 and val > node.right.val:
            return self.left_rotate(node)
        # LR case
        if bf > 1 and val > node.left.val:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
        # RL case
        if bf < -1 and val < node.right.val:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)
        return node
    def inorder(self):
        result = []
        def _t(n):
            if n:
                _t(n.left)
                result.append(n.val)
                _t(n.right)
        _t(self.root)
        return result
# Test
avl = AVLTree()
for v in [10, 20, 30, 40, 50, 25]:
    avl.insert(v)
print(f"Inorder: {avl.inorder()}")
# Trace insert 10, 20, 30:
# Insert 10: root = 10
# Insert 20: 10.right = 20, bf(10) = -1 OK
# Insert 30: 10.right = 20, 20.right = 30
#   bf(10) = 0 - 2 = -2 (RR), bf(20) = -1
#   Left rotate at 10 → 20 becomes root
print("AVL tree is balanced after every insert!")

4. Complexity

Property	Value
Height	≈ 1.44 log₂(n) — guaranteed
Minimum nodes for height h	S(h) = S(h−2) + S(h−1) + 1
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

Practice Questions

Q1. Insert [36, 40, 32, 18, 72, 5, 35, 34] into an AVL tree. Which nodes are leaves? Q2. What's the difference between an LL imbalance and an LR imbalance? Q3. Why can't we use simple BST rotations for self-balancing in all cases? Q4. How many nodes minimum in an AVL tree of height 5?

Answers

A1. After all insertions and rotations, leaf nodes are: 5, 35, 72. (Note: 32 gets rebalanced and becomes a leaf after rotations.)

A2. LL: insertion in left-left grandchild → single right rotate. LR: insertion in left-right grandchild → double rotate (left then right).

A3. BST rotations only fix local imbalance temporarily. AVL rotations use balance factors to detect and fix imbalances at the point of insertion, propagating upward.

A4. S(5) = S(4) + S(3) + 1. S(0)=1, S(1)=2, S(2)=4, S(3)=7, S(4)=12, S(5)=20. Join Discord Previous16. Binary Search TreesNext18. Heaps & Priority Queues