Wörterbuch in Python - AVL Bäume

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
lisa_g
User
Beiträge: 1
Registriert: Montag 14. Juni 2021, 10:18

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
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

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.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

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.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten