CODEWITHSUNDEEP
c++binary-search-tree
SteppingHat
SteppingHat

Reputation: 1362

BST delete doesn't actually delete

I've got this delete function that takes a node in a BST as a parameter to delete it. It checks for three cases before doing anything:

The first two cases work, but not the last case with two children. The code for just that case is as follows

AccNode* smallest = pointer->getRight();
bool foundSmallest = false;

// Find the smallest node in the right branch
while (foundSmallest == false) {
    if (smallest->getLeft() == NULL && smallest->getRight() == NULL) {
        foundSmallest = true;
    } else {
        if (smallest->getLeft() == NULL && smallest->getRight() != NULL) {
            smallest = smallest->getRight();
        } else {
            smallest = smallest->getLeft();
        }
    }
}

// Replace the node we want to delete with the data in
// smallest node we found and delete smallest node in that tree
pointer->setData(smallest->getData());
delete smallest;

To further debug, Xcode has some pretty cool tools that let you visualise the tree, and I discovered something pretty interesting. Before we get to the line delete smallest; the smallest node in the tree looks like this

Smallest node pre deletion

After we delete the line it looks like this

Smallest node post deletion

So what's going on here? Am I messing up something with the way I'm using the pointers?

Edit: I just realised something. In the image on the tree post deletion, in a folded up section the right node is no longer NULL and has value now. I opened it up and it is the entire right branch from the node we wanted to delete from the beginning (so the right branch of the original pointer). So I feel like I'm definitely doing something wrong with the pointers now. Any clue as to what it is?

Upvotes: 2

Views: 306

Answers (3)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145279

You forgot to null the pointer (in the parent node of smallest) pointing to smallest. This leaves that pointer as a dangling pointer, a pointer pointing to already deallocated memory. The debugger shows the arbitrary content for such memory, in many cases just what was there earlier.

You need to keep track of the parent node.

Also, the current logic branches right when it can't branch left and branching right is possible. But that leads to a node with larger value, including all its children. So this logic is ungood.

An alternative to copying data, deleting and nulling pointer in parent, is to rearrange the tree (move the smallest node to the place where you have the node you really want to delete) and then just delete the node you really want to delete. This has the two advantages of generally doing less work, and keeping other pointers to the nodes valid.

Niklaus Wirth's book “Algorithms + Data Structures = Programs” is little gem for this. I read its original edition based on Pascal. I believe there is a free electronic edition now based on Oberon.

General advice: in modern C++ it can be a good idea to use nullptr instead of the macro NULL. It's more type safe in general.

Also, instead of

foundSmallest == false

just (1)write

not foundSmallest

or

!foundSmallest

(1) With at least one not entirely standard-compliant compilers you have to include the <iso646.h> header in order to use the reserved words and, or and not as operators. But, this can be done via forced include directive in the command line. It doesn't need to show in the code.

Upvotes: 2

Zuo Zeng
Zuo Zeng

Reputation: 1

  1. You forgot to null the pointer as Cheers answered.
  2. I don't think your algorithm of finding smallest node is correct. To find the smallest node of a BST, you should NOT go right as any node of the right sub-tree is no less than the node itself. The correct way should be keep going left until it has no left sub-tree which means no node is less than that one.

Upvotes: 0

GraphicsMuncher
GraphicsMuncher

Reputation: 4641

After you've deleted the memory held by smallest, it isn't valid to read anymore. It's just garbage data. It may make sense, it may not, but there's no guarantee of anything.

Algorithmically, as Cheers has pointed out, you've forgotten to remove the smallest node as a child of its parent. In other words, its original part is still pointing to it. You can fix this by keeping track of a parent node.

Upvotes: 0

Related Questions