> I think you mean binary tree - which can get very unbalanced. The standard specifies logarithmic time lookup for associative containers such as std::map. If the tree is not balanced, it could degenerate to linear time in certain cases(if the data is already sorted, f.ex). So I say its a fair bet to assume that std::map uses either an AVL or a red-black tree.
> why not write one? I did write a red-black tree implementation of IDictionary once - its not complete though. You can read messages from the DOTNET archive, unsubscribe from DOTNET, or subscribe to other DevelopMentor lists at http://discuss.develop.com.
