Thread: best STL method to implement a binary tree

  1. #1
    matthewdoucette.com MatthewDoucette's Avatar
    Join Date
    Feb 2005
    Posts
    6

    best STL method to implement a binary tree

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

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    So, you want to implement a plain old binary tree? Why are you bringing the STL into this? Just implement a binary tree.
    Last edited by pianorain; 06-14-2006 at 08:09 PM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    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 saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,079
    I'm going to be different and say use a deque.


    ...but honestly, implement your own.
    Sent from my iPad®

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Not sure if it's STL, but <xtree> contains a tree template. It may just be for use in other STL components though.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  8. #8
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Quote Originally Posted by Magos
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple binary search tree?
    By sybariticak47 in forum C++ Programming
    Replies: 8
    Last Post: 08-09-2007, 03:53 PM
  2. binary tree complete check
    By ichijoji in forum C++ Programming
    Replies: 5
    Last Post: 11-12-2004, 05:48 PM
  3. binary tree start
    By curlious in forum C++ Programming
    Replies: 6
    Last Post: 01-01-2004, 03:47 PM
  4. Traversing a binary tree with pointers
    By supaben34 in forum C++ Programming
    Replies: 8
    Last Post: 12-07-2003, 01:04 PM
  5. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 02:51 PM