Ich versuche, diese Aussage zu widerlegen, dass für jeweils zwei Knoten v und w in einem binären Suchbaum, wenn Sie v löschen und dann w wird das gleiche wie das Löschen von w und dann v.Wie kann ich diese binäre Suchbaumaussage beweisen oder widerlegen?
Ich bin auf der Suche nach einem Gegenbeispiel hoffe ich, dass mir jemand dabei helfen kann.
Vielen Dank im Voraus
Die Eigenschaft von BST ist, dass eine Ordnungsbeziehung zwischen jedem Knoten und seinen Kindern da ist. Daher sollte unabhängig von der Reihenfolge, in der die Löschung durchgeführt wird, die Beziehung zwischen den Knoten intakt bleiben.
Eine einfache Möglichkeit, auf in Inorder Form dies druckt die Elemente des Baumes zu beweisen:
1.) Löschen x, dann y, und drucken Sie alle Elemente in Inorder Form
2.) löschen y, dann x und drucken alle Elemente in inorder Form
Eine der Eigenschaften von inorder Ausdruck ist, dass es immer die BST-Werte im sortiert gedruckt werden. Wenn also sowohl (1) als auch (2) sortiert sind und in der gleichen Reihenfolge, haben wir bewiesen, dass die Löschung von x gefolgt von y der Löschung von y gefolgt von x entspricht, da die BST-Knotenbeziehung intakt bleibt .
Die Inorder-Traversals sind identisch nicht beweisen, dass die Bäume die gleiche Form haben. Die erste Antwort auf diese Frage, http://stackoverflow.com/questions/2990486/deletion-procedure-for-a- binary-search-tree, zeigt ein Beispiel, in dem die Änderung der Löschreihenfolge zu verschiedenen Bäumen führt. –
Mögliches Duplikat von [Löschprozedur für einen binären Suchbaum] (http://stackoverflow.com/questions/2990486/deletion-procedure-for-a-binary-search-tree) –