Arch1tect
Arch1tect

Reputation: 4281

Getting max and min from BST (C++ vs Java)

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

Answers (2)

pankaj
pankaj

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

user207421
user207421

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

Related Questions