Printable View
What's the best STL class or method to implement a binary tree?
I know some STL classes are stored as binary trees internally, but this is not what I want. I wish to create and have full control of the binary tree's structure.
A red-black binary tree will do no good, as the structure changes on its own. The tree must remain exactly as I wish to set it. (Red-black binary trees stored extra info which allow the tree to be modified so that it remains "even" in height.)
If you are implementing your own binary tree, I'm not sure you would use an STL container, since each node would only contain a left and a right node, and there wouldn't be anything to contain.
If you wanted to store all the nodes in a container, then you should use the STL list, since you would be doing a lot of inserting into the middle of the container.
So, you want to implement a plain old binary tree? Why are you bringing the STL into this? Just implement a binary tree.
instead of using the standard library to implement a binary tree, implement your own tree and give it an stl-like interface. that way, you can use it with standard library algorithms.
I'm going to be different and say use a deque.
...but honestly, implement your own.
Red-black trees are always "balanced". Your post gives me the impression that you do not want your trees "balanced". In any case, do what we've been telling you; write your own. It's a good exercise.
Not sure if it's STL, but <xtree> contains a tree template. It may just be for use in other STL components though.
I'm pretty sure that's not supported by STL. Looks like implementation-dependent stuff.Quote:
Originally Posted by Magos
xtree ... I believe that's the common tree implementation that MSVC's std lib uses for map, set, multimap and multiset. It's an implementation detail. (As are all of MSVC's headers that start with x and have no extension.)