Delete a Node from C++ Binary Search Tree (class not struct)

Question

I'm trying to manage a BST in C++ for my academic purpose.

I'm not having problems anywhere except for the DeleteNode function, also I chose to implement this data structure with a class and not with a struct.

The problem is, that I cant figure it out how to make properly work the delete function, often I got 0xDDDDDDDDD error my debugger say, sometimes I can delete the node, sometimes my program crash.

I think that's a possible problem of pointer, but I just can't figure it out where I'm doing wrong.

Here's my delete node function, the one I'm getting serious trouble about:

EDIT: The no-son delete case works perfectly, the one i'm getting mad about is the one-son-case delete.

 //function that delete a selected node
    void DeleteNode(TreeNode* root,int key) {
        /*we got three case here:*/


        //until we find the right node with value in the tree
        if (root->getValue() != key && root != nullptr) {
            if (root->getValue() > key) {
                DeleteNode(root->Left, key);
            }
            else if (root->getValue() < key) {
                DeleteNode(root->Right, key);
            }
        }
        else { //when we found the right node, then operate 
               /* THIS WORKS PERFECTLY! */

            //first case: our node got no right and left son
            if (!root->Left && !root->Right) {

                TreeNode* tmp = root->Father; 

                if (tmp->Left == root) { //if the son is a left son
                    tmp->Left = nullptr;
                    delete root;
                }
                else if (tmp->Right == root) { //if the son is a right son
                    tmp->Right = nullptr;
                    delete root;
                }

            }
            //second case: our node got a left but no right son
            /* THIS ONE DOESN'T WORK. */
            else if (!root->Right) { 
                TreeNode *tmp = root;
                root = root->Left; //new root is the left son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Left = root; //linking the son to the new father

                delete tmp;                     

                std::cout << "Erased!" << std::endl;
            }
            else if (!root->Left) {
                TreeNode *tmp = root;
                root = root->Right; //new root is the right son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Right = root; //linking the son to the new father

                delete tmp;

                std::cout << "Erased!" << std::endl;

            }
        }


        }

I tried a lot of combination, but the result are the same every time: it crashes on the first occurrence of the InOrder display function. (and when it does not, the function just delete the first nodes and then crash when i try to delete a new one.)

Here's a simple main where i'm trying to act the delete:

int main()
{

    TreeNode root;

    root.insertNode(&root,50);
    root.insertNode(&root,30);
    root.insertNode(&root,20);
    root.insertNode(&root,40);
    root.insertNode(&root,70);
    root.insertNode(&root,60);
    root.insertNode(&root,80);

    for (int i = 0; i < 5; i++) {
        int n;
        cin >> n;

        root.DeleteNode(&root, n);

        cout << "In-Order: "; root.inOrder(&root);
        cout << endl;
        cout << "Pre-Order: "; root.preOrder(&root);
        cout << endl;
        cout << "Post-Order: "; root.postOrder(&root);
        cout << endl;
    }

}

Here's my full BST code (except the delete one that i submitted before, just for being more complete in the understanding of my code)

    class TreeNode {
private:
    int value;
    TreeNode* Left;
    TreeNode* Right;
    TreeNode* Father;

public:

    //constructor
    TreeNode() {
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    TreeNode(int value) {
        this->value = value;
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    //functions
    int getValue() { return value; }
    void setValue(int value) { this->value = value; }


    //function to create a new node and insert a value into it
    TreeNode* insertNode(TreeNode* root, int value) {

        if (root->getValue() == NULL) {
            root->setValue(value);
            root->Father = nullptr;
        }

        else {
            if (value > root->getValue()) {
                if (root->Right) {
                    insertNode(root->Right, value);
                }
                else
                    root->Right = new TreeNode(value);
                    root->Right->Father = root;
            }
            else if (value < root->getValue()) {
                if (root->Left) {
                    insertNode(root->Left, value);
                }
                else
                    root->Left = new TreeNode(value);
                    root->Left->Father = root;
            }

        }
        return root;
    }

    //function to search a value into a BST
    TreeNode* SearchNode(TreeNode* root, int key) {

        if (root->getValue() == key) {
            return root;
        }
        else if (root->getValue() < key) {
            if (root->Right) {
                SearchNode(root->Right, key);
            }
            else return nullptr;
        }
        else if (root->getValue() > key) {
            if (root->Left) {
                SearchNode(root->Left, key);
            }
            else return nullptr;
        }
    }

    //function that return the height of the tree 
    int TreeHeigth(TreeNode* root) {

        int heigth;

        if (root == nullptr) {
            return 0;
        }
        else {
            return heigth = 1 + max(TreeHeigth(root->Left), TreeHeigth(root->Right));
        }
    }

    //function that returns the number of the nodes
    int CountTreeNode(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        else {
            return CountTreeNode(root->Left) + CountTreeNode(root->Right) + 1;
        }
    }

    //function that returns the minimum values into the tree
    TreeNode* MinimumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Left != nullptr) {
            root = root->Left;
        }

        return root;
    }

    //function that returns the maximum value into the tree  
    TreeNode* MaximumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Right != nullptr) {
            root = root->Right;
        }

        return root;
    }

    //function that returns a successor of a given nodeb
    TreeNode* SuccessorNode(TreeNode* node) {

        //first case: our node got a rigth subtree:
        if (node->Right != nullptr) {
            return MinimumNode(node->Right); 
        }

        //second case: our node doesnt got a right subtree: lets get 
        //upper in the tree until our node isn't a left child.

        TreeNode* Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Right) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

    }

    //function tht returns a predecessor of a given node
    TreeNode* PredecessorNode(TreeNode* node) {

        //first case: (inverse to successor) our node got a left subtree:
        if (node->Left != nullptr) {
            return MaximumNode(node->Left);
        }

        TreeNode* Ancestor;

            if (node->Father == nullptr)
                return nullptr;
            else 
                Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Left) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

        return Ancestor;
    }



    //function that prints information about nodes
    void InfoNode(TreeNode *root) {

        root != nullptr ? std::cout << "Nodo corrente: " << root->getValue() << std::endl
            : std::cout << "Nodo corrente: " << "NULL" << std::endl;

        root->Father != nullptr? std::cout << "Padre: " << root->Father->getValue() << std::endl
            : std::cout << "Padre: " << "NULL" << std::endl;

        root->Left != nullptr ? std::cout << "Figlio SX: " << root->Left->getValue() << std::endl
            : std::cout << "Figlio SX: " << "NULL" << std::endl;

        root->Right!= nullptr ? std::cout << "Figlio DX: " << (root->Right)->getValue() << std::endl
            : std::cout << "Figlio DX: " << "NULL" << std::endl;
    }

    //visits of a tree
    void preOrder(TreeNode* root) {
        if (root != nullptr) {
            std::cout << root->getValue() << " ";
            preOrder(root->Left);
            preOrder(root->Right);
        }
    }

    void inOrder(TreeNode* root) {
        if (root != nullptr) {
            inOrder(root->Left);
            std::cout << root->getValue() << " ";
            inOrder(root->Right);
        }

    }

    void postOrder(TreeNode *root) {
        if (root != nullptr) {
            postOrder(root->Left);
            postOrder(root->Right);
            std::cout << root->getValue() << " ";
        }
    }


    //max between 2 numbers
    int max(int a, int b) {
        return a > b ? a : b;
    }


    };

And there's the representation of the tree I'm trying to work on:

          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80

Where i'm doing it wrong?

Side note: there is no fundamental difference between a class and a struct. A struct simply has all members public by default, whereas a class has them private. — AVH
– AVH, Commented Nov 18, 2017 at 12:25
i also tried to set all the pointer to the father, left and right son public, but that ain't helped at all. — Asynchronousx
– Asynchronousx, Commented Nov 18, 2017 at 12:29
Another side node: this seems like code to delete a node from a binary tree, not a binary search tree (which needs nodes to be reordered after deletion of an internal node). — AVH
– AVH, Commented Nov 18, 2017 at 12:36
The answer would be a little too long to fit here, but for example take a look at Wikipedia on the Binary tree and Binary search tree pages. Basically when deleting a parent node one of the child nodes might need to take its place to keep it a proper binary search tree. — AVH
– AVH, Commented Nov 18, 2017 at 12:51

Bonje Fir · Accepted Answer · 2017-11-18 14:23:48Z

3

Look at this condition: root->getValue() != key && root != nullptr, This first calls getValue and after that checks root has legal value. swap them(root != nullptr && root->getValue() != key).

Finally I think you must change last line to tmp->Father->Left = root; to fix crash problem.

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father

PS: Also do this exchange for other side...

Note: This is true until root is left child of his father otherwise your code is true. Precisely you must check if root is left child if his father do tmp->Father->Left = root; else tmp->Father->Right = root;

Note: As you mentioned your code does not handle deletion of a node with two childern.

edited Nov 18, 2017 at 14:23

answered Nov 18, 2017 at 12:31

Bonje Fir

8388 silver badges27 bronze badges

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

9 Comments

Asynchronousx Over a year ago

thanks for the note, just adjusted that. But still crashing!

Bonje Fir Over a year ago

@Asynchronousx add this->value = NULL to your TreeNode constructor. At first root has garbage value not NULL.

Bonje Fir Over a year ago

@Asynchronousx If I delete 50 at first your code does not erase it!

Asynchronousx Over a year ago

yea, because 50 is the root, and i didn't make any code for erasing that!

Asynchronousx Over a year ago

YOU. ARE. THE. MAN. I'm trying to figure it out from days this problems, it gave me so much headache!!! Thank you very much for helping me with this Bonje, you're amazing! Can you also explain why when i'm on the right/left side i must update the opposite side with the root? THANK YOU!!

|

Ziezi · Accepted Answer · 2017-11-18 12:59:15Z

2

As there is already an answer giving you directions to correct the specific errors, I will try to focus on a suggestion that will help you avoid similar error all together:

Try separating your current function into two:

One that searches a node with specific key, for example: Node* search(int key) function that returns either a pointer to the node with wanted key or nullptr, or use the one that your already have.
One that deletes (and re-wires) the node passed as pointer and returns: next, previous, etc: Node* delete(Node* n).

Then call search, test against nulltpr, and if different, pass the returned pointer as an input argument in delete.

In this way you could easily detect on which phase is you problem: searching or deleting.

P.S.: figuring out re-wiring bugs is usually done through diagrams (boxes and arrows). Decide what you should do, separate it into steps and implement it.

edited Nov 18, 2017 at 12:59

answered Nov 18, 2017 at 12:39

Ziezi

6,5134 gold badges42 silver badges54 bronze badges

3 Comments

Asynchronousx Over a year ago

I debugged my program with visual studio, step by step, checking the pointers value and the value itself at every step. It seems that the search code lines works well, because it find my desired node, the one i'm gettin trouble with is the delete one, when my node got only one son.

Ziezi Over a year ago

@Asynchronousx Exactly, if the problem was related only to the delete part, it would have been much more easier to read and eventually detect, both by you and the rest of the people possibly reading your code.

Asynchronousx Over a year ago

But the problem is related only to the delete, because everything else works like a charm. The only part that is causing me a bunch of headache is the deleting the one-node-son case. (left or right either)

Phil1970 · Accepted Answer · 2017-11-18 14:05:30Z

Well, once one know that DEBUG version use sentinel value, it become much more trivial to find problems in code.

When and why will an OS initialise memory to 0xCD, 0xDD, etc. on malloc/free/new/delete?

0xDD is for dead memory. That is memory that has been already deleted. So when the debugger stop and it tells you that you have a bad pointer and the data contains a lot of 0xDD, you know the data has already been deleted. At that point, you should inspect class that contain the data to see if they are deleted too so you know which objects were deleted when the are embedded one inside another.

Be aware that sometime you might have some data that has been changed in part of the class if some operations use delete memory. Looking at memory pattern also help finding uninitialized memory and other similar problem.

Some other links:

In a case like yours, if you follow the good practice of writing unit tests, then it would even be more trivial to find the problem. In fact, if you do proper testing, then you will test all possible cases so you will know which cases fail and it would help you find where you might do something wrong.

Asynchronousx · Accepted Answer · 2017-11-18 17:32:23Z

I would like to add something to the answer of @Bonje Fir. Sure it is a correct answer, but partially: I'll explain why.

He suggested to swap the last piece of code i wrote:

Case: we're in the right subtree, and we would like to erase 70 (because we don't have anymore the leaf node 60):

          50
       /     \
      30      70
     /  \       \
   20   40      80

now, with the code that @Bonje Fir suggested us, we would got a problem here:

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Left (instead of Right)  = root; //linking the son to the new father

Because the code is saying, that once you updated the new root with his son, link the father of the previous root (that we saved in a tmp variable) with his left son. Then we would assist to something like this:

and that's inconsistent.

Now take a look on the other side, with the same code and without leaf node 20:

      50
   /      \
  30       70
    \     /  \
    40   60  80

the code fit here, because we're in the right subtree. so once update 30 with 40 (root = root -> right) the situation would be this:

      50
   x      \
  40       70
          /  \
         60  80

then the piece of code @Bonje Fir wrote us, would fit perfectly:

tmp->Father->Left = root

because for sure, we're assigning 40 to the left son of the father of the original root. (because we're in the left subtree.)

      50
   /      \
  40       70
          /  \
         60  80

So i made a little change to correct this logic problem, and make it work both in the right and left subtree.

else if (!root->Left) {
            TreeNode *tmp = root;
            root = tmp->Right;
            root->Father = tmp->Father; //linking the father to the new son

            //we need also to connect the son with the father, but first
            //we need to know in which subtree we're in.

            if (root->Father->Right == tmp) //if we're in the right subtree
                tmp->Father->Right = root;
            else                            ////if we're in the left subtree
                tmp->Father->Left = root;

            delete tmp;

            std::cout << "Erased!" << std::endl;                
        }

i took advantage of the fact i didnt erase my root, once assigned the new one, so the father of the root still points to the old root.

(same speech for the opposite case.)

Collectives™ on Stack Overflow

Delete a Node from C++ Binary Search Tree (class not struct)

4 Answers 4

9 Comments

3 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

9 Comments

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related