Procedure to delete a binary search tree

Question

Consider the deletion procedure in BST when the node to delete has two children. Say I always replace it with node, keeping the minimum key in my right subtree.

The question arises: is this procedure commutative? That is, deleting x and then y has the same result as deleting the first y and then x?

I think the answer is no, but I can’t find a counterexample and I don’t know any reasonable arguments.

EDIT:

Maybe I should be more clear.

Consider the transplant(node x, node y) procedure transplant(node x, node y) : it will replace x with y (and its subtree). So, if I want to remove a node (say x) that has two children, I will replace it with node, keeping the minimum key in its right subtree:

 y = minimum(x.right) transplant(y, y.right) // extracts the minimum (it doesn't have left child) y.right = x.right y.left = x.left transplant(x,y) 

The question is how to prove that the above procedure is not commutative.

Answer 1

Removing (generally speaking) is not commutative. Here is a counterexample:

  4 / \ 3 7 / 6 

What if we remove 4 and then 3?

When we remove 4, we get 6 as the new root:

  6 / \ 3 7 

Removing 3 does not change the tree, but gives us the following:

  6 \ 7 

What if we remove 3 and then 4?

When we delete 3, the tree does not change:

  4 \ 7 / 6 

However, when we now remove 4, the new root becomes 7:

  7 / 6 

The two resulting trees do not match, so deletion is not commutative.

UPDATE

I have not read the limitations that this is when you always delete a node with two children. My solution for the general case. I will update it if / when I find a counter example.

OTHER UPDATE

I have no concrete evidence, but I'm going to be afraid:

In general, you handle deletions differently depending on whether you have two children, one child, or no children. In the above counterprocess example, I first delete the node with two children, and then the node with one child. After that I will remove the node without children, and then another node with one child.

In the special case, only to remove nodes with two children, you should consider the case when both nodes are in the same subtree (since it doesn’t matter if they are in different subtrees, you can make sure that the general structure does not change depending on the order removal). What you really need to prove matters: Does the order of deleting nodes in the same subtree, where each node has two children, have?

Consider two nodes A and B, where A is the ancestor of B. Then you can further clarify the question:

Is a deletion commutative when you consider removing two nodes from a binary search tree that are related between ancestors and descendants of each other (this means that they are in the same subtree)?

When you delete the node (let them say A), you go over the right subtree to find the minimum element. This node will be a leaf of a node and can never be equal to B (since B has two children and cannot be a leaf of a node). Then you replace the value of A with the value of this sheet - node. This means that the only structural change to the tree is to replace the value of A with the value of the leaf node and the loss of the leaf node.

The same process is used for B. That is, you replace the node value and replace the leaf-node. In the general case, when you delete a node with two children, the only structural change is to change the value of the node that you are deleting, and delete the leaf node, whose value you are using as a replacement.

So, the question is being clarified:

Can you guarantee that you will always have a node replacement regardless of the order of removal (when you always delete a node with two children)?

The answer (I think) is yes. What for? Here are a few notes:

• Suppose you first remove the descendant node and the ancestor node. The subtree that was changed when you deleted the node descendant is not in the left subtree of the child child of the node ancestor. This means that this subtree remains unaffected. What this also means, regardless of the order of deletion, is changing two different subtrees, and therefore the operation is commutative.
• Again, let's say you delete the descendant node first and the ancestor node second. The subtree that was changed when you deleted the descendant node is in the left subtree of the child child of the node ancestor. But even here there is no overlap. The reason is that first you delete the descendant node, you look at the left subtree of the child child of the child node. When you remove the ancestor of a node, you will never go down from this subtree, since you will always go left after you enter the right child tree of the predecessor node. So, again, no matter what you delete first, you change the different subtrees, and therefore it seems that the order doesn't matter.
• Another thing is if you first remove the ancestor node, and you find that the minimum node is a descendant of the descendant node. This means that the child of the node will be in one child, and the removal of one child is trivial. Now, consider the case where in this scenario you first deleted the node descendant. Then you replace the value of the descendant node with its right child and then delete the correct child. Then, when you delete the ancestor of the node, you get the same minimum node (the old remote node is the left child, which is also the replaced node left child). In any case, you get the same structure.

This is not a rigorous proof; These are just some of the comments I made. By all means, feel free to breathe!

Answer 2

It seems to me that the counterexample shown in Vivin's answer is the only case of non-commutativity and that it is really eliminated by the restriction that only nodes with two children are deleted.

But it can also be eliminated if we discard what seems to be one of Vivin’s premises, that is, we should cross the right subtree as little as possible in order to find any acceptable successor. If instead we always support the smallest node in the right subtree as a successor, no matter how far it is located, then even if we relax the restriction on deleting nodes with fewer two children, the result of Vivin

  7/6

never achieved if we start with

  4 / \ 3 7/6

Instead, we will first remove 3 (without a successor) and then remove 4 (with 6 as a successor), giving

  6 \ 7

which is the same as if the deletion order was canceled.

The deletion will then be commutative, and I think that it is always commutative, given the assumption I named (the successor is always the smallest node in the right subtree of the deleted node).

I have no formal evidence, just a listing of cases:

• If two nodes to be deleted are in different subtrees, then deleting one of them does not affect the other. Only when they are on the same path can the removal order affect the result.

  Thus, any effect on commutativity can occur only when both the parents of the node and one of its descendants are deleted. Now, how do their vertical relationships affect commutativity?

• A descendant in the left subtree of the ancestor. . This situation will not affect commutativity, because the successor comes from the right subtree and cannot affect the left subtree at all.

• A descendant in the right subtree of the ancestor. If the successor-ancestor is always the smallest node in the right subtree, then the deletion order cannot change the choice of the successor, there is no question of which descendant is deleted before or after the ancestor. Even if the successor of the ancestor turns out to be a descendant of the node, which must also be deleted, this descendant is also replaced by the next largest node, and this descendant cannot have the remaining remaining subtree for the solution. Thus, deleting the ancestor and any descendant of the right subtree will always be commutative.

Answer 3

I will answer here on the second update of Vivin.

I think this is a good rework of the question:

Is deletion commutative when you are considering removing two nodes from a binary search tree that has a descendant ancestor related to each other (which would mean that they are in the same subtree)?

but this bold sentence below is incorrect:

When you delete the node (let them say A), you go through the right subtree and find the minimum element. This node will be a leaf node and can never be equal to B

since the smallest element in the right subtree on the right can have the right child element. So this is not a leaf. Let me name the minimum element in the right subtree of successor(A) . Now it’s true that B cannot be successor(A) , but can be in its right subtree. So this is a mess.

I am trying to generalize.

Hypotheses

• A and B have two children each.
• A and B are in the same subtree.

Other things we can deduce from the hypothesis:

• B is not successor(A) nor A is successor(B) .

Now, given this, I think there are 4 different cases (as usual, let A be the ancestor of B):

• B is in the left subtree
• B is the ancestor of successor(A)
• successor(A) is the ancestor of B
• B and successor (A) have no relationship. (they are in different subtrees of A)

I think (but, of course, I can’t prove it) that cases 1, 2 and 4 do not matter. Thus, only if successor(A) is the ancestor of the removal procedure B cannot be commutative. Or is it possible?

I miss the ball :)

Sincerely.

Answer 4

I think there are two equally viable ways to remove a node when it has 2 children:
SKIP TO CASE 4 ...

Case 1: delete 3 (Leaf node)
2 3
/ \ → / \
1 3 1

Case 2: delete 2 (left child node)
2 3
/ \ → / \
1 3 1

Case 3: delete 2 (right child node)
2 2
/ \ → / \
1 3 3

______________________________________________________________________
Case 4: delete 2 (left and right child nodes)
2 2 3
/ \ \
1 3 1 3
GENERAL WORK and have different resulting trees :) ______________________________________________________________________
As the algorithm is explained here: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html Deleting a node with 2 children nodes: 1) Replace the (to-delete) node with its in-order predecessor or in-order successor 2) Then delete the in-order predecessor or in-order successor