Betrachten Sie die Löschprozedur für eine BST, wenn der zu löschende Knoten zwei untergeordnete Knoten hat. Nehmen wir an, ich ersetze es immer durch den Knoten, der den Mindestschlüssel in seinem rechten Teilbaum enthält.

Die Frage ist: Ist dieses Verfahren kommutativ? Das heißt, das Löschen von x und dann von y hat das gleiche Ergebnis wie das Löschen von erstem y und dann von x?

Ich denke, die Antwort ist nein, aber ich kann weder ein Gegenbeispiel finden noch eine gültige Begründung finden.

BEARBEITEN

Vielleicht muss ich klarer sein.

Bedenke dietransplant(node x, node y) -Prozedur: Ersetzt x durch y (und seinen Teilbaum). Wenn ich also einen Knoten löschen möchte (z. B. x), der zwei Kinder hat, ersetze ich ihn durch den Knoten, der den Mindestschlüssel in seinem rechten Teilbaum enthält:

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)

Die Frage war, wie man beweisen kann, dass das obige Verfahren nicht kommutativ ist.