New Upcoming Legal Jobs Free Workshop March 11 at 5 PM. Register here

    Question

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

    the balance factor of a node to become +2 or -2?
    A The tree becomes unbalanced and cannot be used. Correct Answer Incorrect Answer
    B A rotation or double rotation is performed to restore balance. Correct Answer Incorrect Answer
    C The insertion is rejected to maintain balance. Correct Answer Incorrect Answer
    D The height of the tree increases by 2. Correct Answer Incorrect Answer
    E The balance factor is ignored. Correct Answer Incorrect Answer

    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.

    Practice Next