Reputation: 4281
I know that given a balanced binary search tree, getting the min and max element takes O(logN), I want to ask about their implementation in C++ and Java respectively.
C++
Take std::set
for example, getting min/max can be done by calling *set.begin()
/ *set.rbegin()
, and it's constant time.
Java
Take HashSet
for example, getting min/max can be done by calling HashSet.first()
and HashSet.last()
, but it's logarithmic time.
I wonder if this is because std::set
has done some extra trick to always update the beigin()
and rbegin()
pointer, if so, can anyone show me that code? Btw why didn't Java add this trick too, it seems pretty convenient to me...
EDIT:
My question might not be very clear, I want to see how std::set
implements insert/erase , I'm curious to see how the begin()
and rbegin()
iterator are updated during those operations..
EDIT2:
I'm very confused now. Say I have following code:
set<int> s;
s.insert(5);
s.insert(3);
s.insert(7);
... // say I inserted a total of n elements.
s.insert(0);
s.insert(9999);
cout<<*s.begin()<<endl; //0
cout<<*s.rbegin()<<endl; //9999
Isn't both *s.begin()
and *s.rbegin()
O(1) operations? Are you saying they aren't? s.rbegin() actually iterate to the last element?
Upvotes: 0
Views: 178
Reputation: 1346
My answer isn't language specific.
To fetch the MIN
or MAX
in a BST
, you need to always iterate till the leftmost or the rightmost node respectively. This operation in O(height)
, which may roughly be O(log n)
.
Now, to optimize this retrieval, a class that implements Tree
can always store two extra pointers pointing to the leftmost and the rightmost node and then retrieving them becomes O(1)
. Off course, these pointers brings in the overhead of updating them with each insert operation in the tree.
Upvotes: 2
Reputation: 310957
begin()
and rbegin()
only return iterators, in constant time. Iterating them isn't constant-time.
There is no 'begin()/rbegin()
pointer'. The min and max are reached by iterating to the leftmost or rightmost elements, just as in Java, only Java doesn't have the explicit iterator.
Upvotes: 0