finding a data structure!!!

[ipsita]

Hi All,

I want a data structure that can perform all the following operations in O(log n) time each:

1. Search an element
2. Insert an element
3. Delete an element
4. Find the the Max

Please suggest!!!

Cheers!!!

[Peter_APIIT]

I think there are no algorithm/DS that perform that well.

AFAIK, all performed within O(n log n);

[Russco]

I think AVL tree (http://en.wikipedia.org/wiki/AVL_tree) meets those requirements.

[ipsita]

Hello,

Thanks all for your inputs.
I have a suggestion.
What about an Augmented-RB tree (max field is maintained at each node)

Search takes O(log n) similar to BST.
Delete and Insert will also take O(log n) since RB trees are always balanced.
Max will take O(1) by checking the max filed of the root.

What do you guys think!!!
Do you guys have any idea whether this can be done with any type of binary heaps???

Cheers!!!