440 views
0 votes
0 votes

Consider a data type whose elements are integers and whose operations are INSERT, DELETE, and FINDCLOSEST, with FINDCLOSEST(y) defined to be some element x in the current set such that|x-y| ≤ |xi-y| for all xi in the current set. Let

T = max ( T_{INSERT} ,T_{DELETE}, T_{FINDCLOSEST} )

where T_{op} denotes the worst-case time complexity for the given operation OP. Which of the following data structures would be best to use in order to minimizeT?

(A) A sorted list

(B) An unordered list

(C) An implicit heap

(D) An AVL tree

1 Answer

0 votes
0 votes

I think option C will be the best.

Sorted list will find the position in O(1) but then you have to move other elements to insert the new one. That will take O(n). Same for delete. find closest will take O(1) time.

Unordered list is best if only insertion or deletion was asked. It will take O(1) time. Problem will arise in case of find closest. It will take O(n) time.

Implicit heap is a special type of heap where elements are arranged like arr[1,2,3,4,...n]. Insert and delete will take O(log2 n) time. And find Closest will take O(1) time as you have to check only previous and immediate next element of y (the given key).

In case of AVL tree we can do insertion and deletion in O(log n) time but find closest will also take O(log n) as first you have to find where y is then you can check it's children which one is closer.

          

Related questions

2 votes
2 votes
1 answer
1
smartmeet asked Feb 7, 2017
881 views
A B-tree of order m is a tree which satisfies the following properties:Every node has at most m children.Every node (except root) has at least ⌈m/2⌉ children maximi...