1 votes 1 votes Can anyone please explain ?? What does R+1,L+1 or R+1,L-1 means ?? atul_21 asked Jan 1, 2018 atul_21 1.4k views answer comment Share Follow See all 21 Comments See all 21 21 Comments reply Manu Thakur commented Jan 1, 2018 reply Follow Share sometimes i feel, those people who make test series, why they are so creative :/ irrelevant questions, only time waste!! they should explain the meaning of such self created terms at least. 3 votes 3 votes Ashwin Kulkarni commented Jan 1, 2018 reply Follow Share Haaha @Manu Thakur sir. Even we can't guess what it actually means :p 1 votes 1 votes atul_21 commented Jan 1, 2018 reply Follow Share Really 0 votes 0 votes atul_21 commented Jan 1, 2018 reply Follow Share But please tell me how to balance the tree ,when 80 is deleted? 0 votes 0 votes Manu Thakur commented Jan 1, 2018 reply Follow Share @atul study AVL tree! 0 votes 0 votes Manu Thakur commented Jan 1, 2018 reply Follow Share In case of deletion, in worst, i think O(logn) rotations are required, while in case of insertion always O(1) rotation is required. can someone confirm? 0 votes 0 votes atul_21 commented Jan 1, 2018 reply Follow Share I want to ask one thing,will I first balance the LL imbalance at LST or at RST ?? 0 votes 0 votes atul_21 commented Jan 1, 2018 reply Follow Share Yes u r right. . @Manu Thakur 0 votes 0 votes Ashwin Kulkarni commented Jan 1, 2018 reply Follow Share @atul When you delete 80 there is LL imbalance at 70 ! So first you have to resolve that. 0 votes 0 votes Ashwin Kulkarni commented Jan 1, 2018 reply Follow Share Then there imbalnce will be at root node. Then you have to resolve that. 0 votes 0 votes gauravkc commented Jan 1, 2018 reply Follow Share If you wish to explore AVL properties, try this online simulation https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 1 votes 1 votes Ashwin Kulkarni commented Jan 1, 2018 reply Follow Share @Manu sir, In AVL tree insertion also takes O(logn) time. Because when we insert an element we might need to balance the tree again which takes O(logn). 0 votes 0 votes Manu Thakur commented Jan 1, 2018 reply Follow Share @Ashwin you're correct, but i was talking about rotate operations, but not about the complexity to insert an element in the avl tree. "Because when we insert an element we might need to balance the tree again which takes O(logn)." this is not correct. we need O(logn) time to find the correct place for that element as AVL tree is balanced binary search tree, this compexity is not because we need O(logn) to preserve the AVL properties. 1 votes 1 votes joshi_nitish commented Jan 1, 2018 reply Follow Share @Manu, i think # of rotations required on deletion of node is O(1), maximum i think we need rotation upto 2 levels up from bottom, so O(1). what you think ? 1 votes 1 votes atul_21 commented Jan 1, 2018 reply Follow Share Thank you so much @Ashwin 0 votes 0 votes Manu Thakur commented Jan 1, 2018 reply Follow Share @nitish insertion requires O(1) rotation. deletion requires O(logn) rotate operations. 0 votes 0 votes Anu007 commented Jan 1, 2018 reply Follow Share Manu , after insertion we need to check avl property is preserved or not, that also a factor for time complexity O(logn) i.e. searching place (O(logn) )+ insert O(1) + check avl property still stisfy (O(logn)).= O(logn) 0 votes 0 votes joshi_nitish commented Jan 1, 2018 reply Follow Share @Anu sir, @Manu i am only concerned about no. of rotations, i know deletion require O(logn) for AVL tree, because first we need to find that particular key which will take O(logn) but if a pointer to a given node to be deleted is given, then time complexity of deletion of node completely depends on no. of rotations, so what is no. of rotations required in worst case? i think it should be O(1), and hence to delete a node whose pointer is given, it will take O(1) time. 0 votes 0 votes Anu007 commented Jan 1, 2018 reply Follow Share nitish delete root node in avl. Now tell how much time require assume the pointer to root is given. 0 votes 0 votes Ashwin Kulkarni commented Jan 1, 2018 reply Follow Share I think Rotations also might take O(logn), as per @Anu Sir said, if root node is deleted then worst case we still need O(logn) rotations. 0 votes 0 votes joshi_nitish commented Jan 1, 2018 reply Follow Share @Anu007 sir, thankyou! now its clear that no. of rotations required in worst case is O(logn) 1 votes 1 votes Please log in or register to add a comment.