What's wrong with my RemoveNode function (BST)?

[gedamial]

Hi.

This is the RemoveNode function:

// keyNode is a pointer to the Node to delete
void RemoveNodePrivate(Node* keyNode)
{
	// CASE 1 = No children
	if (!keyNode->left && !keyNode->right)
	{
		delete keyNode;
		keyNode = nullptr;
	}

	// CASE 2 = One child
	else if (keyNode->left == nullptr)
	{
                // tmp is a copy of keyNode (copy constructor)
		Node* tmp{ keyNode };
		keyNode = keyNode->right;
		delete tmp;
	}

	else if (keyNode->right == nullptr)
	{
		Node* tmp{ keyNode };
		keyNode = keyNode->left;
		delete tmp;
	}

	// CASE 3 = Two children
	else
	{
                // SmallestPrivate() returns the smallest value in a tree
		Node* smallest = SmallestPrivate(keyNode->right);

		keyNode->value = smallest->value;

		RemoveNodePrivate(smallest);
	}
}

Now, I have this tree:

	 [5]
    [3]      [7]
 [1]	  [6]   [8]

When I call the function all is ok... but when I do something with the "brand new tree" (like printing all of its nodes) I issue an Access violation reading location

I should end up with

	 [5]
    [3]      [8]
 [1]	  [6]   

Thanks to the powerful Visual Studio debugger, it turned out that the right-pointer of 8 is undefined.

So i'm in a situation like:

	 [5]
    [3]      [8]
 [1]	  [6]   [???]  // <--- mess! 

How can I fix this?

*Screenshot of the Visual Studio debugger : http://i.imgur.com/zFtnVoY.jpg

[ne555]

keyNode = /*...*/;
statement has no effect.

`keyNode' holds a copy of the pointer, any changes made to it would be local to the function.
To clarify, you make a call RemoveNodePrivate(smallest); `smallest' would not be modified

[gedamial]

Even by changing the parameter from Node* keyNode to Node*& keyNode the problem persists

[cire]

On line 31 you create a local copy of a pointer-to-Node. It is this copy that is fed to RemoveNodePrivate, so changing the parameter to pass by reference will be ineffective.

[gedamial]

But where does the real issue come out from?

One thought of mine is that parent's left-and-right pointers aren't set to nullptr after the extraction of the node to remove.

I don't know, any tip?

[cire]

But where does the real issue come out from?

It's already been pointed out to you.

One thought of mine is that parent's left-and-right pointers aren't set to nullptr after the extraction of the node to remove.

As pointed out above, they are not.

I don't know, any tip?

Don't modify copies of objects and expect originals to be affected.

If: void RemoveNodePrivate(Node* keyNode) is changed to take a reference to a pointer, and in Node* smallest = SmallestPrivate(keyNode->right); smallest is made to be a reference, and SmallestPrivate returns a reference to a pointer that is part of the tree and not a local copy of one, I think you'll have fixed the problem.

Often, a problem doesn't stem from one mistake, but many, which is why fixing one bug sometimes reveals another.

[gedamial]

Unfortunately, that didn't solve the problem.

To make things easier for you guys, I uploaded a Simulation on this link: http://coliru.stacked-crooked.com/a/821a98c0428aa00d

I've got the headache

[cire]

Recall that I said:

and SmallestPrivate returns a reference to a pointer that is part of the tree and not a local copy of one

Seeing:

		Node*& SmallestPrivate(Node* current) const
		{
			if (current->left)
				return SmallestPrivate(current->left);
			else
				return current;
		}

current is a local copy, and if you return a reference to current you have a dangling reference (and undefined behavior.)

[gedamial]

Alright, I also fixed that one and all seems to work.
By the way, I want to understand better what was going on, and figure out what was the thing that didn't make my function work as expected.

When the RemoveNodePrivate() was called, keyNode was just a pointer to the node to be deleted.

Let's pretend we have the following tree:

	 [5]
    [3]      [7]
 [1]	  [6]   [8]

And let's say we pass in the pointer to the node 7.

Since 7 has two children, the CASE 3 is chosen.

In that if-statement block, the pointer called 'smallest' will point to the node 8.

After that, I change the value-pointed by keyNode from 7 to 8.

So far, so good the changes have effect, now our tree looks like:

	 [5]
    [3]      [8]
 [1]	  [6]   [8]

Now, we need to delete the "old" 8 node were we have stolen the value from

Another recursive call to RemoveNodePrivate() is launched, but this time with a pointer to the node 'smallest' (which points to the "old" 8).

Hence, keyNode this time points to the old 8.

Since the old 8 has no children, the first case is chosen.

The node gets freed from the Heap, so the node NO LONGER EXISTS.
FINE! IT'S EXACTLY WHAT WE WANTED, ISN'T IT?


Finally, the keyNode pointer is set to nullptr, BUT THIS IS USELESS SINCE keyNode IS A COPY.

So, at the end of the day, the only thing that was wrong with the old code was to set a local pointer to null.

AND HERE'S THE QUESTION:

How does setting a local pointer to nullptr (instead of the original one) make the difference?

Mentioning myself

The node gets freed from the Heap, so the node NO LONGER EXISTS.
FINE! IT'S EXACTLY WHAT WE WANTED, ISN'T IT?

So we did it! We deleted the node! What's the purpose of setting the original pointer to null?

[cire]

How does setting a local pointer to nullptr (instead of the original one) make the difference? We deleted the node! What's the purpose of setting the original pointer to null?

The goal is not just to delete the node. The goal is to delete the node and update the data structure so that it no longer references an invalid object. If we only do the first of those the data structure is compromised, as we have seen from your code.

[gedamial]

. The goal is to delete the node and update the data structure so that it no longer references an invalid object

You said that.

Now listen to me carefully. Here is the Simulation so you understand better: http://coliru.stacked-crooked.com/a/c481b0bf71afc3df

It works as expected but there's still one thing I don't get.

Unfortunately I can't upload screenshots on the forum so I'll give you them as links.

Here is my tree: http://prntscr.com/bu1km5 (ignore the magenta arrow)
The red arrows that you see are the famous real pointers that we are going to modify. Right?

If you look at the Remove() function, I call it the first time passing 7.

All the Remove() function does is searching for a node with a given value (in this case, 7) and returns a brand new pointer to that node. Let's call this pointer "finder"

Screenshot: http://prntscr.com/bu1mmm

Again, the red arrows are the real pointers. The green one is the pointer returned by the Search() function which points to our node 7 which we want to be deleted.

Here's the point

In the Remove() function, we call the RemoveNodePrivate() function passing a reference to the GREEN pointer.

So, when we set keyNode to nullptr, we are setting the GREEN pointer to nullptr.

We are not even touching the red arrows (the real pointers!)

**
This problem is hidden because the node [7] has 2 children.

If I delete, say, the node [2] which is a leaf... access violation reading location.

So even the search function should return a pointer by reference, shouldn't it?

[cire]

So even the search function should return a pointer by reference, shouldn't it?

Yes. Any function which returns an object should do so by reference if you want to use the returned value to modify the original, whether that object is a pointer or some other construct.