GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
50 views

What are we suppose to take?

LR - 2 rotations.
RL-  2 rotations.

OR

LR - 1 rotation.
RL-  1 rotation.

Kindly Solve and Verify the Total Numbers of Rotations Performed.

asked in DS by Loyal (2.6k points)   | 50 views
is it 1LR and 1RL ?
Are you talking about Final Answer?
in total after all insertions i am getting 1RL, 1RR, 1LR.
Well , I am getting

1- RL
1-RL
1-LL
1-LL
In the same sequence in total at the End.
If asked about rotations simply , they should be taken as two as they are double rotation instances..
on 80 insertion no rotation, then atmax 3 [as only 3 insertions after this] should be there how you getting 4 ?
How can you say,@Gate Mission 1?Sir,  Have you tried it?

When you apply 2nd RL , the tree needs to get Rebalanced. And that's why it takes one more.

The answer Given is 5 and that Confuses me.

@jason, 

Use it for visualisation : https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

I am not sir :) ...just an aspirant.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.


Top Users Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,041 answers
63,230 comments
24,135 users