Binary search tree deletion operation

2
votes

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 ?

3
data-structuresbinary-treebinary-search-tree
Does this help? stackoverflow.com/a/13755350/1288408 – Modus Tollens
why is there a java tag? – Manish Mulani
@ManishMulani Studying Java however i can see that this doesnt refer to java speceficly – Marc Rasmussen
@KatjaChristiansen Yeah it helps however i am really confused about the in-order princip on wiki it says it starts with the left subtree but this guy tell me to take the node from the right subtree= – Marc Rasmussen
Try googling and then you can put some code if you don't understand it – TechSpellBound

3 Answers

1
votes

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

enter image description here

  • 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!!

2
votes

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 :

enter image description here

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)

2
votes

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