Musterlösung April 2013 Aufgabe 6

[29917180]

Hallo,

Ich glaube, einen Fehler in der Musterlösung der Klausur vom April 2013 bei Aufgabe 6 gefunden zu haben. Soweit ich die Aufgabe richtig verstanden habe, entfernt man jeden Knoten, der nur einen Nachfolger hat, bis man keinen mehr hat, dann ist der Baum vollständig binär. Ich habe mir die Musterlösung zu dieser Aufgabe angesehen und denke, dass sie falsch ist. Wenn man einen richtigen rekursiven Algorithmus dazu haben will, muss dieser folgendes erfüllen:

1. Nach einen rekursiven Aufruf, ist der Teilbaum mit dem aufgerufenen Knoten als Wurzel vollständig binär (das ist offensichtlich)
2. Der als Parameter übergebene Knoten, außer der Wurzel, muss entweder 2 Nachfolger haben oder ein Blatt sein
3. Sollte die Wurzel des resultierenden Baumes nur einen Nachfolger haben, wird dieser Nachfolger als neue Wurzel gewählt

Die zweite Bedingung ist da, weil ein Knoten sich nicht selbst löschen kann, wenn er nur einen Nachfolger hat und gegen die Invariante verstößt. Gegen die Invarianten wird, wenn ich die Lösung richtig verstanden habe, aber mehrmals verstoßen:

In der Funktion reduceToCompleteness wird zwar einmal überprüft, ob die Wurzel nur einen Nachfolger hat und wenn ja, wird dieser als neue Wurzel gewählt, danach wird reduceToCompletenessRec(root) aufgerufen, aber nach dem Aufruf nicht überprüft, ob diese Wurzel auch einen Nachfolger hat (Vertsoß gegen die dritte Invariante).

In der Funktion reduceToCompletenessRec werden die NachfolgerKnoten des übergebenen Parameters gelöscht, wenn sie nur einen Nachfolger haben, es wird aber vor dem rekursiven aufruf aber nicht überprüft, ob der neue NachfolgerKnoten auch nur einen Nachfolger hat, sondern der neue Nachfolger wird direkt als Parameter übergeben (Verstoß gegen die zweite Invariante).

Das Problem könnte gelöst werden, indem man entweder erlaubt, dass reduceToCompletenessRec einen Rückgabewert hat oder man ruft die Funktion mit demselben Parameter rekursiv auf, wenn ein Nachfolgerknoten nur einen Nachfolger hat (Edit: nachdem man diesen Knoten natürlich gelöscht hat) und terminiert dann sofort (der rekursive Aufruf mit demselben Parameter hat schon alles erledigt, also ist nichts mehr zu tun).

Ich habe den Vorschlag in der Musterlösung übrigens getestet und er Funktioniert nicht auf Bäumen, bei denen mer als 2 aufeinander folgende Knoten nur einen Nachfolger haben, sondern löscht nur jeden zweiten und der resultierende Baum ist dann nicht vollständig binär.

Sollte ich mich geirrt haben, tut es mir leid, ich habe die Aufgabenstellung nicht verstanden und es würde mich freuen, wenn ich dann vor der Klausur aufgeklärt werde

LG