Seite 1 von 1

Wörterbuch in Python - AVL Bäume

Verfasst: Montag 14. Juni 2021, 10:31
von lisa_g
Hallo ihr lieben,

für die Uni soll ich ein Programm schreiben, welches eine Textdatei einliest, die in der ersten Zeile einen Kommentar beginnend mit # und in jeder weiteren Zeile ein Kommando aus {ins, del, search}
und einen String s ∈ {a, ..., z} enthält. Auf der Basis von AVL Bäumen soll ich ein Wörterbuch implementieren welches dann die einzugebenden Operationen (per txt) in der Konsole ausgeben soll. Zudem soll noch ein weiteres Wörterbuch über Hashing implementiert werden, das bekomme ich aber denke hin.

Meine Frage. Mir fehlt jeglicher Ansatz zu den AVL Bäumen und wäre wirklich dankbar wenn mir jemand nen Denkanstoß oder Tipps geben könnte ! :)

LG Lisa

Re: Wörterbuch in Python - AVL Bäume

Verfasst: Montag 14. Juni 2021, 11:40
von __deets__
Du wirst eine Baum-Klasse brauchen, und eine Knoten-Klasse, mit den Attributen, die so ein AVL-Knoten braucht. Habe ich nicht mehr im Kopf, aber das ist neben der Nutzlast auch irgendwelche Marker, wenn ich mich recht erinnere. Oder waren das Red-Black-Trees.

Und dann fängst du erstmal mit den Klassikern an. Suchen eines Knoten im Baum. Einfügen eines Knoten in den Baum. Etc.

Re: Wörterbuch in Python - AVL Bäume

Verfasst: Dienstag 15. Juni 2021, 13:24
von __blackjack__
Wenn das doch nur so Seiten im Netz gäbe wo man einen Suchbegriff eingeben könnte, und die dann danach Suchergebnisse mit Webseiten liefern könnten, wo dieser Suchbegriff vorkäme. Der absolute Hammer wäre es, wenn man dabei regelmässig zu solchen Technischen Suchbegriffen auch Seiten finden könnte die so etwas wie eine Enzyklopädie wären: https://de.wikipedia.org/wiki/AVL-Baum

In der Uni hätte ich auch erwartet das die Folien zu der Vorlesung eine Literaturliste haben. Ist ja nicht so das AVL-Bäume nicht zum Standard von vielen Fachbüchern zu Datenstrukturen gehören würden. In meinem Cormen steht auf Seite 333 was zu AVL-Bäumen.