C++ Binary search tree delete issue

Question

I am new on C++. My background is from PHP and C#. I implement Binary search tree in VC++ in Visual Studio 2005

All operations are fine, I am facing the problem with delete in one particular scenario, i.e. when I try to delete head twice or more times.

Proposed strategy is

Find minimum in the right sub tree

Replace the node you want to delete with minimum

delete minimum

In my code 8 is on the top, when I delete top, first time, than 11 become top from right sub tree, If I delete any other node, code is working fine, but if I delete top again(after deletion of 8 now it is 11) I got following error

Windows has triggered a breakpoint in BinarySearchTreeByList.exe.

This may be due to a corruption of the heap, and indicates a bug in >BinarySearchTreeByList.exe or any of the DLLs it has loaded.

The output window may have more diagnostic information

Following is complete code

#include "stdafx.h"
#include <stdio.h>
#include <tchar.h>
#include <list>
#include <iostream>

typedef struct node
{
    node* left;
    node* right;
    node* parent;
    int val;
};

using namespace std;

void insert_node(node** iterate, int newVal, node* newParent);
void traverse(node* iterate);
void del(node** iterate, int newVal, char direction);


void traverse(node* iterate)
{
    if(iterate != NULL)
    {
        traverse(iterate->left);
        printf("%d ",iterate->val);
        traverse(iterate->right);
    }
}


void del(node** iterate, int newVal, char direction)
{

    if((*iterate) == NULL)
        return;

    if((*iterate)->val == newVal)
    {
        if((*iterate)->left == NULL && (*iterate)->right == NULL)
        {
            if(direction == 't')
            {
                node* deleted = *iterate;
                *iterate = NULL;
                free(deleted);
            }

            if(direction == 'l')
            {
                node* deleted = (*iterate)->parent->left;
                (*iterate)->parent->left = NULL;
                free(deleted);
            }

            if(direction == 'r')
            {
                node* deleted = (*iterate)->parent->right;
                (*iterate)->parent->right = NULL;
                free(deleted);
            }

            return;
        }

        if((*iterate)->left == NULL)
        {
            if(direction == 't')
            {
                node* deleted = *iterate;
                *iterate = (*iterate)->right;
                (*iterate)->parent = NULL;
                free(deleted);
            }

            if(direction == 'l')
            {
                node* deleted = *iterate;
                (*iterate)->parent->left = (*iterate)->right;
                free(deleted);
            }

            if(direction == 'r')
            {
                node* deleted = *iterate;
                (*iterate)->parent->right = (*iterate)->right;
                free(deleted);
            }

            return;
        }

        if((*iterate)->right == NULL)
        {
            if(direction == 't')
            {
                node* deleted = *iterate;
                *iterate = (*iterate)->left;
                (*iterate)->parent = NULL;
                free(deleted);
            }

            if(direction == 'l')
            {
                node* deleted = *iterate;
                (*iterate)->parent->left = (*iterate)->left;
                free(deleted);
            }

            if(direction == 'r')
            {
                node* deleted = *iterate;
                (*iterate)->parent->right = (*iterate)->left;
                free(deleted);
            }

            return;
        }

        node* findmin = (*iterate)->right;

        int minVal = 0;

        while(findmin != NULL)
        {
            minVal = findmin->val;
            findmin = findmin->left;
        }

        (*iterate)->val = minVal;

        del(&((*iterate)->right), minVal, 'r');

        return;
    }

    if(newVal < (*iterate)->val)
        del(&((*iterate)->left) ,newVal, 'l');
    else
        del(&((*iterate)->right) ,newVal, 'r');

}


void insert_node(node** iterate, int newVal, node* newParent)
{
    if(*iterate == NULL)
    {
        node* newNode = (node*)malloc(sizeof(node));

        newNode->val = newVal;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->parent = newParent;

        *iterate = newNode;

        return;
    }

    if(newVal < (*iterate)->val)
        insert_node(&((*iterate)->left) , newVal, *iterate);
    else
        insert_node(&((*iterate)->right) , newVal, *iterate);
}

int main()
{
    node* iterate = NULL;

    insert_node(&iterate, 8, NULL);
    insert_node(&iterate, 15, NULL);
    insert_node(&iterate, 4, NULL);
    insert_node(&iterate, 2, NULL);
    insert_node(&iterate, 1, NULL);
    insert_node(&iterate, 3, NULL);
    insert_node(&iterate, 7, NULL);
    insert_node(&iterate, 6, NULL);
    insert_node(&iterate, 11, NULL);
    insert_node(&iterate, 22, NULL);
    insert_node(&iterate, 12, NULL);
    insert_node(&iterate, 13, NULL);    


    traverse(iterate);
    printf("\n\n");

    del(&iterate, 8, 't');
    del(&iterate, 22, 't');
    del(&iterate, 7, 't');
    del(&iterate, 11, 't');

    printf("\n\n");
    traverse(iterate);

    cin.clear();
    cin.ignore(255, '\n');
    cin.get(); 

}

Thank you for your help

Do you actually need to implement it? Could you use std::map or std::set instead? — juanchopanza
– juanchopanza, Commented Jan 14, 2014 at 7:37
Unrelated, the decl of your typedef struct node is not functional C++. You're declaring a typedef without a formal alias, i.e. it declares nothing. Lose the typedef if this is C++ (which apart from the cin usage at the bottom, it isn't) — WhozCraig
– WhozCraig, Commented Jan 14, 2014 at 7:42
@juanchopanza Actually this is a sort of requirement to implement it like this — Hassan
– Hassan, Commented Jan 14, 2014 at 7:46
probably would be better to tag it C and change cin to fgets() since you do not even use new/delete — AndersK
– AndersK, Commented Jan 14, 2014 at 7:52

Uri Y · Accepted Answer · 2014-01-14 09:15:16Z

1

Your problem is when you delete a node you set the child node pointer of the deleted parent to the deleted node's child, but you don't set the deleted parent's child pointer to the deleted node's child.

For instance:

    if(direction == 'l')
    {
        node* deleted = *iterate;
        (*iterate)->parent->left = (*iterate)->right;
        deleted->right->parent = deleted->parent;
        free(deleted);
    }

You were missing the line deleted->right->parent = deleted->parent;, I added it. There are a few more places in the code you should fix in the same manner.

answered Jan 14, 2014 at 9:15

Uri Y

8505 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

M Oehm · Accepted Answer · 2014-01-14 08:29:48Z

0

Your problem is that you don't update the parents when you delete a node with children. The parent field is only assigned when you insert a node, and hence you have a well-defined tree. You also set it in some cases, e.g. when there is only one child and the direction is 't'.

You break the tree when you start jiggling around nodes without updating the parents of the children of the deleted nodes in the 'l' and 'r' cases.

answered Jan 14, 2014 at 8:29

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

Collectives™ on Stack Overflow

C++ Binary search tree delete issue

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related