Data Structure



Any idea of how to implement a Data Structure that supports two operation in less than O(n) and the ds is sorted?


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 !!!