Binary Search Trees

[jin]

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

code:

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]

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.

code:

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

code:

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

Hope that helps.

KL