Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 5 / b

Yes, provided balancing guarantees logarithmic height. In a suitably maintained balanced binary tree of height $O(\log (n+1))$, insertion searches one root-to-leaf path and deletion of the minimum follows the leftmost path. Reconnecting the tree and performing the required rebalancing also costs at most a constant amount per level for the standard logarithmic-time schemes. Thus both operations take $O(\log (n+1))$ time, conventionally written $O(\log n)$ for nontrivial sizes. Merely calling a tree approximately balanced would not prove that height bound; it is the balancing guarantee that matters. Without it, a binary search tree can have linear height.

Not automatically: the duplicate-value policy must implement a multiset. A strict binary search tree storing one entry per distinct key represents a set; inserting a second equal value then loses a required occurrence. A fixed rule that puts all equal values on one side also needs care, because ordinary balancing rotations need not preserve that one-sided equality rule.

One valid refinement stores a multiplicity at each distinct key. Inserting an equal key increments its count; delMin decrements the minimum key's count and removes that node only at zero. Alternatively, use distinct internal keys such as (value, uniqueSerial) while ordering primarily by value and returning only the value. With an appropriate balanced representation either approach preserves every occurrence and the required operation bounds. A bare claim about balanced search trees, with no treatment of duplicates, does not establish the abstract specification.

A minimum-oriented binary heap is an appropriate alternative. Store a complete binary tree in an array and maintain heap order. Insertion appends a value and moves it upward; removing the root replaces it by the last value and moves that value downward. Each path has $O(\log (n+1))$ levels, and equal values can be stored in separate slots. Both operations therefore take $O(\log (n+1))$ time when capacity is available.

Unlike a binary search tree, the heap does not maintain a complete search order, so finding an arbitrary specified value can require $O(n)$ inspections. A simple array implementation also has a capacity issue: a fixed array can fill, and resizing a growable array occasionally costs $O(n)$, giving an amortized insertion guarantee unless allocation is otherwise managed. This capacity cost is an implementation tradeoff, not an inherent inability of heaps to represent the priority queue abstraction.