Is STL set a binary search tree?

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Is STL set a binary search tree?

Post by ImLazy » Thu Jan 19, 2006 12:23 pm

Is STL set in fact a binary search tree?
Or is the running time of set::find() and set::insert() O(log n)?
I stay home. Don't call me out.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Jan 19, 2006 12:58 pm

A balanced binary tree is more likely. A binary search tree has a worst case performance no
better than a linked list. Look up red-black trees, AVL etc.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Jan 19, 2006 1:22 pm

Thanks.
Another question, how can I get an element of index i in an STL set quickly (O(log n) time).
I think the following code is very slow:

Code: Select all

set<int> s;
set<int>::iterator p = s.begin();
for(n = 0; n < i; n++){
    p++;
}
Is there any faster way?
I'm sorry I'm not very familiar with STL.
I stay home. Don't call me out.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Jan 19, 2006 1:33 pm

ImLazy wrote:Thanks.
Another question, how can I get an element of index i in an STL set quickly (O(log n) time).
....
Why would you want that? How do you want the index to be calculated ?
I don't know where & why you are using that, but I'd suggest
some other container, if its speed that you are getting tied up with. E.g. std::vector.

BTW: in a very simple case, you can use the (value, index) pair to create your set. The index
can actually reflect the order in which they were inserted to the set.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Jan 19, 2006 2:01 pm

Sometimes I need data structure that can
1. insert and remove in O(log n)
2. search an element in O(log n)
3. search the ith smallest element in O(log n).
e.g. problem 10909.
Binary search tree fits this requirement.
But it seem's that STL set can not fit the 3rd requirement.
I stay home. Don't call me out.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Thu Jan 19, 2006 3:56 pm

I would suggest using the STL map using (index,value) pair.

Code: Select all

map <int,int> int2val;//Say we want the ith integer in this map
Then use the find function in STL map (it runs in O(log n) time) or do this:

Code: Select all

int i = 10;
int val = int2val[i];
Of course for the example given, the map needs to have at least 10 elements inside.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Jan 19, 2006 4:21 pm

chunyi81 wrote:I would suggest using the STL map using (index,value) pair.
Neither set nor map can't be used to find the k-th smallest stored element effectively. For problem 10909 I implemented my own splay tree.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Jan 20, 2006 6:11 am

Neither set nor map can't be used to find the k-th smallest stored element effectively.
Not true - it's possible to use the underlying tree structure. However, such code is not portable.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Fri Jan 20, 2006 12:37 pm

Krzysztof Duleba wrote:
Neither set nor map can't be used to find the k-th smallest stored element effectively.
Not true - it's possible to use the underlying tree structure. However, such code is not portable.
What I meant is that you can't use them directly, they don't have such methods.

Still, I'm interested in your suggestion. I can imagine that I copy and paste the implementation of the red-black tree and modify it to suit my needs. But what you wrote suggests a more friendly possibility. Could you be more specific on this?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Jan 20, 2006 5:59 pm

There are no obstacles to enhance trees on your own. I attach sample code that shows how to add subtree size information to nodes and how to maintain it after insertions. You can handle erase operation in a similar fashion.

Mind that this code is not portable. For some reason it works with all versions of g++ that I've tried, but it relies heavily on STL implementation aspects that are not standarized.

Code: Select all

#include <set>
#include <map>
#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

template<typename T>
struct Myset{
	private:
	map<T, int> mp;

	typedef _Rb_tree_node<pair<const T, int> > _Node;
	
	void fix_size(_Rb_tree_node_base * it, bool step_in = true){
		int & it_size = static_cast<_Node *>(it) -> _M_value_field.second;
		it_size = 1;
		if(it -> _M_left != 0){
			if(step_in)fix_size(it -> _M_left, false);
			it_size += static_cast<_Node *>(it -> _M_left) -> _M_value_field.second;
		}
		if(it -> _M_right != 0){
			if(step_in)fix_size(it -> _M_right, false);
			it_size += static_cast<_Node *>(it -> _M_right) -> _M_value_field.second;
		}
	}

	void fix_all_sizes(_Rb_tree_node_base * it, _Rb_tree_node_base * end){
		if(it -> _M_left != 0)fix_size(it -> _M_left);
		if(it -> _M_right != 0)fix_size(it -> _M_right);
		do{
			fix_size(it);
			it = it -> _M_parent;
		}while(it != end);
	}
	
	public:
	void print()const{
		const _Rb_tree_node_base * it = mp.begin()._M_node;
		while(it -> _M_parent != mp.end()._M_node){
			it = it -> _M_parent;
		}
		print_impl(it, "");
	}
	void print_impl(const _Rb_tree_node_base * it, string indent)const{
		if(it == 0){
			cout << indent << "nil (0)" << endl;
			return;
		}
		cout << indent << static_cast<const _Node *>(it) -> _M_value_field.first;
		cout	<< " (" << static_cast<const _Node *>(it) -> _M_value_field.second << ")" << endl;
		if(it -> _M_left != 0 || it -> _M_right != 0){
			print_impl(it -> _M_left, indent + "  ");
			print_impl(it -> _M_right, indent + "  ");
		}
	}

	void insert(const T & t){
		pair<typename map<T, int>::iterator, bool> fit = mp.insert(pair<T, int>(t, -1));
		if(fit.second == false)return;
		fix_all_sizes(fit.first._M_node, mp.end()._M_node);
	}
};

int main(){
	Myset<int> st;
	for(int i = 0; i < 30; ++i)st.insert(rand() % 100);
	st.print();
}
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Post Reply

Return to “C++”