Search code examples
binary-search-tree

Deletion operation in Binary Search Tree: successor or predecessor

Delete operation is the most complex operation in Binary Search Tree, since it needs to consider several possibilities:

  • The deleted node is leaf node
  • The deleted node has only one child
  • The deleted node has both left and right child

The first two cases are easy. But for the second one, I read many books or documents, the solution is: find the min value in the right subtree and replace it with the deleted node. And then delete it from right subtree.

I can fully understand this solution.

In fact, generally, the node with the min value in the right subtree is called Successor of the node. So the above solution is replace the deleted node with its successor's value. And delete the successor node from the subtree.

On the other hand, predecessor of each node is the node with max value in the left subtree.

I think, replace the deleted node with its predecessor should also work.

For instance, the example used in the book of "Data structure and algorithm analysis in C".

enter image description here

If we want to delete node "2". Then we replace it with "3" which is "2" 's successor.

I think, replace "2" with "1" which is "2" 's predecessor can also work. Right? But the books didn't talk about it even a bit.

So is there any convention here? And If after one deletion operation, there are two results both correct. How to keep consistent?

Edit:

Update something based on new learning about this issue. In fact, the book "data structure and algorithm analysis in c" discussed the issue. In summary, it goes as follows:

  • First, both methods (based on successor or predecessor)should work.
  • If repeat O(n^2) insert/delete pairs on the tree. And all the deletion operation is based on successor. Then the tree will become unbalanced. Because the algorithm makes the left subtrees deeper than the right. The idea can be illustrated with the following two images:

enter image description here

enter image description here

Then it introduces to the concept of balanced search tree, such as AVL tree.

Solution

  • I can tell for the theory, to me your argument seems correct, that one can take either the predecessor or the successor.

    Now in practice, I would think that the best decision would be to keep the tree balanced, and switch between the two options depending on which makes the depth the lowest.