How to save minimum and maximum time O (1) in a balanced binary search tree without resetting the pointers?

Question

Excise tax 3-7 in the book "Algorithm Design Guide" says:

Suppose you have access to a balanced dictionary data structure that supports each of the search, insert, delete, minimum, maximum, successor and predecessor operations in O (log n). Explain how to change the insert and delete operations so that they still do O (log n), but now the minimum and maximum time is O (1). (Hint: think in terms of using abstract dictionary operations, rather than resetting pointers, etc. ... )

Without hints, I think this question is pretty simple.

Here is my solution:

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

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

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

But the hint says that I can't avoid pointers and the like. Is my decision disgusting with pointers?

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

thanks

Answer 1

Your answer is the same that I would give - you do not bother with pointers, you just save the min / max values.

So just be more confident :)

Answer 2

You can reach the registration time (N) for update / deletion and constant time to get the minimum / maximum value with Min-Max Heaps

Answer 3

I don't think you can get O (1) for both maximum and mininum.

In any case, the book wants you to discover the binary heaps yourself. Do not look at the link if you want to do it yourself. Consider this hint: “The root of the tree always contains the minimum value” (or the maximum value if you want the “maximum” to be O (1)).

Answer 4

I would use two binary heaps: min and maximum heap. In each of them you store half of the elements, and thus you can access both max and min O (1) times. The minimum heap will contain half with the smallest elements and the maximum heap half with the largest elements. Insert / delete operations will still be O (log n). When inserting a new item, just check which heap it should go to.

Answer 5

Keep two values, maximum and minimum. They should be checked and potentially updated with every deletion. If the minimum is removed, call the successor, update the minimum and delete the old item. In the inset, compare the new element with min / max if it replaces one min / max update, respectively