Design a data structure D that supports the following operat

Design a data structure D that supports the following operations in O(log n) time. insert(x)-insert x into D find(k)-returns the kth smallest element from D. search(x)-returns true if and only if x D You may assume that all elements of D are integers.

Solution

Ans. AVL tree does all these operations in O(log n).

AVL tree is a tree for which height of left subtree and right subtree differ by at most 1 for all the nodes. THerefore the maximum height of any such tree would be log n.
Insert : Any value x will be inserted at the leaves which are at log n height.
Find : Since nodes are stored in sorted order, therefore finding kth smallest element would also be O(log n).
Search : Since AVL tree is a Binary Serach Tree, therefore search also takes O(log n).