Red and black tree help

[blcase]

ok exploring the STL <set> if you entered the values say 1 to 1000 in order would it auto balance?....i thought no but then a friend of mine told me about this "red and black" tree and if i test the result times to find an element (random and numeric insertion) there is only a difference of like 2e-6s (which makes think the tree does auto balance) so anyone please help me understand what is going on

[sarehu]

It does auto-balance.

[bugmenot]

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
http://en.wikipedia.org/wiki/Red-black_tree

[vijayan121]

the c++ standard only specifies the performance requirements: for insert, erase and find
this is O( log N ). to meet this requirement, any tree implementation must be (reasonably) balanced at all times.