Remove Parent from AVL Tree

Question

I've been stuck on this part of my coding assignment dealing with AVL trees. We are supposed to remove members from the AVL tree. I've been able to deal with all the other cases of removing leafs from the tree. My problem is what to do when removing the head leaf (or parent?) of the tree.

To keep it simple, I am trying to remove B from the tree. In the struct of my class, I have access to the parent and the left and right child.

   B
  / \
 A   C

I have a method that computes the predecessor, which is A in this case. Node is the node is to be removed (B) From there, I am trying this code, but keep getting segfaults. This follows the general code which I used to remove other leafs in the tree.

successor->right = node->right;
node->right->parent = successor;
successor->parent = NULL;
node = NULL;
delete node;

it's because of your node = NULL. You can't delete a NULL. swap them — WindowsMaker
The segmentation fault was coming from another snippet of my code. I solved the problem now. — dclark
@zaftcoAgeiha Wrong. delete NULL; will do nothing, because the default deleter will contain a check for NULL. — Anthony

Anthony Anthony · Accepted Answer · 2013-12-04T00:22:43

To begin with, the following two lines don't make much sense in the order you've written them:

node = NULL;
delete node;

Deleting NULL is a nothing operation. You probably intended to switch those lines around. As for your segfault, I don't see anything in the code you posted which would cause a crash; it's probably occurring elsewhere in the code.

For AVL Deletion there are a number of useful tutorials. The Wikipedia page on AVL Trees contains a step-by-step on how to process a delete. I also enjoyed reading the tutorial on Eternally Confuzzled. There are heaps more, which Google will turn up. Also, consult your text if you have one.

Remove Parent from AVL Tree

1 Answers