Q19Data Structures

While standard Binary Search Trees (BSTs) theoretically offer highly efficient $O(\log n)$ time complexities for critical operations like searching, insertion, and deletion, they harbor a severe architectural vulnerability. If data is inserted in a strictly sorted or highly ordered manner, a standard BST will rapidly degrade into a skewed, linear linked list configuration. In this degraded state, the operational time complexity collapses to a disastrous $O(n)$, completely negating the structural advantage of the tree format. To definitively solve this systemic issue, computer scientists G.M. Adelson-Velsky and E.M. Landis invented the AVL Tree in 1962.

1. Theoretical Definition of an AVL Tree

An AVL tree is a rigorously self-balancing Binary Search Tree. It imposes a strict mathematical structural constraint on every single node within its hierarchy: the height difference between any node's left contiguous subtree and its right contiguous subtree can never exceed a magnitude of 1. This singular, powerful rule universally guarantees that the overall tree remains asymptotically balanced at all times, mathematically forcing the tree's maximum depth to remain strictly proportional to $O(\log n)$. Consequently, all search and modification operations are eternally bound to $O(\log n)$ worst-case performance.

2. The Mathematics of the Balance Factor

To continuously monitor and enforce this structural rule, AVL algorithms rely on calculating a specific metric called the Balance Factor (BF) for every node. The calculation is straightforward: $BalanceFactor(Node)=Height(LeftSubtree)-Height(RightSubtree)$.

In a structurally healthy AVL tree, the Balance Factor for any node is strictly confined to the permissible set of integers $\{-1,0,1\}$. - $BF=0$: The node is perfectly balanced; subtrees are equal height. - $BF=+1$: The node is slightly left-heavy, but within legal limits. - $BF=-1$: The node is slightly right-heavy, but within legal limits.

The absolute moment an insertion or deletion operation causes any node's Balance Factor to mutate to $+2$ or $-2$, the AVL structural integrity is officially compromised. The tree immediately triggers a corrective sequence of algorithmic "rotations" to forcefully restore the legal balance factor constraints.

3. Step-by-Step AVL Tree Construction Trace

We will now meticulously construct an AVL tree by sequentially inserting the dataset: 21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7. Every insertion must be validated for balance.

• Insert 21: Node 21 becomes the root. Tree is balanced.
• Insert 26: 26 > 21, inserted as right child of 21. Tree is balanced.
• Insert 30: 30 > 26, inserted as right child of 26. Imbalance Detected: Node 21 now has $BF=-2$ (Right-Right heavy). Correction: Execute a Left Rotation (LL Rotation) pivoting around 21. Node 26 elevates to become the new root. 21 becomes its left child, 30 remains its right child.
• Insert 9: 9 < 26, 9 < 21, inserted as left child of 21. Tree is balanced.
• Insert 4: 4 < 21, 4 < 9, inserted as left child of 9. Imbalance Detected: Node 21 now has $BF=+2$ (Left-Left heavy). Correction: Execute a Right Rotation (RR Rotation) pivoting around 21. Node 9 elevates. 4 remains left child of 9, 21 becomes right child of 9.
• Insert 14: 14 < 26, 14 > 9, 14 < 21, inserted as left child of 21. Tree is balanced.
• Insert 28: 28 > 26, 28 < 30, inserted as left child of 30. Tree is balanced.
• Insert 18: 18 < 26, 18 > 9, 18 < 21, 18 > 14, inserted as right child of 14. Imbalance Detected: Node 21 has $BF=+2$ (Left subtree of 21 is heavy, specifically the Right child 14 is heavy $\to$ Left-Right case). Correction: Execute a complex Left-Right Rotation (LR Rotation). First, Left Rotate around 9 (child). Then, Right Rotate around 21 (parent). Node 14 elevates to balance.
• Insert 15: 15 < 18, inserted as left child of 18. Tree is balanced.
• Insert 10: 10 < 14, inserted as left child of 14 (right of 9). Tree is balanced.
• Insert 2: 2 < 4, inserted as left child of 4. Tree is balanced.
• Insert 3: 3 > 2, inserted as right child of 2. Imbalance Detected: Node 4 has $BF=+2$ (Left-Right case). Correction: LR Rotation. Left rotate on 2, Right rotate on 4. Node 3 elevates.
• Insert 7: 7 > 4, inserted as right child of 4. Tree remains perfectly balanced within AVL tolerances.

Through this rigorous, continuous application of calculated structural rotations, the tree perpetually defends its $O(\log n)$ operational efficiency, completely immune to the sequential ordering of the input data.