STL and Binary Search Trees

Does the STL have an implementation of a Binary Search Tree or any sort of tree for that matter?

The set/multiset/map/multimap containers are typically (not guaranteed) implemented as a form of tree, i.e. red-black tree. The MSVC compiler versions of the headers for these containers include a header called xtree and if you open that up, you get something like:

Code:

---

template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
        class _Tree {
protected:
        enum _Redbl {_Red, _Black};
etc...

---

So I would guess that means that a red/black tree is definitely implemented for those containers mentioned above.

The C++ standard sets speed requirements on the various operations of sets and maps. In practice, only binary search trees meet these requirements.