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.

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

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

Solution 5

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

View more solutions

Comments

[Martin York]

I though that is what I wrote? But I should note the Red-Black part.

[Robert Gould]

Doesn't look bad, but its GNU. That is a very heavy price to pay for a tree

[Robert Gould]

The nice thing about a (generic)tree is that you can add n children to a branch, and apply operations onto different branches, but std::map abstracts all that away, or uses red-black (child n=2), and abstracts away the structure into a flat interface.

[Robert Gould]

Being able to operate on a single branch is the whole point or a tree. Examples could be filesystem folders, data layout, scene graphs, language analysis, xml-like structured data, and probably many more cases I can't think of right now.

[Robert Gould]

But for flat data, yes you are right, a map will do nicely, however personally I prefer a hash for flat data

[Robert Gould]

Yes you are right, and I just came back from looking at Boost::Graph. It seems suitable to my needs (structure), however the documentation is huge! Would've been nice if there was a simpler version of a tree though.

[Roel]

True, the documentation is daunting. If you are really going to base a serious part of your project on this, I suggest you get the boost graph book. It's clearly written (for as far as a book on this topic can be clear) and fairly comprehensive. Most importantly, it'll get you up to speed quickly.

[ypnos]

First of all, this project is not part of GNU. Second, if you talk about the GPL, this is not necessarily any price to pay. It depends on if one wants to publish the code and under what terms.

[John La Rooy]

He mentions on the homepage to contact him if the GPL doesn't suit. What is a fair price to pay for a tree? How much work/time does it save your project?

[nurettin]

OK std::map<std::string, std::map<std::string, int>> wtf; So how would you implement a "previous sibling" in a node stored in std::map ? how do you store "parent" ? std::map is not an answer to this just because map has underlying tree.

[Martin York]

@nurettin: You will notice that the question was edited after I added this answer. This answers the original question.

[nurettin]

@LokiAstari it seems he edited because he had the same idea (map or map of maps is inadequate for trees) It also seems that this question is ages old, so nevermind :-)

[robin girard]

@user18044 with tree.hh, is it possible to move in a bi-directional way (from father to sons and from son to fathers ) ?

[danbo]

Hmm, it's small , lack of documentation and slow ... my concern is ... why it is slow :(. Granted that Boost::BGL can be a pain in a ass for allocation due to vector<> strategy, it does however grant pure speed once optimized ( althought preallocation is a pain to do .. ).

[fuji]

I just posted a new question here that asks how to implement such a tree using the Boost Graph Library. Maybe you can point me in the right direction? Thank you very much!

[davidbak]

10 years later I'm not sure why this is the highest voted answer. The OP wants a tree and the answer is use Boost Graph because "isn't that what you really want"? Even though there's no indication that the OP wants a graph, not a tree. And BTW, w.r.t. Boost Graph: it's not a tree, but you can use it to build a tree, especially if you buy a book to get you up to speed quickly. (And I'm speaking as one who already has the book.)

[Roel]

@davidbak And yet, 10 years ago, the OP answered indicating that indeed this is what he was looking for, and my answer itself says that a graph is not a tree but that you can use one to build one? No idea what the point of your comment is...