Binary search tree deletion operation

Question

I have a book that explains the over all binary search tree in a very bad way i have so far been able to close study my book and get an idea of the binary search tree however i find the explanation for the Binary search tree's operation Delete

I do understand the two first simple operations:

• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.

However the one with two children is really difficult for me to understand, i have already read on wiki and other sites to try and find a solution but i find the explanations to be kinda encrypted.

I was hoping that someone here could give me a more details or explain it in to me another way ?

Answer 1

Can we say in short:

To delete a node N with 2 children in a binary tree (like the aforementioned ones), either replace this N with the largest node of the left sub-tree or with the smallest node of the right sub-tree

Answer 2

If you understand the first two rules, then deleting a node with two children is not tough to understand.

A very simple way to think of it is, go to the in-order successor (or predecessor) of the node to be deleted. Then apply the first two rules and the previous rule again.

While programming, having a fully functional successor (predecessor) function makes coding deletion a lot simpler.

For this tree :

To delete 8 :

• Go to 9 (7)

• Replace 9 with 10

• Replace 8 with 9 (7)

To delete 12 :

• Go to 14 (10)

• (Replace 9 with 10)

• Replace 12 with 14 (10)

Answer 3

When the node has two children you have to:

1. Find the minimum.
2. Replace the key of the node to be deleted by the minimum element.

look at this picture: we want to delete element 4

• 4 has 2 children.

• find min right sub-tree.

• 5 found.

• So, 4 is replaced by 5, and 4 is deleted.

Hope that is what you are looking for!!