-----------------------------------

jin

Fri Mar 23, 2007 6:31 pm


Binary Search Trees

-----------------------------------

Hey i am using binary search trees and my deletion code is giving me problems. in theory this woks by traversing through the tree until it finds the node to delete. then it checks if it has subtrees or not if i does not then deletes it. If one subtree replaces itself and if two subtrees then finds the largest value smaller than itself and replaces it. There are no compile time errors only run time errors after i delete a value. If you know how to fix this or a better way to code the deletion please let me know. thanks 


bool 
studentDB::remove(unsigned int studentNum)
{
	// Variable Declaration
	bool result = false;
	treeNode* target = root;
	treeNode* targetParent = NULL;

	while (target != NULL)
	{
		if (target->getStudentRec()->getStudentNumber() == studentNum)
			break;
		targetParent = target;
		if (target->getStudentRec()->getStudentNumber() > studentNum)
			target = target->getLeftChild();
		else
			target = target->getRightChild();
	}

	if (target == NULL)
		return (result);

	treeNode* child = target;
	treeNode* childParent = NULL;

	while (child != NULL)
	{
		if (child->getRightChild() == NULL)
			break;
		childParent = child;
		child = child->getRightChild();
	}

	if (child == NULL)
	{
		if (targetParent->getLeftChild()==target)
			targetParent->setLeftChild(target->getRightChild());
		else
			targetParent->setRightChild(target->getRightChild());
	}

	else
	{
		if (childParent!=NULL)
			childParent->setRightChild(child->getLeftChild());
		child->setLeftChild(target->getLeftChild());
		child->setRightChild(target->getRightChild());

		if (targetParent!=NULL)
		{
			if (targetParent->getLeftChild()==target)
				targetParent->setLeftChild(child);
			else
				targetParent->setRightChild(child);
			delete target;
		}
		else
		{
			childParent->setRightChild(NULL);
			target->setLeftChild(child->getLeftChild());
			target->setRightChild(child->getRightChild());
			delete child;
		}
	}
	result = true;
	// Return true/false to indicate if record was removed or not from database.
	return (result);
}



-----------------------------------

klopyrev

Sat Mar 24, 2007 8:44 am


Re: Binary Search Trees

-----------------------------------

Like you said, to delete a node, you need to find the largest child smaller than it. So, you would go right of the target and immediately after, go left. Your code continues to go right until it finds a null right node.


while (child != NULL) 
   { 
      if (child->getRightChild() == NULL) 
         break; 
      childParent = child; 
      child = child->getRightChild(); 
   } 


I didn't read the entire code, but perhaps that should be 


 while (child.getLeftChild() != NULL) 
   { 
      childParent = child; 
      child = child->getRightChild(); 
   } 


Hope that helps.

KL