What's a good and stable C++ tree implementation?

Question

I'm wondering if anyone can recommend a good C++ tree implementation, hopefully one that is stl compatible if at all possible.

For the record, I've written tree algorithms many times before, and I know it can be fun, but I want to be pragmatic and lazy if at all possible. So an actual link to a working solution is the goal here.

Note: I'm looking for a generic tree, not a balanced tree or a map/set, the structure itself and the connectivity of the tree is important in this case, not only the data within. So each branch needs to be able to hold arbitrary amounts of data, and each branch should be separately iterateable.

Answer 1

I am going to suggest using std::map instead of a tree.

The complexity characteristics of a tree are:

Insert:       O(ln(n))
Removal:  O(ln(n))
Find:         O(ln(n))

These are the same characteristics the std::map guarantees.
Thus as a result most implementations of std::map use a tree (Red-Black Tree) underneath the covers (though technically this is not required).

Answer 2

Take a look at this.

The tree.hh library for C++ provides an STL-like container class for n-ary trees, templated over the data stored at the nodes. Various types of iterators are provided (post-order, pre-order, and others). Where possible the access methods are compatible with the STL or alternative algorithms are available.

HTH

Answer 3

If you don't have (key, value) pairs, but simply keys, use std::set. That uses the same Red-Black tree as std::map.

Answer 4

Well good on you for wanting to re-use rather than re-write. I opened a project yesterday, saw a directory called "Collections" (first warning) and opened that to find BinaryTree.cs, SortedBinaryTree.cs, RedBlackTree.cs... all of course re-implementations.

Even better, however, was BufferedEnumerator.cs. It bears this description:

    /// This enumerator is designed to encapsulate a forward only 
    /// iterator to provide limited rewind functionality.
    /// It is only possible to rewind the the last restore point.

The mind truly boggles.

Answer 5

Ok folks, I found another tree library, but haven't tried it out yet

Answer 6

I don't know about your requirements, but wouldn't you be better off with a graph (implementations for example in Boost Graph (http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/index.html) if you're interested mostly in the structure and not so much in tree-specific benefits like speed through balancing? You can 'emulate' a tree through a graph, and maybe it'll be (conceptually) closer to what you're looking for.