-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 12:28:26AM +0200, Urs Liska wrote:
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
[...]
Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
02-data-structures/06-binary-search-trees/is_bst/is_bst.py
Ja. Allerdings ist die bereits im master-Branch, was bedeutet, dass die Aufgabe schon erfolgreich absolviert wurde (inzwischen, d.h. seit meinem ersten Post).
Congrats :)
Bei der Methode is_bst(self, indeex=0) stehe ich noch auf der Leitung: was soll die Methode als Rückgabewert liefern? Ich meine: was für eine Art Objekt?
Wenn ich nicht ganz auf der Leitung stehe, dann vermute ich hier den Knoten :-)
Das ist in der Tat recht kryptisch und hätte wohl eine bessere Kommentierung verdient. Dann hätte ich auch den (allerdings konsequenzlosen) Fehler bemerkt ...
+1
Der Rückgabewert der rekursiven Funktion ist eine Liste mit den Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right",
OK. Darauf wäre ich allerdings nicht gekommen, zumal is_bst einem das Hirn schon auf ein boolean "polt" (is this thing a binary search tree?). Das verführt einem dazu, sich diese "Frage" rekursiv vorzustellen
is_bst(tree): return tree.left.val < tree.val \ and tree.val < tree.right.var \ and is_bst(tree.left) \ and is_bst(tree.right)
(das ist natürlich salopp formuliert, bei Deiner Darstellung des Baums müssen eher solche Dinge stehen wie
self.value(self.left(index)) < self.value(index) ...
bzw.
is_bst(self.left(index))...
... you get the idea. Man muss natürlich damit klarkommen, dass diese Methoden manchmal None liefern, was den Ausdruck etwas unübersichtlich macht (bei den Vergleichen).
Anders als bei Deinem Ansatz muss man also nicht "mittendrin" herausspringen (d.h. fail()), sondern das Ergebnis entsteht rekursiv. Im Fehlerfall ist das "Herausspringen" schneller, natürlich.
wodurch rekursiv eine Liste mit dem gesamten Inhalt des Baums in natürlicher Ordnung entsteht. Diese Liste kann allerdings recht lang werden und kostet offensichtlich zu viel Rechenzeit.
Falsch ist, dass das mittlere Element nicht "[index]" sein dürfte, sondern der tatsächliche Schlüsselwert, nämlich "[self.value(index)]". Da dieser mittlere Wert aber überhaupt nicht gebraucht wird, ist der
Das verstehe ich nicht: der mittlere Wert muss doch zwischen den linken und den rechten liegen, damit der Baum sortiert ist? Muss man das nicht auch prüfen?
Fehler nicht aufgefallen. DIESE Aufgabe ist also inzwischen erfolgreich gelöst.
Bestens. Hängst Du noch irgendwo?
lg - -- t