CODEWITHSUNDEEP
binary-search-tree
Samuele Colombo
Samuele Colombo

Reputation: 685

deleting multiple node in BST changes the resulting tree?

If I need to delete multiple nodes in BST are the resulting trees different altering deletion order? The normal left-right order will be preserved, but I'm not sure about the tree structure.

This is a "phisolophical" question and I need a dimostration of it or a counter-example.

Upvotes: 1

Views: 1466

Answers (2)

Behnam Gomar
Behnam Gomar

Reputation: 21

Deleting 1 and 2 in different order results in two different treesCounterexample: the order of deleting 1 and 2 results in different BSTs. Because when you want to delete 2 at first, you must find next element in its right subtree,that is, 3 and replace it with 2, but when you delete 1 at first and then you want to delete 2, now it has only one child and simply its child replace it, that is,4. So results in two different trees.

Upvotes: 2

Beta
Beta

Reputation: 99094

To prove that order of deletion has no effect on the final tree, it is necessary and sufficient to prove that any two deletion operations commute (that is, that they have the same effect if their order is reversed).

The effect of the deletion of a node is confined to that node and the subtree of which it is the root. So if two nodes are separate (i.e neither is under the other) then their deletions commute. So the only cases of interest have one node in the other's subtree.

Without loss of generality, suppose we use the rule that when we delete a node that has two children, we replace it with its successor. We'll call the higher one A and the lower one B. If B is in A's left subtree, then the deletions commute because the deletion of A has no effect on A's left subtree, and the deletion of B has no effect outside A's left subtree. So the only case of interest is when B is in A's right subtree.

When A is deleted, the effect on A's right subtree is the same as if A's successor had been deleted. Suppose B is not A's successor; we'll call A's successor C. The deletion of A consists of the deletion of C from the right subtree and the replacement of A with C (which commute), so if the deletions of B and C commute, then the deletion of A and B commute. By induction, if any pair of deletions do not commute, then the deletion of A and B where B is A's successor does not commute.

But the deletion of A and its successor do commute, by inspection. Q.E.D.

Upvotes: 1

Related Questions