In an AVL tree, what happens if a node insertion causes

Solution

An AVL tree is a self-balancing binary search tree where the balance factor of each node (height difference between the left and right subtrees) is kept between -1 and +1. When the balance factor becomes +2 or -2 after an insertion, the tree violates this property and must be rebalanced using rotations. The type of rotation depends on the imbalance: • Single Rotation: Used when the imbalance is in one direction, either left-heavy (LL rotation) or right-heavy (RR rotation). • Double Rotation: Used when the imbalance involves opposite directions, such as left-right (LR rotation) or right-left (RL rotation). Option 2 is correct because the AVL tree algorithm always rebalances the tree after insertion using rotations to ensure logarithmic height. Why Other Options Are Incorrect: 1. Tree becomes unbalanced and cannot be used: Incorrect, as AVL trees are explicitly designed to handle imbalances. 2. Insertion is rejected: Incorrect, as rebalancing is performed instead of rejecting insertions. 3. Height increases by 2: Incorrect, as height adjustments depend on rebalancing and typically increase by at most 1. 4. Balance factor is ignored: Incorrect, as the balance factor is central to maintaining AVL tree properties.