How to modify and search for a values in a tree?

[Lacy9265]

Write a program that maintains a database containing data, Name and Birthday. You will be able to enter, remove, modify or search this data. Initially, you can assume that the names are unique. Design a class to represent the database and another to represent the people. Use binary search of people as a data member of the database class. Right now I'm having trouble how to implement the functions from PeopleTree.h to Driver.cpp so if the user wants to search for a person by name or search by month. Also, if the user wants to modify a person's birthday. The code for this project includes Driver.cpp, People.h, and PeopleTree.h. The PeopleTree.h file is in the next post below.

Here are the options the user is given.
Enter Add a new person to you list.
Modify Change the name or birthday of a person.
Remove Remove a person from your list.
Search Display the information about a given person (unique name).
Query: Run a query that displays the people by asking the user to enter a month.
Print List everyone in the database.

//Driver.cpp
#include <iostream>
#include <fstream>
#include "PeopleTree.h"
int main() {

    // Declare variables
    int userChoice = 0;
    std::string name;
    std::string birthday;
    std::string month;
    PeopleTree people;

    do {
        
        std::cout << "1.Add a new person to list" << std::endl;
        std::cout << "2.Modify a person's birthday" << std::endl;
        std::cout << "3.Remove a person from the list" << std::endl;
        std::cout << "4.Search for a person by name" << std::endl;
        std::cout << "5.Search for a month(query)" << std::endl;
        std::cout << "6.Print the entire list" << std::endl;
        std::cout << "7.Quit" << std::endl;
        std::cout << "Enter your choice: ";
        std::cin >> userChoice;

        switch (userChoice) {

        // If type '1' then ask user to enter name and birthday
        // then added what user types to list
        case 1:
        {
            std::cout << "Enter name" << std::endl;
            std::cin >> name;
            std::cout << "Enter Birthday (Ex: Month, Day): ";
            std::cin >> birthday;
            people.insert(name, birthday);
        }
        break;

        // If user types '2' then ask user for person's name and new birthday
        // Then delete previous birthday and add new birthday
        case 2:
        {
            std::cout << "Enter name of the person you would like to modify" << std::endl;
            std::cin >> name;
            people.find(name);
            std::cout << "Enter the new person's birthday" << std::endl;
            std::cin >> birthday;
        }
        break;

        // If the user selects '3' then remove person from list
        case 3:
        {
            std::cout << "Enter the name of the person you want to remove" << std::endl;
            std::cin >> name;
            people.remove(name);
        }
        break;
        // If user type '4' then search for person name user entered
        // then print the birthday of that person
        case 4:
        {
            std::cout << "Enter the name of the person you want to search for" << std::endl;
            std::cin >> name;
            people.find(name);
        }
        break;

        // If user types '5' then search for who's birthdays are in month entered by user
        case 5:
        {
            std::cout << "Enter the month you want to search for" << std::endl;
            std::cin >> month;
            people.findMonth(month);
        }
        break;

        // If user types '6' then print the entire list
        case 6:
        {
            people.printInOrder();
        }
        break;

        // If user types '7' then exit program
        case 7:
        {
            exit(1);
        }
        break;
        }

       
    }
    // While the user choice is not to quit 
    while (userChoice != '7');
}

//People.h
#include <string>
#include <iostream>

class People {
private: 
	std::string name;
	std::string birthday;

public:
	People();
	People(std::string name, std::string birthday);
	~People();

	void print();

	void setName(std::string name);
	void setBirthday(std::string birthday);


	std::string getName();
	std::string getBirthday();
	bool operator >(People& obj) {
		return name > obj.name;
	}
	bool operator<(People& obj) {
		return name < obj.name;
	}
	bool operator==(People& obj) {
		return name == obj.name;
	}

};


inline People::People() {
	name;
	birthday ;
}

inline People::People(std::string empName, std::string empBirthday) {
	name = empName;
	birthday = empBirthday;
}
inline People::~People() {

}
inline void People::setName(std::string n) {
	name = n;
}
inline void People::setBirthday(std::string b) {
	birthday = b;
}

inline std::string People::getName() {
	return name;
}

inline std::string People::getBirthday() {
	return birthday;
}

inline void People::print() {
	std::cout << "Name: " << name << std::endl;
	std::cout << "Birthday: " << birthday << std::endl;
}

[Lacy9265]

//PeopleTree.h
#pragma once
#include "People.h"
#include <iostream>
#include <cstdlib>
#include <string>

class PeopleTree {

private:
	struct node {
		node* left;
		node* right;
		People value;
	};
	node* root;

    void insert(node*& currentPtr, node* newNode);
    void remove(node*& currentPtr, std::string name);
    void printInOrder(node* currentPtr);
    People* find(node* current, std::string name);
	People* findMonth(node* current, std::string birthday);
    void deleteTree(node* currentPtr);

public:
	PeopleTree(const PeopleTree&) = delete;
	PeopleTree& operator=(const PeopleTree&) = delete;
	PeopleTree();
	~PeopleTree();

	void insert(std::string name, std::string birthday);
	void insert(People& item);
	void remove(std::string name);
	//bool search(std::string name);
	void find(std::string name);
	void findMonth(std::string birthday);
	void printInOrder();

};

inline PeopleTree::PeopleTree() {
	root = NULL;
}

inline PeopleTree::~PeopleTree() {
	deleteTree(root);
}

inline void PeopleTree::insert(node*& current, node* newNode) {

	//base case 1: current is null
	if (current == NULL) {
		current = newNode;
	}

	//general case 1: current->value < newNode->value
	else if (current->value < newNode->value) {
		/*will go to left node and then keep calling function and going through the tree
		until it hits a nullptr*/
		insert(current->left, newNode);
	}
	//general case 2: current->value > newNode->value
	else if (current->value > newNode->value) {
		/*will go to right node and then keep calling function and going through the tree
		until it hits a nullptr*/
		insert(current->right, newNode);
	}
}

inline void PeopleTree::insert(std::string name, std::string birthday) {
	//new employee object 
	People* newPeople = new People(name, birthday);
	//create a node to add to tree
	node* newNode = new node;
	//set left and right inside newNode
	newNode->left;
	newNode->right; //= nullptr;

	//now insert into tree
	insert(root, newNode);

}

inline void PeopleTree::insert(People& item) {

	//create new node
	node* newNode = new node;
	//set left and right pointers to nullptr
	newNode->left = NULL;
	newNode->right = NULL;

	insert(root, newNode);
}

inline void PeopleTree::deleteTree(node* current) {
	//base case
	if (current == NULL) {
		//do nothing
	}
	else {
		deleteTree(current->left);
		deleteTree(current->right);
		delete current;
	}
}

inline People* PeopleTree::find(node* current, std::string name) {
	//Base case 1:
	if (current == nullptr) {
		return nullptr;
	}
	//Base case 2:
	else if (current->value.getName() == name) {  // class has no memeber 
		return &current->value;
	}
	//General case:
	else {
		//go right or left
		if (name < current->value.getName()) { // class has no memeber 
			return find(current->right, name);
		}
		else {
			return find(current->left, name);
		}
	}
}

inline People* PeopleTree::findMonth(node* current, std::string birthday) {
	//Base case 1:
	if (current == nullptr) {
		return nullptr;
	}
	//Base case 2:
	else if (current->value.getBirthday() == birthday) {  // class has no memeber 
		return &current->value;
	}
	//General case:
	else {
		//go right or left
		if (birthday < current->value.getBirthday()) { // class has no memeber 
			return find(current->right, birthday);
		}
		else {
			return find(current->left, birthday);
		}
	}
}
//wrapper for find

inline void PeopleTree::find(std::string name) {

	People* found = find(root, name);

	if (found == nullptr) {
		std::cout << "That name is not in the tree." << std::endl;
	}
	else {
		std::cout << "Name: " << found->getName() << " Birthday: " << found->getBirthday() << std::endl;

	}
}

inline void PeopleTree::findMonth(std::string birthday) {

	People* found = find(root, birthday);

	if (found == nullptr) {
		std::cout << "That month is not in the tree." << std::endl;
	}
	else {
		std::cout << "Name: " << found->getName() << " Birthday: " << found->getBirthday() << std::endl;

	}
}



//Prints left nodes, current node, right nodes. Prints in descending order.
inline void PeopleTree::printInOrder(node* current) {

	//Base case: If null, do nothing

	//General case
	if (current != nullptr) {
		//prints the left nodes
		printInOrder(current->left);
		//prints the current node
		std::cout << current->value.getName() << current->value.getBirthday() << std::endl; // class has no memeber 
		//prints the right nodes
		printInOrder(current->right);
	}
}

inline void PeopleTree::printInOrder() {

	printInOrder(root);
}

inline void PeopleTree::remove(node*& current, std::string name) {

	//Base Case 1: Does the node exist?
	if (current == nullptr) {
		//do nothing
	}
	//Base Case 2: Item was found
	else if (current->value.getName() == name) { //Error occurs here 

		//Create a temp node pointer and set it equal to current
		node* tempPtr = current;

		//Check every case of nodes that may be attached to current node
		//Left and right point to null
		if (current->left == nullptr && current->right == nullptr) {
			current = nullptr;
		}
		//Left points to null, right points to somthing
		else if (current->left == nullptr && current->right != nullptr) {
			current = current->right;
		}
		//Left points to something, right points to null
		else if (current->left != nullptr && current->right == nullptr) {
			current = current->left;
		}
		//Left and right both point to something
		else {
			node* leftMost = current->right;
			while (leftMost->left != nullptr) {
				leftMost = leftMost->left;
			}
			leftMost->left = current->left;
			current = current->right;
		}
		delete tempPtr;
	}
	//General Case:
	else {
		if (name < current->value.getName()) {
			remove(current->left, name);
		}
		else {
			remove(current->right, name);
		}
	}

}

inline void PeopleTree::remove(std::string name) {

	remove(root, name);
}

[AbstractionAnon]

What is your question?

[Lacy9265]

I don't understand when the user selects modify or one of two searches how am I suppose to do that using the functions that I have in PeopleTree.h.

Basically having trouble with
Modify: Change the name or birthday of a person.
Search: Display the information about a given person (unique name).
Query: Run a query that displays the people by asking the user to enter a month.

[AbstractionAnon]

Modify: Change the name or birthday of a person.

Ask the user what name he wants to modify.
Use your Find function to find that entry.
Ask the user for the new name or birthdate
set the new name or birthdate into the entry you found.

Search: Display the information about a given person (unique name).

Ask the user for the name they want to search for.
Use your existing find function to find that entry.
Use your print function to print that entry.

Query: Run a query that displays the people by asking the user to enter a month.

Ask the user for the month they want.
Walk the tree examining each entry for a matching month.
If the month matches, print that entry.

edit: You need to modify your find function to return the address of the person found.

I don't know if you've learned function pointers yet. I like to have one and only one function that walks the tree. I pass that a function a function pointer to call for each node visited.

[jonnin]

I did not read the wall of code, but if this is a search tree, modification is annoying when it changes the sort-key field. When that happens, you have a few options:

the cheap way: mark the original node as deleted and reinsert it with the updated info (and the new one is not deleted). All your code will need to be 'deleted aware' if you do that.
the expensive way: delete the node and all its children and reinsert them all. You don't need to make new nodes, just rehook all the pointers -- you need an insert that accepts an already created node, if you do not have one like that.

search: if it is a search tree, there is a simple algorithm for that... if a node is less than where you are, search the left subtree, if greater, search the right, if equal you found it of course. If you hit a null child, its not there. This implies that you inserted the nodes in this manner, though.

queries: you can touch every node, but then why fool with making a tree at all? Allowing this means a tree was the wrong structure** (but, you gotta do what you gotta do in a classroom). Or maybe not 'wrong structure' but you are going to need additional containers to make searching fast, and making them all trees runs into the modification of the key problem frequently. A vector of vectors of pointer only entries that you keep sorted based off various criteria... anyway, for now, just touch all the nodes and realize that its a terrible way to do things!

** in my career, I can count on 1 hand with room to spare the number of times a classical pointer type tree was a better choice than anything else.