The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Encapulated Binary Search Tree in C++

I am trying to create an encapsulated binary search tree in C++.  For the most part, I know how to do it (I think), but I am having a few problems.  How can I have an unlimited number of nodes and be able to add new nodes at runtime?  I was thinking of using a struct for the info about each node, and a class that stores all the nodes and can perform operations on them.  Like a "MyBinaryTree" class.  I need the entire tree in a class object (I think), because I want to be able to pass the entire tree into functions for them to use.  How can I do this?

Not sure if I have been entirely clear, post if you are confused about my question.
Steven Gary Noyce Send private email
Thursday, July 27, 2006
 
 
#include <map>
A. Nonymous
Friday, July 28, 2006
 
 
> #include <map>

+1
Neville Franks Send private email
Friday, July 28, 2006
 
 
Thanks, but then how do I pass maps into functions and methods?  (thought I could figure it out, but had serious problems and couldn't find anything to help me on google either)
Steven Gary Noyce Send private email
Friday, July 28, 2006
 
 
<map>?  don't you mean <tree>

Saturday, July 29, 2006
 
 
A map, while not a tree, is implemented using a tree though and provides O(ln(n)) search/insert time

To pass a map to a function?  It is just like passing an int or a double. Remember, built-in types have no special treatment, well except that they can't be redefined/hidden by something of the same name in a nested scope.

//by value
void f(map<string,int> m); //function declaration
map<string,int> m; //variable definition
f(m); //function call

//by reference
void f(map<string,int>& m); //function declaration
map<string,int> m; //variable definition
f(m); //function call
Tom
Saturday, July 29, 2006
 
 
How much is "unlimited number of nodes" - i.e. does it fit into RAM, disk, Internet?

Find a a binary search tree insertion (balanced is better for search speed) algorithm and implement it according to your needs. Shouldn't take long.
Andrei Send private email
Sunday, July 30, 2006
 
 
A map is perfectly passable as a function argument, as somebody mentioned.  Just don't do something silly like pass it by value.  Pass by reference, or pass a pointer.

As for size issues, if you need the tree to be larger than what will fit in ram, any of the ISAM databases will do just fine.  SQLite uses a btree on disk, as do gdbm and Sleepycat's Berkeley DB.
Clay Dowling Send private email
Sunday, July 30, 2006
 
 
Thanks everyone!  That realy helped.  Now my program should work just fine, but out of curiosity, how could I make my own class or struct to do the same thing?  I guess what I am interested in is having an unlimited number of varibles inside a class.  Like the string class, or the vector template, or the map template.  How do they implement the functions that add elements, like concat for string and pushback for vector?

I am kind of new to C++, so if this is way complicated then don't worry about it, but I would realy like to know.
Steven Gary Noyce Send private email
Sunday, July 30, 2006
 
 
>Now my program should work just fine, but out of curiosity, how could I make my own class or struct to do the same thing?  I guess what I am interested in is having an unlimited number of varibles inside a class.

You can use map<>, vector<> whatever in your class. So if you want an array of strings you'd use vector<string> m_astrings; then pass a reference to the class instance around.

If you really mean unlimited then you should be using a database as Clay said.

"The C++ Standard Library" by N.M. Josuttis is a good book on STL. Also check out "Effective STL" by Meyers as well as his other Effective .. books.
Neville Franks Send private email
Sunday, July 30, 2006
 
 
> How do they implement the functions that add elements, like concat for string and pushback for vector?

Storage is dynamically allocated by the new or new[] operators, which are implemented by the library call malloc(), which in Unix-like operating systems is implemented by the brk() system call.
William Dowling Send private email
Monday, July 31, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz