binarySearchTree delete function problem

This is a discussion on binarySearchTree delete function problem within the C++ Programming forums, part of the General Programming Boards category; When I try to use the deletePerson() function, it deletes the same node every time (I actually think its the ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    34

    Arrow binarySearchTree delete function problem

    When I try to use the deletePerson() function, it deletes the same node every time (I actually think its the root node). I'm thinking that the string I'm trying to delete isn't getting passed through to my interface file, because the function (in binarySearchTree class) itself works fine when called directly. Here is my code:

    Code:
    #ifndef person_h
    #define person_h
    #include <iostream>
    #include <string>
    #include "binarySearchTree.h"
    
    using namespace std;
    
    class person: public binarySearchTree
    {
    	friend ostream& operator<<(ostream&, const person&);
    	 
    public:
        void setPersonalInfo(treeNode *&root, string name, string address, 
    					  string phoneNum);
    	//Function to set the details of a video. 
        //The private data members are set according to the 
        //parameters.
    	//Postcondition:  personName = name;
    	//		personAddress = address;
    	//		personPhoneNum = phoneNum;
    	//		numInBook = setNumInBook;
    					
       	void printName(treeNode *&root) const;
    	//Function to print the names located in the address book; 
    
        void printInfo() const;
    	//Function to print the name and addresses in the address book;
    
        bool checkName(string name);
    	//Function to check if the name is already in the address book;
    
    	string getName();
    	//Function to return a name from the address book;
    	
        person(string name = "" , string address = "", 
    			  string phoneNum = "");
    	//constructor
    	//The private data members are set according to the incoming parameters;
    	//If no values are specified the default values are assigned.
    	//Postcondition: personName = name;
    	//		personAddress = address;
    	//		personPhoneNum = phoneNum;
    	
    	void addPerson(treeNode *&root, string name); //, string address, string phoneNum);
    	//Function to add a name and info to the address book;
    
    	void deletePerson(treeNode *&root, string name);
    	//Function to delete a name from the address book;
    
    	void findPerson(treeNode *&root, string name);
    	//Function to find a name located in the address book;
    
    	void modifyPerson(string name, string address, string phoneNum);
    	//Function to modify an entry in the address book;
    
    	//overload relational operators:
        bool operator==(const person&) const;
        bool operator!=(const person&) const;
    	bool operator<(const person&) const;
    	bool operator<=(const person&) const;
    	bool operator>(const person&) const;
    	bool operator>=(const person&) const;
    
    private:
        string personName;			//variable to store the name;
        string personAddress;		//variable to store the address;	
        string personPhoneNum;		//variable to store the phone number;	
        				
    };
    
    #endif
    #include <iostream>
    #include <string>
    #include "person.h"
    
    using namespace std;
    
    /**Function to set the details of an entry.  Private members are 
       set according to the parameters.
       Postcondition: personName = name;
    		personAddress = address;
    		personPhoneNum = phoneNum;
    		numInBook = setNumInBook;
      */
    void person::setPersonalInfo(treeNode *&root, string name, string address, 
    							 string phoneNum)
    {
    	
    	personName = name;
    	personAddress = address;
    	personPhoneNum = phoneNum;
    }
    
    
    /**Function to print the names located in the address book; */
    void person::printName(treeNode *&root) const
    {
    	
    	binarySearchTree tmp;
    
    	tmp.inOrderPrint(root);
    }
    
    /**Function to print the name and addresses in the address book;*/
    void person::printInfo() const
    {
    	cout<<"Name: "<< personName<<endl;
    	cout<<"Address: "<< personAddress <<endl;
    	cout<<"Phone Number: "<< personPhoneNum<<endl;	
    }
    
    /** Function to check if the name is already in the address book;  */
    bool person::checkName(string name)
    {
    	return(personName == name);
    }
    
    /** Function to return a name from the address book;  */
    string person::getName()
    {
    	return personName;
    }
    
    /** constructor
    	The private data members are set according to the incoming parameters;
    	If no values are specified the default values are assigned.
    	Postcondition: personName = name;
    			personAddress = address;
    			personPhoneNum = phoneNum;
    			numInBook = setNumInBook;  */
    person::person(string name, string address, 
    					 string phoneNum)
    {
    	setPersonalInfo(root, name, address, phoneNum);
    }
    
    /**Function to add a name and info to the address book; */
    void person::addPerson(treeNode *&root, string name)
    {
    	binarySearchTree tmp;
    	
    	tmp.treeInsert(root, name);
    }
    
    /**Function to delete a name from the address book; */
    void person::deletePerson(treeNode *&root, string name)
    {
    	binarySearchTree tmp;
    		
    	tmp.treeDelete(root, name);
    }
    
    /**Function to find a name located in the address book;  */
    void person::findPerson(treeNode *&root, string name)
    {
    	binarySearchTree tmp;
    	
    	if(!tmp.treeContains(root, name))
    	{
    		cout<<name<<" not found"<<endl;
    	}
    	else
    		cout << name << " found" <<endl;
    }
    
    /**Function to modify an entry in the address book;  */
    void person::modifyPerson(string name, string address, string phoneNum)
    {
    	//to be added later
    }
    
    /** overload the relational operators */
    bool person::operator==(const person& right) const
    {
    	return (personName == right.personName);
    }
    
    bool person::operator!=(const person& right) const
    {
    	return (personName != right.personName);
    }
    
    bool person::operator<(const person& right) const
    {
    	return (personName < right.personName);
    }
    
    bool person::operator<=(const person& right) const
    {
    	return (personName <= right.personName);
    }
    
    bool person::operator>(const person& right) const
    {
    	return (personName > right.personName);
    }
    
    bool person::operator>=(const person& right) const
    {
    	return (personName >= right.personName);
    }
    
    ostream& operator<<(ostream& os, const person &person)
    {
    	os<<endl;
    	os<<"Name: "<< person.personName <<endl;
    	os<<"Address: "<< person.personAddress << endl;
    	os<<"_____________________________________"<<endl;
    	return os;
    }
    
    #ifndef binarySearchTree_h
    #define binarySearchTree_h
    
    #include <string>
    #include <iostream>
    
    using namespace std;
    
    //Define the node
    struct treeNode
    //An object of type TreeNode 
    {
    	string data;
    	treeNode *left;
    	treeNode *right;
    
    treeNode(string str)
    		//constructor: Make a node containing str.
    {
    	data = str;
    	left = NULL;
    	right = NULL;
    }
    
    };
    
    //define the class
    class binarySearchTree
    {
    public:
    	binarySearchTree(); 
    		//constructor
    	void treeInsert(treeNode *&root, string newItem);
    		//Add an item to the binary sort tree
    		//to which the parameter 'root' refers.
    	void treeDelete(treeNode *&root, string deleteItem);
    		//Delete an item from the binary sort tree
    		//to which the parameter 'root' refers.
    	void inOrderPrint(treeNode *&root);
    		//Print all the items in the tree to which
    		//the tree points
    	int countNodes(treeNode *root);
    		//count the nodes in the binary tree
    		//and return the answer
    	bool isEmpty() const;
    	    //returns true if tree is empty
    	bool treeContains(treeNode *root, string data);
    		//return true if item is one of the items in the 
    		//binary sort tree to which root points. Return
    		//false if not
    
    
    protected:
    	treeNode *root;
    	
    };
    #endif
    
    #include "binarySearchTree.h"
    
    #include <string>
    #include <iostream>
    
    using namespace std;
    
    binarySearchTree::binarySearchTree() :root(NULL)
    {
    }
    void binarySearchTree::treeInsert(treeNode *&root, string newItem)
    		//Add an item to the binary sort tree
    		//to which the parameter 'root' refers.
    {
    	if(root == NULL)
    	{
    		//the tree is empty.  Set root to point to a new node containing
    		//the new item.  This becomes the only  node in the tree.
    
    		root = new treeNode(newItem);
    		//left and right subtrees of root are automatically set to NULL by 
    		//the constructor
    		return;
    	}
    	else if(newItem < root->data)
    	{
    		treeInsert(root->left, newItem);
    	}
    	else
    	{
    		treeInsert(root->right, newItem);
    	}
    }//end treeInsert
    
    void binarySearchTree::treeDelete(treeNode *&root, string deleteItem)
    	//Delete an item from the binary sort tree
    	//to which the parameter 'root' refers.
    {
    
    	treeNode *previous, *tmp = root;
    
    	if(root == NULL)
    	{
    		//the tree is empty
    		cout << "The tree is empty, can't delete from an empty tree" << endl;
    	}
    	else if(root->right == NULL)
    	{
    		root = root->left;
    	}
    	else if(root->left == NULL)
    	{
    		root = root->right;
    	}
    	else
    	{
    		tmp = root->left;
    		previous = root;
    		while(tmp->right !=NULL)
    		{
    			previous = tmp;
    			tmp = tmp->right;
    		}
    		root->data = tmp->data;
    		if(previous == root)
    			previous->left = tmp->left;
    		else previous->right = tmp->left;
    	}
    	delete tmp;
    }//end deleteNode
    
    void binarySearchTree::inOrderPrint(treeNode *&root)
    	//Print all the items in the tree to which
    	//the tree points
    {
    	if(root !=NULL)
    			//otherwise, there is nothing to print
    	{
    		inOrderPrint(root->left); //prints items in left subtree
    		cout << root->data << " ";//print the root item
    		cout << endl;
    		inOrderPrint(root->right);//print the items in rigth subtree;
    	}
    
    }//end inOrderPrint()
    int binarySearchTree::countNodes(treeNode *root)
    	//count the nodes in the binary tree
    	//and return the answer
    {
    	if(root==NULL)
    		return 0;  //the tree is empty
    	else
    	{
    		int count = 1;  //start by counting the root
    		count += countNodes(root->left);  //add the number of nodes
    										  //in the left subtree
    		count += countNodes(root->right); //add the number of nodes
    										  //in the right subtree
    		return count;  //return the total
    	}
    }//end countNodes
    
    bool binarySearchTree::isEmpty() const
    		//return true if tree is empty
    {
    	return (root == NULL);
    } 
    
    bool binarySearchTree::treeContains(treeNode *root, string data)     
    		//return true if item is one of the items in the 
    		//binary sort tree to which root points. Return
    		//false if not
    	{
    		if(root==NULL)
    			//tree is empty
    		{
    			cout << "Can't search an empty tree " << endl;
    				return false;
    		}
    		if(data==root->data)
    			//item has been found
    		{
    			return true;
    		}
    		
    		if(data < root->data)
    			//item is in left subtree
    		{
    			return treeContains(root->left, data);
    		}
    		else
    			//item is in right subtree
    		{
    			return treeContains(root->right, data);
    		} 
    	
    	} //end treeContains()
    
    #include "binarySearchTree.h"
    #include "person.h"
    
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
    	person myList;
    	binarySearchTree list;
    	treeNode *root;  //pointer to the root noode in the tree
    	root = NULL;  //start with an empty tree
    	string someName;
    	int choice;
    	int num = 0;
    	
    	cout << "What would you like to do? "<< endl;
    	cout << "1=insert" << endl;
    	cout << "2=count the nodes" << endl;
    	cout << "3=print the nodes" << endl; 
    	cout << "4=delete a node" << endl;
    	cout << "5=find a name" << endl;
    	cout << "9=exit "<< endl;
    	cout << endl;
    	cin >> choice;
    	cin.ignore(100, '\n');
    	while(choice !=9)
    	{
    		switch (choice)
    		{
    		case 1: cout << "Enter a name for the list: " ;
    				getline(cin, someName);
    				myList.addPerson(root, someName);
    				break;
    
    		case 2: cout << "The number of nodes in the tree are: ";
    				num =  list.countNodes(root);
    				cout << num ; 
    				break;
    
    		case 3: cout << "Here is the list: " << endl;
    				myList.inOrderPrint(root);
    				break;
    
    		case 4: cout << "What item to delete? ";
    				getline(cin, someName);
    				myList.deletePerson(root, someName);
    				cout << someName << "is deleted." << endl;
    				list.inOrderPrint(root);
    				break;
    		case 5: cout << "What name are you searching for? ";
    				getline(cin, someName);
    				myList.findPerson(root, someName);
    				break;
    
    		default: cout << "Invalid selection" << endl;
    		
    		} //end switch
    
    	cout << endl;
    	cout << "What would you like to do? "<< endl;
    	cout << "1=insert" << endl;
    	cout << "2=count the nodes" << endl;
    	cout << "3=print the nodes" << endl; 
    	cout << "4=delete a node" << endl;
    	cout << "9=exit "<< endl;
    	cout << endl;
    	cin >> choice;
    	cin.ignore(100, '\n');
    	cout << endl;
    	}//end while
    	
    
    	cout << endl;
    	return 0;
    }
    main() is simply a test. My teacher will use a driver file, so I haven't put much effort into making main very pretty

    If I enter a list of names as follows:

    fred
    barney
    wilma
    dino

    and I try to delete dino, fred gets deleted. I assume its simply deleting the root node?

    Thanks for your help.

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    There is a very clear algorithm in the treeContains (of course it uses recursion but for the start it's OK)

    And what about delete? How it supposes to find the node to be deleted if it does not even uses the data to be deleted?

    Do you always ignore the compiler warnings? Or your compiler does not warn you if the parameter is not used?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Overall, your design is confusing because you have a distinct separation between nodes and trees, but your setup suggests otherwise. At the moment, having a tree class is pointless because you get the same effect you would from a handful of functions in a namespace.

    >it deletes the same node every time
    Your deletion algorithm deletes the root you pass it. Since you always pass the root of the tree, that's what gets deleted. Most operations in a binary search tree involve a search, and that includes deletion.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    Quote Originally Posted by vart
    There is a very clear algorithm in the treeContains (of course it uses recursion but for the start it's OK)

    And what about delete? How it supposes to find the node to be deleted if it does not even uses the data to be deleted?

    Do you always ignore the compiler warnings? Or your compiler does not warn you if the parameter is not used?

    There are no warnings. I blew up my Linux (Ubuntu 6.02) when I tried to update the distribution to the new 6.10. So, I'm using (cough cough) Visual C++.

    My confusion is just what you asked. I'm not sure how to pass what I want to be deleted over to the person class. I tried a couple of things, but that is when I started getting errors.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >There are no warnings.
    Every decent compiler has a setting for "evil bastard", where you can get all kinds of nifty warnings to help improve your code.

    >I'm not sure how to pass what I want to be deleted over to the person class.
    What you're passing now is fine. The problem is in your deletion algorithm. Presumably you've had time (about 25 minutes from the time of my post to yours) to read my post, follow the link, and be enlightened, yet I get the feeling you've ignored me completely.
    My best code is written with the delete key.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Its called "delete by copy" and is very elegant, I think.
    I know what it is. What you don't seem to understand is that you've implemented it incorrectly. Rather, you've missed a step. Your algorithm does indeed delete a node, and as long as you pass the node you want to delete, all is well. However, first you do this:
    Code:
    myList.deletePerson(root, someName);
    And then you do this:
    Code:
    tmp.treeDelete(root, name);
    There's never a search for someName. You always delete the root of the tree. That's why a deletion algorithm typically includes a search for the data first, then deletes it using a process such as the one you're using. Your code is broken, and it can be easily and repeatedly proven even when you "call it directly" as you claim works:
    Code:
    int main()
    {
      binarySearchTree treeHandler;
      treeNode *root = 0;
      string a[] = {"This", "is", "a", "test"};
    
      for ( int i = 0; i < 4; i++ )
        treeHandler.treeInsert ( root, a[i] );
    
      treeHandler.inOrderPrint ( root );
      cout<<"==================\n";
      treeHandler.treeDelete ( root, "a" );
      treeHandler.inOrderPrint ( root );
    }
    >If I'm in a test, do you think my teacher would mind if I refer to your web site?
    You can if you'd like. Though it's best to use what you learned in class and only use external references to enhance what you've been told already or correct mistakes.

    >I can't seem to figure out how to access the item I'm trying to delete
    That's what my site is there for. You don't have to copy the code verbatim, but keep in mind that it is correct. At the very least you can enumerate the steps needed and get ideas for how to write the code by looking at an existing implementation.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    [QUOTE=Prelude]>Its called "delete by copy" and is very elegant, I think.
    I know what it is. What you don't seem to understand is that you've implemented it incorrectly. Rather, you've missed a step. Your algorithm does indeed delete a node, and as long as you pass the node you want to delete, all is well. However, first you do this:
    Code:
    myList.deletePerson(root, someName);
    And then you do this:
    Code:
    tmp.treeDelete(root, name);
    There's never a search for someName. You always delete the root of the tree. That's why a deletion algorithm typically includes a search for the data first, then deletes it using a process such as the one you're using. Your code is broken, and it can be easily and repeatedly proven even when you "call it directly" as you claim works:
    Code:
    int main()
    {
      binarySearchTree treeHandler;
      treeNode *root = 0;
      string a[] = {"This", "is", "a", "test"};
    
      for ( int i = 0; i < 4; i++ )
        treeHandler.treeInsert ( root, a[i] );
    
      treeHandler.inOrderPrint ( root );
      cout<<"==================\n";
      treeHandler.treeDelete ( root, "a" );
      treeHandler.inOrderPrint ( root );
    }
    OK, now I see what you were saying. It wasn't clear the first time. So, I need to search for the item first (thought that was happening, now I see the hole), then do the delete. I am not bright enough to follow the code you wrote however. At least I'm not clever enough to figure out how to convert it to strings and use it in my program without big changes.

    I suppose I will keep at it until I figure it out.

    thanks

  8. #8
    Registered User
    Join Date
    Nov 2006
    Posts
    34

    Cool

    Nope, I didn't ignore you. The delete function I am using was proposed by Thomas Hibbard and Donald Knuth. Its called "delete by copy" and is very elegant, I think. It works very well, when I call it directly.

    The reason you felt like I was ignoring you, is because I don't want to solve my problem by using your code. My code works, but its in the interface I'm having problems.

    I have to restructure everything anyway, because my teacher reminded me there will be a driver he uses (I still don't have access to it) and I can't use the treeNode *&root in the file. SO, back to the drawing board.

    I did go to the web site, and it is very well done. If I'm in a test, do you think my teacher would mind if I refer to your web site? Or would it be better for me to use what I know? LOL

    You are absolutely right, and, as I mentioned at the end of my first post, I'm passing the root, and that is all that is deleting. I can't seem to figure out how to access the item I'm trying to delete, which is what your response reiterated also. But thank you for your input.

    TMS

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 10-28-2009, 10:25 AM
  2. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 09:18 PM
  3. Delete Function in Doubly Linked List
    By Dampecram in forum C Programming
    Replies: 5
    Last Post: 11-15-2008, 04:30 PM
  4. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  5. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21