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

Solution 1:

I don't know about your requirements, but wouldn't you be better off with a graph (implementations for example in Boost Graph) 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.

Solution 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

Solution 3:

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).

Solution 4:

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

Solution 5:

Ok folks, I found another tree library; stlplus.ntree. But haven't tried it out yet.