Binary Search Trees-Deletion

1
votes

In the case of Binary Search Trees why cannot we simply put the predecessor in place of the successor of a node in deletion case where a node is having two children?

2
algorithmtreebinary-search-tree
Based on Wikipedia and my understanding of what you're asking, that's exactly what we do. Can you clarify how you think deletion works / how exactly you mean it should work (images always help)? – Bernhard Barker
@silentseeker Please consider accepting an answer. – Nikunj Banka

2 Answers

0
votes

why cannot we simply put the predecessor in place of the successor of a node in deletion case where a node is having two children?

We can put both and it is not necessary to replace the deleted node with the inorder successor. This is because in either case, the general contract of a BST is maintained.

Case1. Replace the deleted node with the inorder successor. This is done by finding the leftmost node in the deleted node's right subtree.

Case2. Replace the deleted node with the inorder predecessor. This is done by finding the rightmost node in the deleted node's left subtree.

Note that both these cases will keep all the elements in the left subtree smaller and all elements in right subtree greater than the element that we have brought into the position of the deleted node.

0
votes

We'd like to delete such a node with minimum amount of work and disruption to the structure of the tree.

Suppose we want to delete the node containing 6 from the following tree:

enter image description here

The standard solution is based on this idea: we leave the node containing 6 exactly where it is, but we get rid of the value 6 and find another value to store in the 6 node. This value is taken from a node below the 6s node, and it is that node that is actually removed from the tree.

enter image description here

Now, what value can we move into the vacated node and have a binary search tree? Well, here's how to figure it out. If we choose value X, then:

  1. everything in the left subtree must be smaller than X.
  2. everything in the right subtree must be bigger than X.

Let's suppose we're going to get X from the left subtree. (2) is guaranteed because everything in the left subtree is smaller than everything in the right subtree. What about (1)? If X is coming from the left subtree, (1) says that there is a unique choice for X - we must choose X to be the largest value in the left subtree. In our example, 3 is the largest value in the left subtree. So if we put 3 in the vacated node and delete it from its current position we will have a BST with 6 deleted.

The result is :

enter image description here