Remove multiple entries from Binary Search Tree

[FeedMeTacos]

I'm currently working on a binary search tree project for school that uses a BST to organize book data. I have completed nearly all of the requirements for my project except for one function where I need to remove all entries where for a specific author chosen by the user.

The tree is organized by keyword. I have two removal tasks for this project, one is to remove a single entry by keyword which I have successfully done. The other is to remove all entries for a specific author. This is the one I'm having trouble with. I have tried many different variations, but I'm having difficulty with this task. I am having a difficult time figuring out where I am at in the tree (when using cout statements), so I can't tell what I may need to adjust. I'm also not positive if I can use the removeBook function in my removeAllMatches, or if that is part of my problem.

I end up either removing a single entry, or deleting the entire tree (previous attempt with using a for-loop). Since the tree is organized by keyword and that remove function works, I decided to try calling that function when there is a correct author match. So, when a match is present, it passes in the keyword for that specific entry and then the removeBook function takes over. When it completes, it should move on to checking the other entries in the tree.

Can someone explain to me what's going wrong and how I should go about fixing it?

These are the relevant functions that I'm working with, but let me know if I need to include anything else. If I need to upload header/implementation files and a main function to test, I can do so.

void BST::removeAllMatches(Book &aBook)
{
	char author[25];
	cout << "Enter the author to remove from the list: " << endl;
	cin.get(author, 25, '\n');

	removeAllMatches(root, author, aBook);
}


bool BST::removeAllMatches(Node *&currRoot, const char *author, Book &aBook)
{
	int temp = 0;
	char match[25];
	char key[50];

	bool flag = false;

		if (currRoot)
		{
			currRoot->data.getAuthor(match); 
			temp = strcmp(author, match);
			
			if (temp == 0)
			{
				currRoot->data.getKeyword(key);
				removeBook(currRoot, key, aBook);
				flag = true;
			}
			else if (temp < 0)
			{
				currRoot = currRoot->left;
				currRoot->data.getKeyword(key);
				removeAllMatches(currRoot->left, key, aBook);
			}
			else
			{
				currRoot = currRoot->right;
				currRoot->data.getKeyword(key);
				removeAllMatches(currRoot->right, key, aBook);
			}
		}

	return flag;
}

// remove single Book by keyword
bool BST::removeBook(char *key, Book &removeEntry)
{
	return removeBook(root, key, removeEntry);
}

// recursive single removal helper
bool BST::removeBook(Node *&currRoot, char *key, Book &removeEntry)
{
	char keyword[50];

	if (!currRoot)
		return false; 

	currRoot->data.getKeyword(keyword);

	int temp = strcmp(key, keyword);
	
	if (temp == 0)
	{

		removeEntry = currRoot->data;
		deleteNode(currRoot);
		size--;
		return true;
	}
	else if (temp < 0) // remove from left tree
	{
		return removeBook(currRoot->left, key, removeEntry);
	}
	else // remove from right tree
	{
		return removeBook(currRoot->right, key, removeEntry);
	}
}

void BST::deleteNode(Node *&target)
{
	if (!target->left && !target->right)
	{
		delete target;
		target = nullptr;
	}
	else if (!target->right)
	{
		Node *temp = target;
		target = target->left;
		delete temp;
		temp = nullptr;
	}
	else if (!target->left)
	{
		Node *temp = target;
		target = target->right;
		delete temp;
		temp = nullptr;
	}
	else
	{
		// find the inorder successor
		Node *prev = nullptr;
		Node *curr = target->right;
		while (curr->left)
		{
			prev = curr;
			curr = curr->left;
		}

		target->data = curr->data;
		if (!prev)
		{
			target->right = curr->right;
		}
		else
		{
			prev->left = curr->right;
		}
		delete curr;
	}

}

[jonnin]

an easy way to delete multiple is to loop the delete 1 code. that algorithm is find keys for all you want to delete, and call delete on each one by the key.


you can do a lazy delete: mark items as deleted but leave them in place for now by putting a 'is deleted' in your nodes.
Then every once in a while (you decide this, every 10 min or every 50th call to a delete function or whatever (can do that with a static variable) ) you just make a new tree from the old tree, traversing it to hit every node and skipping the deleted ones on the rebuild. Your other routines like search/print/whatever need to know to skip deleted items but traverse their children as normal.

try the first approach, is my take on it for classwork.

[FeedMeTacos]

Thank you for the reply and explanation. I ended up rewriting my removeAllMatches function as sort of a combination of what I already had written and my single remove function. Whenever a match is found, the program does the following routine

removeEntry = currRoot->data;
deleteNode(currRoot);
size--;
flag = true;
removeAllMatches(currRoot, topic, removeEntry);

Then I call the same function for the left and right trees. It seems to be working well.