1,002 views
6 votes
6 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

Best answer
19 votes
19 votes

Let us analyse one by one..In each case we have to see the most expensive operation out of "findclosest , insert and delete" as T is defined as :

T = max( insert , delete , findclosest )

A) Sorted List : 

For sorted list we need to find the appropriate place of insertion , so we may end up inserting at the end..                             Hence T in this case = O(n)..

B) An unordered list :

Here although we can do insertion in O(1) time as there is no restriction on ordering of elements..But to delete we need to find the element hence T = deletion time  = O(n)

C) An implicit heap :

Here no issue with insertion and deletion as they can be done in O(logn) time..But issue is with finding the closest pair..As we know there is no sibling relation in heap tree..So we may need to check for the entire level of the heap tree..And hence we may end up in O(n) complexity..

D) An AVL tree :

Here insertion and deletion is done in O(logn) time..To do findclosest(y) for a specific element y we can do it by finding the inorder successor and predecessor in the AVL tree along the height and hence the complexity = O(logn)..

Hence the minimum complexity is given by AVL tree..Hence D) should be the correct answer..

selected by

Related questions

0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
srestha asked May 2, 2019
470 views
A $d-$ary heap is a binary heap, but instead of $2$ children, nodes have $d$ children. A $d-ary$ heap can be represented by $1-D$ array as follows. The root is kept in $A...