C++ Map Binary Tree

[Willo123]

Hello! I have a hard time understanding the question from Alex Allains book "Jumping into C++",

6. Implement a simple map, in the form of a binary tree, that holds an address book; the key for the map
should be a person's name and the value should be the person's email address. You should provide the
ability to add email addresses to the map, remove email addresses, update email addresses, and of
course find email addresses. You'll also want to clean up your address book when your program shuts
down. As a reminder, you can use any of the standard C++ comparison operators (such as ==, < or >) to
compare two strings 

How can I make it search for email adresses in the binary tree consisting of key "name"? Or does it imply that It refers to one certain "key's" email adresses? And those adresses should be searchable? I don't quite get the question, maybe anyone does?

[Willo123]

But, I haven't entered chapter of the std libs yet, it wants me to use a raw style for solving it & getting a better understanding on how things work;

But I guess it wants me to;

struct node{
string key;
string value[3];
node* right;
node* left;
};

If key is correct, only then, u should be able to "find", "remove", or "add" email adresses", just for the specific "key" AKA name?

Should value be as an array then?
I'm sorry, I am just generally bad at understanding the questions sometimes.

Edit @gentleguy
I haven't yet, but it will come, this chapter is about binary trees

[Willo123]

I mean sure, I'll appreciate any help I get, and will try to learn from any code samples I may get, but generally just curious of;

"You should provide the
ability to add email addresses to the map, remove email addresses, update email addresses, and of
course find email addresses."

But if you search through a binary tree, (which I assume is the raw thing as a std::map(?)), If they are sorted by key(name), how will you find a certain email adress if the nodes are sorted by key and not "value"?

And if value(mail) should be multiple, it has to be as an array? A loop inside each node until you find the correct mail you searched for?

But does he imply that I should know the key on beforehand? Because otherwise I have no realistic idea of how to search through all of the nodes. (apart from literally recursively digging into every single nodes email, and then try to find it based on pure luck).

[keskiverto]

Should value be as an array then?

No. The value stores email address, which is one string.

You can have a tree with only unique keys (easier) or a tree, where more than one node may have same key.

When you insert new (name,address) to unique tree and the tree already contains a node with that key you can either modify the value of existing node, or report an error and leave the tree unchanged.

You search by "visiting" the nodes and testing whether the key matches the name you are searching with.

[Willo123]

@gentleguy
Sure:)!

@keskiverto
So basically, adding the nodes which contains "1 key & MAX 1 email adress", at a tree where it gets added based on if node is less than or greater than current root node? (so they get sorted by key)


Then it should search(based on key) through the binary tree if the key value is greater or less than (root key), then if it is lesser, it keeps digging left, greater, keeps digging right, when equal to,
it should stop & You have the ability to find the mail adress(cout), & replace/delete/edit it?

As I read it, you should be able to add multiple adresses to one key, which confused me with the array part.


BUT... if you do not have the key node, and want to search by Email, you have to search recursively through every single node until found, cause it could be anywhere in the tree, since you can't compare keys with; (> root or < root) anymore?

Did I understand the question?:P

[TwilightSpectre]

Umm... @gentleguy, the program you gave uses a linked list, not a binary tree (as the question asked for). Whoops.

@Willo123:
Yes, it looks like you've understood the question correctly, at least from my standpoint. In essence, you have a tree of (name: [emails]), for which you (as the question states) need to be able to add/remove/change emails for each 'name', as well as look through the tree to find an email address.

And yes, you'll need to do it recursively: Go down a step, check if the email was there. If it is, you're done, otherwise pick a node and go down another step. Repeat the process until you've run out of nodes, in which case take a step back and choose the other branch. If you run out of branches, then you can say you didn't find the email address.

Ideally, you'd use a std::vector for the array of emails, but if you're not allowed to use it then you could use a static array like you suggested (and give some arbitrary 'maximum' number of emails). Alternately you could roll your own dynamic array, though that can be complicated and difficult, or you could store all the emails in a single space- or semicolon-delimited string, and just search through the string to separate out the emails.

[MikeyBoy]

Umm... @gentleguy, the program you gave uses a linked list, not a binary tree (as the question asked for). Whoops.

You act is if this was an accident. Be advised that gentleguy is a known troll, who deliberately posts incorrect or misleading answers, for malicious purposes.

[doug4]

@Willo123,

Stop trying to figure out what @gentleguy is trying to give you. Solve the problem on your own.

I think you may be making things more difficult on yourself than you need to. I think "add email addresses to the map" means add an email address for a new name to the map, not add additional email addresses to a given name.

I also would interpret "remove email addresses" to mean remove the name/email address combination from the map. Given a name, remove the e-mail address. And I would interpret "find email addresses" to mean given a name, find the associated e-mail address. I don't think the problem statement requires you to compare email addresses at all (so no need to traverse the entire tree looking for an address). Everything can be done using the key values.

[JayhawkZombie]

Do not use a private message from gentleguy to get a solution, and blatantly taking a solution from someone else removes the opportunity to learn.

If gentleguy is confident in his solution, he can post it here, in a public thread. If he refuses to do so, then I'd take that as a sign that he is not confident in his solution or his ability to give assistance.

[keskiverto]

I do not know the book, but I presume that the task is to learn by doing basic dynamic memory management, basic pointers, and basic tree operations on basic binary tree.

Therefore, forget the plurals.

add email addresses to the map,
remove email addresses,
update email addresses,
and of course find email addresses

A test program might thus use:

int main() {
  node * book = nullptr; // empty book/tree/map

  // add addresses
  insert( book, "John", "john@here" ); // will add a node
  insert( book, "Jane", "jane@here" );
  insert( book, "Mike", "mc@there" );

  // update address
  update( book, "Jane", "jane.doe@here" ); // will change a node

  // remove address
  remove( book, "John" ); // will remove a node

  // find address
  std::string addr = search( book, "Jane" );

  // clean up your address book
  // ?
  return 0;
}

The operations do not have to be standalone functions. They could be member functions:

int main() {
  Tree book; // empty book
  book.insert( "John", "john@here" );
  std::string addr = book.search( "Jane" );

  // use destructor of class Tree to do the cleanup
  return 0;
}

Make first a version that will allow only unique keys and exactly one address per key.

You will still have plenty to do. Once you have done the "simple" version, you can make a "multi-address" version as "extra credit".

[Willo123]

Thanks for all kind replies & clarifications, I'm new here, but I do however regard @gentleguy's reply as very hard for me as a beginner! I am indeed trying to understand what I am doing, and I'm very interested in learning what I am actually doing!

This is my current progress, I will try to update it with the rest tommorow, a big thanks for the help.

To do:
- Understand how to edit/search a certain part of a string(like multiple email adresses ending with ;"
- Feedback, whatever I may have not thought of?
- I guess a new search also had to be implemented, searching through entire tree recursively looking after a certain email adress and not "name".

//Binary Search Tree Program
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <stdio.h>
#include <windows.h>
#include <math.h>
#include <cmath>

using namespace std;

struct node{
string name;
string email;
node* right;
node* left;
};

node *addElement(node* root, string name, string email){
if (root == NULL){
    node* newNode = new node;
    root = newNode;
    newNode->name = name;
    newNode->email = email;
    newNode->right = NULL;
    newNode->left = NULL;
}
else if (name < root->name){
   root->left = addElement(root->left, name, email);
}
else if (name > root->name){
    root->right = addElement(root->right, name, email);
}
else{
    cout << "The name is already in use!\n Select a new name\n";
}
return root;
}

int searchMap(node *root, string name, int input)
{
    if (root == NULL){
            cout << "\nMapOwner does not exist.\n\n"; return 0;
    }
    if (name == root->name){
        cout << "\nFound map! \nMapOwner: " << root->name << "\nEmail: " << root->email << "\n\n";
        cout << " 1. Edit your email\n 2. Add an email adress\n 3. Delete an email-adress\n 4. Do nothing\n";
        cin >> input;
        string mail;

        switch (input){
            case 1:
                cout << "Enter mail;\n";
                cin >> mail;
                root->email = mail;
                cout << "\n" << root->email << "\n";
                break;

            case 2:
                cout << "Enter mail;\n";
                cin >> mail;
                root->email = root->email + ";" + mail + ";"; '\n';
                cout << root->email;
                break;

            case 3:
                root->email = "";
                cout << "<Empty>\n";
                break;

            case 4:
            break;
        }
}
else if (name < root->name){
    searchMap(root->left, name, input);
}
else if (name > root->name){
    searchMap(root->right, name, input);
}
return 0;
}

node *deleteBook(node *root)
{

    if (root != NULL){
    deleteBook(root->left);
    deleteBook(root->right);


    delete root;
    root = NULL;
    return root;
}
}


int main ()
{
      /*6. Implement a simple map, in the form of a binary tree, that holds an address book; the key for the map
should be a person's name and the value should be the person's email address. You should provide the
ability to add email addresses to the map, remove email addresses, update email addresses, and of
course find email addresses. You'll also want to clean up your address book when your program shuts
down. As a reminder, you can use any of the standard C++ comparison operators (such as ==, < or >) to
compare two strings*/

    /*root = addElement(root,"Wille");
    root = addElement(root,"Kelle");
    root = addElement(root,"Lullor");
    root = addElement(root,"Sollke");
    root = addElement(root,"Fitto");
    root = addElement(root,"YxO");
    root = addElement(root,"Memo");
    root = addElement(root,"Jayyao");*/


    node *root = NULL;
    int input;
    string name;
    string email;
    while (input != 0){

    cout << "Select method:\n1. Add an element to the tree\n2. Search after a specific map by its Name:\n3. Exit and de-allocate memory\n";
    cin >> input;

    switch (input){
    case 1:
        cin.clear();
        cin.ignore();

        cout << "Enter your name: \n";
        getline(cin, name, '\n');
        cout << "Enter your first email: \n";
        getline(cin, email, '\n');

        root = addElement(root, name, email);
        break;

    case 2:
        cin.clear();
        cin.ignore();

        cout << "Which Mapname would you like to search after?\n";
        getline(cin, name);
        searchMap(root, name, 1000);
        break;

    case 3:
        root = deleteBook(root);
        break;
}
}
}

[Willo123]

Oh, I just forgot to remove it all from earlier practices!

[Willo123]

Nope, it works for me without any problems I think? Did you find/encounter any problem or?
https://i.gyazo.com/d112654105851005f3910c6b668ba6c1.png (pic)

[cire]

searchMap promises to return a value, but it only does in some cases. Relying on that value in the cases where it doesn't return a value results in undefined behavior. I can see that you never do anything with the return value... so why does it promise to return one?

[Willo123]

@gentleguy
Yeah well I did test all the features & resulted in no errors/crashes, but I found a few small problems today, occuring while searching after names with spaces, & program terminating after searching. (edited main post)

@cire
hmm, but Isn't the only times it will need a return 0, when it should terminate, which is only if root is either NULL, or if root->name = name (where it finds the search?)

EDIT: I suppose I should have a return 0; at the very bottom aswell? That may be what I forgot. Should it be done in a void instead? But there I can't return if something happens?

[keskiverto]

EDIT: I suppose I should have a return 0; at the very bottom aswell? That may be what I forgot. Should it be done in a void instead? But there I can't return if something happens?

If a function promises to return a value, then it must return a value on every exit path. Your compiler should warn if you have a function that does not.

There are two versions of return: return expr; and return;
The latter is for void functions:

void foo( bool test ) {
  if ( test ) return;
  // other code
}

There are various strategies for how to handle an "error" situation.

A Search(key) could return a pointer to the node that contains the key. If there are no nodes in the tree or no node contains the key, then the returned value is nullptr. It is the responsibility of the user to check the pointer's validity :

auto found = Search( "fubar" );
if ( found ) {
  // assertion: found->key == "fubar"
  // use found
}

[dhayden]

Line 62 contains two statements:

root->email = root->email + ";" + mail + ";";
 '\n';

The second one doesn't do anything.

Add constructors to struct node:

    node() :
        right(NULL), left(NULL)
    {}
    node(const string &n, const string &e) :
        name(n),
        email(e),
        right(NULL),
        left(NULL)
    {}

Here is a trick to make life a whole lot easier: create a method that finds a node, not instead of returning a pointer to the node, return a reference to the pointer to the node. If the node isn't in the tree, return a reference to the pointer where the node should go:

// Find the node for the name.  Returns a reference to the pointer
// to the node, or a reference to the null pointer where the node should go
node * &find(node * &root, const string &name)
{
    if (name == root->name) {
        return root;
    } else if (name < root->name) {
        return find(root->left, name);
    } else {
        return find(root->right, name);
    }
}

Now addElement becomes almost trivial:

bool
addElement(node * &root, string name, string email)
{
    node * &ptr(find(root, name));
    if (ptr) {
        return false;
    }

    ptr = new node(name, email);
    return true;
}

Let's look at searchMap. What does it do?
- search for an item
- prompt the user for what to do with it
- edit the item accordingly.

The parameters are the root of the tree, the name to search for and something called "input". Huh? If I'm calling your searchMap function, what is this "input" parameter? Since nothing useful is passed in, that should be a local variable. Also, searchMap should can use the find() function above.

int
searchMap(node *root, string name)
{
    int input(0);

    node *ptr = find(root, name);
    if (ptr == NULL) {
        cout << "\nMapOwner does not exist.\n\n";
        return 0;
    }

    cout << "\nFound map! \nMapOwner: " << root->name << "\nEmail: " << root->
        email << "\n\n";
    cout <<
        " 1. Edit your email\n 2. Add an email adress\n 3. Delete an email-adre\
ss\n 4. Do nothing\n";
    cin >> input;
    string mail;

    switch (input) {
    case 1:
        cout << "Enter mail;\n";
        cin >> mail;
        ptr->email = mail;
        cout << "\n" << ptr->email << "\n";
        break;

    case 2:
        cout << "Enter mail;\n";
        cin >> mail;
        ptr->email = ptr->email + ";" + mail + ";";
        cout << ptr->email;
        break;

    case 3:
        ptr->email = "";
        cout << "<Empty>\n";
        break;

    case 4:
        break;
    }
    return 0;
}

By the way, the last case where you delete an email may not be right. Should it remove the node from the tree? This is definitely the hardest operation to do in a binary tree and it's often ignored in beginning programming classes, so maybe you don't need to do it.

[Willo123]

@keskiverto
Hmm alright, I get the first part, but do you mind showing me a more full second example? I don't quite get it I'm afraid =/.

I tried, but here I really don't get the point of the return as pointer statement, cause I haven't understood the advantages I assume

node *Search(node *root, string name)
{
    if (root != NULL){
    if (name == root->name){
    cout << root->name << "\n";
    }
    if (name>root->name)
    return root = Search(root->left, name);

    else if (name<root->name)
    return root = Search(root->right, name);
    }
    return NULL;
}

EDIT:
@dhayden Didn't see u posted, will read it

EDIT2: Line62, true!
Hmm ok, I haven't learned about constructors/methods/ yet though, so I will try to come back and re-read it when I know more:)

And no, I don't believe I should be able to remove the actual node email.
Thanks for your reply!