C++ remove node binary search tree

Question

I am trying to figure out how to remove a node from a binary search tree, I understand that it is different for each node whether it is a leaf, has one child or two children. So as of now my function is nothing more than:

bool BinSTree::remove_root(treeNode*& node) {
   if(node -> left == NULL && node -> right == NULL) {


   }
   elseif(node -> left != NULL && node -> right != NULL) {


   }  
   else {

   }                           

}

I am having a very hard time trying to comprehend the logic, for instance I know for all of them I need to be able to find the parent node to the node being deleted, which is where I am left clueless and any help would be much appreciated!

Answer 1

This sounds like homework. You might find this article on binary tree rotation to be helpful. In addition to give you some hints on how to handle some interesting cases, that article will also show you how you might diagram the problem out for yourself.

Deleting from a tree is an interesting case, and I remember puzzling over it when I wrote my own AVL tree implementation in C in the late 80s.

Answer 2

To start with, your function should have a parameter for the parent, too (unless your tree has pointers to parents, which it sounds like it doesn't).

With that change, it should be easier for you to figure the rest out. But how you call that function becomes important.

Note: I'm assuming this is homework, so I don't want to provide a comprehensive answer.

Also, for the logic of what to do with the nodes after one is removed (how to relink them), try drawing some diagrams.

Answer 3

This wiki page on binary search tree might help.

Answer 4

In addition to the other answers (and assuming this is homework, the point being to learn), you may find Niklaus Wirth's "Algorithms + Data Structures = Programs" very enlightening, both in general and for your particular problem.

It's a classic little book, a gem.

Hopefully available at your nearest (university?) library?

Cheers & hth.,

Answer 5

When you delete a node,
- If it's a leaf, you're done.
- If it has one child, promote the child and then delete the child from its subtree (by calling yourself).
- If it has two children, pick which one to promote and then delete that child from its subtree (by calling yourself).

Sometimes which of two children you pick depends on factors like
- the root of a subtree is the least of all the nodes in the subtree
- the root of a subtree is the most of all the nodes in the subtree
- some coloring or other side-condition must be conserved

This should get you off high-center.