Computer Science Canada

Binary Search Trees
Author:  jin [ Fri Mar 23, 2007 6:31 pm ]
Post subject:  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

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);
}
Author:  klopyrev [ Sat Mar 24, 2007 8:44 am ]
Post subject:  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.

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

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy