- Forum
- General C++ Programming
- Binary Search tree from text file
Binary Search tree from text file
Hello, I'm fairly new to C++
I was wondering if any one knew how I would implement a binary search tree that could read "user input" then search the file and if the user input matched information in the file, it would return the information.
Example:
Text file:
Name: John Doe; Age: 21, Job: Programmer;
Name: Sam Tye; Age: 11, Job: Student;
Name: Liam Dounce; Age: 17, Job: Accountant;
Name: Jackie Doe; Age: 18, Job: Doctor;
Search: Doctors
I was wondering if any one knew how I would implement a binary search tree that could read "user input" then search the file and if the user input matched information in the file, it would return the information.
Example:
Text file:
Name: John Doe; Age: 21, Job: Programmer;
Name: Sam Tye; Age: 11, Job: Student;
Name: Liam Dounce; Age: 17, Job: Accountant;
Name: Jackie Doe; Age: 18, Job: Doctor;
Search: Doctors
read the file, insert each record into your tree, search the tree. However a BST is not the best answer for this, unless you have additional requirements (don't search, just fetch the data directly instead). Are you studying trees, or looking to solve the problem?
Hey thanks for answering, I'm studying data structures (search algorithms).
The project is due after Easter hols, so I'm trying to do all the research into the best method of developing this
The project is due after Easter hols, so I'm trying to do all the research into the best method of developing this
the 'best method' depends on what searches you allow.
if you want to search all programmers, for example, that is different from what you stated, which is give the program specific info to locate specific person.
if your design is just 'get one person who matches input (of 1 or more 'keys') the 'best' design is probably some sort of hashed container. Imagine an array, and imagine you can turn your data into an index into that array. Then when user gives input, you convert to the number, check the array at that slot, if its there (and possibly, check that it matches) they got it right, show them the data, if not, the person didnt exist in the data. No searching involved.
but as I said, you can load up a tree and search it if you like. If the assignment is a tree, you should do a tree :P
I dislike things like trees and if forced to deal with one will usually cram it into a vector on the back end and make it look like a tree. This allows you to do some stuff behind the scenes a little cleaner than trying to manhandle pointers. Effectively, all you do instead of new / pointer is do a push-back and grab the new index. Treat index like a pointer, otherwise its the same on the tree side. This is a slightly more advanced approach as you would need to know when to use the tree functions and when to cheat and use the vector functions, which is a lot to go into here. I don't recommend it right now, but as you do the tree work, think to yourself "would this function be easier if I were processing a vector??" and you will start to see for yourself what I mean. Things like "process every item in the data" go from a recursive tree processing algorithm to a simple loop. Sorting it and rebuilding the tree (rebalance algorithm, in tree terminology) becomes efficient and a breeze.
if you want to search all programmers, for example, that is different from what you stated, which is give the program specific info to locate specific person.
if your design is just 'get one person who matches input (of 1 or more 'keys') the 'best' design is probably some sort of hashed container. Imagine an array, and imagine you can turn your data into an index into that array. Then when user gives input, you convert to the number, check the array at that slot, if its there (and possibly, check that it matches) they got it right, show them the data, if not, the person didnt exist in the data. No searching involved.
but as I said, you can load up a tree and search it if you like. If the assignment is a tree, you should do a tree :P
I dislike things like trees and if forced to deal with one will usually cram it into a vector on the back end and make it look like a tree. This allows you to do some stuff behind the scenes a little cleaner than trying to manhandle pointers. Effectively, all you do instead of new / pointer is do a push-back and grab the new index. Treat index like a pointer, otherwise its the same on the tree side. This is a slightly more advanced approach as you would need to know when to use the tree functions and when to cheat and use the vector functions, which is a lot to go into here. I don't recommend it right now, but as you do the tree work, think to yourself "would this function be easier if I were processing a vector??" and you will start to see for yourself what I mean. Things like "process every item in the data" go from a recursive tree processing algorithm to a simple loop. Sorting it and rebuilding the tree (rebalance algorithm, in tree terminology) becomes efficient and a breeze.
Last edited on
Alright thanks,
I want to be search by Name and search by Job
And create a display (that show all of the information)
depending on certain conditions for example Age group and Gender
Do you know how I can start implementing this or know of any tutorials I can use to learn how to do this
I want to be search by Name and search by Job
And create a display (that show all of the information)
depending on certain conditions for example Age group and Gender
Do you know how I can start implementing this or know of any tutorials I can use to learn how to do this
Might be best to search the web for a tutorial, the last time I did data structures tutorials was before java existed! I am 100% sure that both code and algorithms are all over the web, these are classic coding exercises and done to death.
the 10 cent version that I can type here is you have a class or struct that has 2 pointers, left and right, to itself:
struct int_tree_node
{
int data; //the actual thing stored in the tree.
int_tree_node *left; //this would be an integer and an index in the vector version.
int_tree_node *right;
}
also recommended is to keep the tree class and the data class distinct (this is good design) so that you have
class datathingy
{
string first_name;
string last_name;
int age;
etc...
};
and put that in where I had 'int' when you make your tree (and later you will learn to make the tree accept *any type of anything*, but not today). If it isnt tightly coupled to your data type class, that will be easier to do later when you get to it.
Then you will have a bunch of methods for your tree class that handle inserting, deleting, rebalancing (optional, but trees can become linked lists if left alone too long with volatile data, making them slower and poorish, so you re-do them back to a binary structure now and then) and your search algorithm etc. You will want to learn about a 'traversal' in your study of trees.
the 10 cent version that I can type here is you have a class or struct that has 2 pointers, left and right, to itself:
struct int_tree_node
{
int data; //the actual thing stored in the tree.
int_tree_node *left; //this would be an integer and an index in the vector version.
int_tree_node *right;
}
also recommended is to keep the tree class and the data class distinct (this is good design) so that you have
class datathingy
{
string first_name;
string last_name;
int age;
etc...
};
and put that in where I had 'int' when you make your tree (and later you will learn to make the tree accept *any type of anything*, but not today). If it isnt tightly coupled to your data type class, that will be easier to do later when you get to it.
Then you will have a bunch of methods for your tree class that handle inserting, deleting, rebalancing (optional, but trees can become linked lists if left alone too long with volatile data, making them slower and poorish, so you re-do them back to a binary structure now and then) and your search algorithm etc. You will want to learn about a 'traversal' in your study of trees.
Last edited on
almost done, but one of the (several) problems with trees is their nature vs your needs.
A BST stores data in less left, greater right format. eg:
so if searching for 7, it goes less, left (5), greater right (7) and finds it with only a few looks; it never even has to look at 15 or anything under it (could be dozens of items there); in a balanced tree every look throws away 1/2 of the remaining items!
but, you can't store the data off multiple fields.
you can't search for all doctors and and search by names in the same tree using this method as ONE attribute (or combined attribute) governs the sorting which governs the less left / greater right. Name could be greated and job title lesser for the same entry, see?
there are other types of trees than BST, but you either need 1 tree for each search criteria (data repetition) or a cross reference if you use a BST. Thankfully by job means you have to look at all the nodes anyway, that is just a traversal, but if you need to look for unique records using 2 different criteria, you will encounter an issue. Keep that in mind.
A BST stores data in less left, greater right format. eg:
|
|
so if searching for 7, it goes less, left (5), greater right (7) and finds it with only a few looks; it never even has to look at 15 or anything under it (could be dozens of items there); in a balanced tree every look throws away 1/2 of the remaining items!
but, you can't store the data off multiple fields.
you can't search for all doctors and and search by names in the same tree using this method as ONE attribute (or combined attribute) governs the sorting which governs the less left / greater right. Name could be greated and job title lesser for the same entry, see?
there are other types of trees than BST, but you either need 1 tree for each search criteria (data repetition) or a cross reference if you use a BST. Thankfully by job means you have to look at all the nodes anyway, that is just a traversal, but if you need to look for unique records using 2 different criteria, you will encounter an issue. Keep that in mind.
Hey Sorry to distrub
I'm thinking of using Hashtables instead
Would you recommend them I found a great tutorial:
I'm thinking of using Hashtables instead
Would you recommend them I found a great tutorial:
|
|
yes, that was what I was saying was faster and easier for just pure store & locate.
see my second post:
"if your design is just 'get one person who matches input (of 1 or more 'keys') the 'best' design is probably some sort of hashed container."
C++ has one built in, but if you are rolling your own, the thing to know here is you will need a way to convert the keys the user searches on (name, etc) into some sort of number.
There are any number of ways to do that.
Hashing will suffer the same problem as above with trees -- you can't hash on both the name and the job type, so you can't search off both of those for unique data records in a single table easily. You either need a more convoluted structure and approach, or multiple tables, or something that solves this. Or a really fat table you could hash the data twice into it for that matter, one hash per search key. This is sometimes called the time space tradeoff... you can waste time (one copy of the data, but searching is less efficient vs multiple copies of the data and searching is more efficient) to save space or waste space to save time.
if you want to let C++ do ALL the work for you, that is an option too.
and again, if you put it in a vector, you can have a thin-tree on top of it and a hash table on top of it as well, at the same time even, if you had some need for that. Vectors can emulate almost all other data structures, and save a lot of aggravations. Doing both at once is not helpful here, don't take this as a suggestion, but as a possibility.
see my second post:
"if your design is just 'get one person who matches input (of 1 or more 'keys') the 'best' design is probably some sort of hashed container."
C++ has one built in, but if you are rolling your own, the thing to know here is you will need a way to convert the keys the user searches on (name, etc) into some sort of number.
There are any number of ways to do that.
Hashing will suffer the same problem as above with trees -- you can't hash on both the name and the job type, so you can't search off both of those for unique data records in a single table easily. You either need a more convoluted structure and approach, or multiple tables, or something that solves this. Or a really fat table you could hash the data twice into it for that matter, one hash per search key. This is sometimes called the time space tradeoff... you can waste time (one copy of the data, but searching is less efficient vs multiple copies of the data and searching is more efficient) to save space or waste space to save time.
if you want to let C++ do ALL the work for you, that is an option too.
and again, if you put it in a vector, you can have a thin-tree on top of it and a hash table on top of it as well, at the same time even, if you had some need for that. Vectors can emulate almost all other data structures, and save a lot of aggravations. Doing both at once is not helpful here, don't take this as a suggestion, but as a possibility.
Last edited on
Sorry I completely missed that, haha.
But you've been great help thanks
Alright, so to do the two separate search I'll have to create multiple tables one for
example
[User info]
Id, Name, age, gener
[Job info]
Id, Job, company
Like I would in SQL ?
But you've been great help thanks
Alright, so to do the two separate search I'll have to create multiple tables one for
example
[User info]
Id, Name, age, gener
[Job info]
Id, Job, company
Like I would in SQL ?
Topic archived. No new replies allowed.