Any idea of how to implement a Data Structure that supports two operation in less than O(n) and the ds is sorted? asked 07 Mar '18, 22:51
showing 5 of 6
show all

You are not logged in. Please login at www.codechef.com to post your questions!
×CodeChef Discussion 
Any idea of how to implement a Data Structure that supports two operation in less than O(n) and the ds is sorted? asked 07 Mar '18, 22:51
showing 5 of 6
show all

Once you sign in you will be able to subscribe for any updates here
By RSS:Markdown Basics
Question tags:
question asked: 07 Mar '18, 22:51
question was seen: 185 times
last updated: 07 Mar '18, 23:29
BST(Binary Search Tree)
Insertion and Deletion Complexity: O(log2(n))
@shawnfrost in bst its O(h) and worst case the insertion and deletion is O(n) anything better than that?
AVL Tree.
They are same as BST but are height balanced.
So, h remain log2(n) always.
how to delete in avl trees? and also like is there a way if i can find nth max in avl tree?
Complete implementation is available on geeksforgeeks.
Consider maintaining count of nodes on the left and right of each node.
Now,perform binary search skipping all nodes before nth node.
O(log2(n)) per query.
thanks !!!