Considere el procedimiento de eliminación en un BST, cuando el nodo a eliminar tiene dos hijos. Digamos que siempre lo reemplazo con el nodo que contiene la clave mínima en su subárbol derecho.

La pregunta es: ¿es este procedimiento conmutativo? Es decir, eliminar x y luego y tiene el mismo resultado que eliminar primero y luego x.

Creo que la respuesta es no, pero no puedo encontrar un contraejemplo, ni encontrar ningún razonamiento válido.

EDITAR:

Tal vez tengo que ser más claro.

Considera eltransplant(node x, node y) procedimiento: reemplaza x con y (y su subárbol). Entonces, si quiero eliminar un nodo (digamos x) que tiene dos hijos, lo reemplazo con el nodo que contiene la clave mínima en su subárbol derecho:

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)

La pregunta era cómo demostrar que el procedimiento anterior no es conmutativo.