48

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.

6 Answers 6

25

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.

5
  • 2
    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. Oct 8, 2008 at 8:25
  • 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.
    – Roel
    Oct 8, 2008 at 9:38
  • 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!
    – fuji
    Nov 26, 2016 at 11:55
  • 3
    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.)
    – davidbak
    Jun 17, 2019 at 20:10
  • @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...
    – Roel
    Jul 10, 2019 at 13:55
19

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

5
  • 18
    Doesn't look bad, but its GNU. That is a very heavy price to pay for a tree Oct 8, 2008 at 7:27
  • 4
    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.
    – ypnos
    Oct 24, 2008 at 3:19
  • 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? Oct 12, 2009 at 2:02
  • @user18044 with tree.hh, is it possible to move in a bi-directional way (from father to sons and from son to fathers ) ? Nov 26, 2013 at 10:45
  • 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 .. ).
    – danbo
    Sep 24, 2015 at 12:35
9

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

8
  • I think you mean that most std::map implementations use a tree underneath the covers. Specifically, many (most?) use a Red-Black tree. Oct 8, 2008 at 7:23
  • I though that is what I wrote? But I should note the Red-Black part. Oct 8, 2008 at 7:25
  • 2
    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. Oct 8, 2008 at 7:30
  • 5
    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. Oct 8, 2008 at 7:49
  • 1
    But for flat data, yes you are right, a map will do nicely, however personally I prefer a hash for flat data Oct 8, 2008 at 7:50
2

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

2

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

-1

Let suppose the question is about balanced (in some form, mostly red black tree) binary trees, even if it is not the case.

Balanced binaries trees, like vector, allow to manage some ordering of elements without any need of key (like by inserting elements anywhere in vector), but :

  • With optimal O(log(n)) or better complexity for all the modification of one element (add/remove at begin, end and before & after any iterator)
  • With persistance of iterators thru any modifications except direct destruction of the element pointed by the iterator.

Optionally one may support access by index like in vector (with a cost of one size_t by element), with O(log(n)) complexity. If used, iterators will be random.

Optionally order can be enforced by some comparison func, but persistence of iterators allow to use non repeatable comparison scheme (ex: arbitrary car lanes change during traffic jam).

In practice, balanced binary tree have interface of vector, list, double linked list, map, multimap, deque, queue, priority_queue... with attaining theoretic optimal O(log(n)) complexity for all single element operations.

<sarcastic> this is probably why c++ stl does not propose it </sarcastic>

Individuals may not implement general balanced tree by themselves, due to the difficulties to get correct management of balancing, especially during element extraction.

There is no widely available implementation of balanced binary tree because the state of the art red black tree (at this time the best type of balanced tree due to fixed number of costly tree reorganizations during remove) know implementation, slavishly copied by every implementers’ from the initial code of the structure inventor, does not allow iterator persistency. It is probably the reason of the absence of fully functionnal tree template.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.