How many rotations are required during the construction of an AVL tree if the elements 35, 50, 40, 25, 30, 60, 78, 20, 28 are added in this sequence?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 3 left rotations, 2 right rotations
Explanation
Inserting 40 needs an RL double rotation (1 right + 1 left); 30 needs an LR double rotation (1 left + 1 right); 78 needs an RR single left rotation. 20 and 28 need none. Total: 3 left and 2 right rotations.
More Data Structures and Algorithms questions
- For the graph shown, the following depth-first search sequences are given: (A) abcghf (B) abfchg (C) abfhgc (D) afghbc. Which of the follow…
- Match each algorithm with its running time. (A) Breadth-first search, (B) Rabin–Karp algorithm, (C) Depth-first search, (D) Heap sort (wors…
- Statement I: Vertex cover has a polynomial-time 2-approximation algorithm. Statement II: TSP-tour is a polynomial-time 3-approximation algo…
- The postfix form of the expression (A + B) * (C * D - E ) * F /G is _______
- A double‐ended queue (dequeue) supports adding and removing items from both the ends of the queue. The operations supported by dequeue are…
- Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.