Give data structures for the following InsertS x insert x to

Give data structures for the following: Insert(S, x): insert x to S Search(x): search if x is in S Delete(S, x): Delete x from S. Max - Gap(S): find the maximum difference, max_x, y S {|x - y|}, in O(1) time. Min - Gap(S): find in O(1) time, min_x, y S, x notequalto y {|x - y|}.

Solution

a)S here can be linked list,binary tree, any other trees,stack,queue,heap,Graph.Any data structures we can use for insert

b)Search:We can search data in  linked list,binary tree,stack,queue,heap,Graph, any other trees,etc.Hence S belong to that

c)Delete:We can Delete data in  linked list,binary tree,heap,Graph, any other trees,etc.Hence S belong to that

d)We can get maximum difference between data in O(1) using Max Heap as it stores the maximum value at root

e)We can get minimum difference between data in O(1) using Min Heap as it stores the minimum value at root