BST

Question

A data structure is required for storing the set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set
1. Deletion of the smallest element
2. Insertion of an element if it is not already present in the set
Which of the following data structure can be used?
a.) A heap but not a balance bst
b) a balance bst but not a heap
c.) Both balance bst and a heap
d.) Neither balance bst nor a heap

Answer 1

A self-balancing balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in

O(log n) worst-case time. Since it’s a self balancing BST. We can easily find out minimum element in O(logn) time which is always the leftmost element.

Even in min heap  insertion and deletion of an element  will take O(logn) time.

But question here is Insertion of an element if it is not already present in the set.

If element is not present in the set heap will take O(n) time to find the element and O(logn) time for insertion.

Comments

How min heap deletion of element wiill take 0 (1) ?

---

oops sorry that would in case of finding min element . deletion would again requiry heapify which would take O (logn ) ..

---

Actually deletion is causing any  problem here .

Here the concern the insertion of an element that is not present in the set.Heap will take O($n$) time to search the element and then insertion of will take O(logn).Total O($n$) time.

On the other hand balanced BST will take O($logn$) time to search plus O($logn$) time to insert.Total O($logn$) time.