Practice mode Data Structures

The keys 10, 20, 30 are inserted in that order into an empty AVL tree. Which rotation restores balance and which key becomes the root?

Correct answer A. A single left rotation; 20 becomes the root

Explanation

After inserting 30, node 10 has an empty left subtree and a right subtree of height 2, a balance factor of −2. The imbalance is right-right, since 30 went into the right child's right subtree, so one left rotation at 10 fixes it, making 20 the root with children 10 and 30. Double rotations are only needed for left-right or right-left cases.

Report a problem

Answer checked How we write and check questions

Tip: press A, B, C or D to answer, and N for the next question.

Advertisement

Have a question about this answer?

Your email address will not be published. Required fields are marked *

Links and website addresses are not allowed in comments.