GATE CS 2003 Q63 — Binary Search Trees

To determine which data structure is suitable, let's analyze the time complexity of the required operations for both a balanced binary search tree (BST) and a heap.

1. Balanced Binary Search Tree (e.g., AVL Tree, Red-Black Tree)

• Operation I (Deletion of the smallest element): The smallest element in a BST is always the leftmost node. Finding this node takes $O(\log n)$ time by traversing down the left pointers. Deleting it and rebalancing the tree also takes $O(\log n)$ time.
• Operation II (Insertion if not already present): We first search for the element to ensure it is not already present, which takes $O(\log n)$ time. If it is absent, we insert it and rebalance the tree in $O(\log n)$ time.

Thus, a balanced BST successfully supports both operations in $O(\log n)$ time.

2. Heap (Min-Heap or Max-Heap)

• Operation I (Deletion of the smallest element): In a min-heap, the smallest element is at the root. Removing it and restoring the heap property takes $O(\log n)$ time.
• Operation II (Insertion if not already present): To insert an element only if it is not already present, we must first search the heap to check for its existence. Since a heap does not maintain a sorted search order across all elements, searching for an arbitrary element in a heap requires a full traversal, taking $\Theta(n)$ time in the worst case.

Thus, a heap cannot perform the conditional insertion in $O(\log n)$ time.

Conclusion: A balanced binary search tree can be used, but a heap cannot.