Рассмотрим процедуру удаления на BST, когда у удаляемого узла есть два дочерних элемента. Допустим, я всегда заменяю его на узел, содержащий минимальный ключ в своем правом поддереве.

Вопрос в том, является ли эта процедура коммутативной? То есть удаление x, а затем y имеет тот же результат, что и удаление сначала y, а затем x?

Я думаю, что ответ - нет, но я не могу найти контрпример или найти какие-либо веские аргументы.

РЕДАКТИРОВАТЬ:

Может быть, я должен быть яснее.

Рассмотримtransplant(node x, node y) процедура: заменить х на у (и его поддерево). Итак, если я хочу удалить узел (скажем, x), у которого есть два потомка, я заменяю его узлом, содержащим минимальный ключ в его правом поддереве:

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)

Вопрос был в том, как доказать описанную выше процедуру не коммутативно.