|
06-14-2006, 01:38 PM
| #1 |
| matthewdoucette.com  Join Date: Feb 2005
Posts: 6
| best STL 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.) |
| MatthewDoucette is offline |  |
|
06-14-2006, 01:55 PM
| #2 |
| Registered User Join Date: Jan 2005
Posts: 7,252
| 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. |
| Daved is offline | |
|
06-14-2006, 02:23 PM
| #3 |
| Anti-Poster Join Date: Feb 2002
Posts: 1,241
| So, you want to implement a plain old binary tree? Why are you bringing the STL into this? Just implement a binary tree.
__________________ Rule #1: Every rule has exceptions Last edited by pianorain; 06-14-2006 at 08:09 PM. |
| pianorain is offline | |
|
06-14-2006, 03:08 PM
| #4 |
| semi-colon generator  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? |
| ChaosEngine is offline | |
|
06-14-2006, 03:38 PM
| #5 |
| Devil's Advocate  Join Date: May 2004 Location: Out of scope
Posts: 3,778
| I'm going to be different and say use a deque. ...but honestly, implement your own.
__________________ Terms of Service By quoting or replying directly to this post, you consent to the fact that all of the information in the post above is completely accurate and highly intelligent and no comments will be made towards its validity, thoughtlessness, and/or grammatical structure. Violators will be prosecuted to the fullest extent of the law. |
| SlyMaelstrom is offline | |
|
06-15-2006, 01:44 AM
| #6 |
| Registered User Join Date: Mar 2006
Posts: 726
| 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;}
|
| jafet is offline | |
|
06-15-2006, 03:39 PM
| #7 |
| Confused  Join Date: Sep 2001 Location: Sweden
Posts: 3,125
| 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. |
| Magos is offline | |
|
06-15-2006, 04:14 PM
| #8 | |
| Anti-Poster Join Date: Feb 2002
Posts: 1,241
| Quote:
__________________ Rule #1: Every rule has exceptions | |
| pianorain is offline | |
|
06-16-2006, 07:08 AM
| #9 |
| Cat without Hat  Join Date: Apr 2003
Posts: 8,492
| 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 |
| CornedBee is offline | |
 |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Simple binary search tree? | sybariticak47 | C++ Programming | 8 | 08-09-2007 03:53 PM |
| binary tree complete check | ichijoji | C++ Programming | 5 | 11-12-2004 05:48 PM |
| binary tree start | curlious | C++ Programming | 6 | 01-01-2004 03:47 PM |
| Traversing a binary tree with pointers | supaben34 | C++ Programming | 8 | 12-07-2003 01:04 PM |
| binary search tree help | noob2c | C++ Programming | 6 | 11-09-2003 02:51 PM |
Linear Mode
