How to keep minimum and maximum take O(1) time in a balanced binary search tree, without mucking about with pointers?

Question

The excise 3-7 in "Algorithm Design Manual" book says:

Suppose you have access to a balanced dictionary data structure, which supports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in O(log n) time. Explain how to modify the insert and delete operations so they still take O(log n) but now minimum and maximum take O(1) time. (Hint: think in terms of using the abstract dictionary operations, instead of mucking about with pointers and the like.)

Without the hints, I think this question is fairly easy.

Here is my solution:

for the tree, I just maintain a pointer min always pointing to minimum, and another pointer max always pointing to maximum.

When inserting x, I just compare min.key with x.key, if min.key > x.key, then min = x; and also do this for max, if necessary.

When deleting x, if min==x, then min = successor(x); if max==x, then max = predecessor(x);

But the hint says I can't mucking about the pointers and the like. Does my solution muck about with pointers?

If we can't use extra points, how can I get O(1) for minimum and maximum?

Thanks

Answer 1

Your answer is the same one I would give - you're not messing with pointers, you're just storing the min/max values.

So, just be more confident :)