MODULE 4.212 min readAUTO-DEPTH · 42% MASTERY

Self-Balancing Trees: The AVL Approach

Every node stores a balance factor: height(left) − height(right). Valid values are −1, 0 and +1. Insertion walks back up the path to the root, updating heights and checking factors.

Diagram of an AVL tree rotation restoring balance — Fig 4.1: Left-Right rotation applied to an unbalanced node.

A factor of +2 with the new key in the outer subtree needs a single right rotation; if the key landed in the inner subtree you need a left-right double rotation. The mirrored cases apply for −2.

Each rotation is O(1) pointer surgery, and at most one rebalance is needed per insertion, so insertion stays O(log n).

Check your logic

A node has left-subtree height 4 and right-subtree height 2, and the new key was inserted into the inner subtree of the heavy side. Which fix is required?