Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
datenstrukturen (klausur 03/2002)
also,
aufgabe 7 der o. g. klausur:
bibliotheksarchiv, fuer das beste struktur gesucht wird. angegeben: alle daten werden aufsteigend sortierter reihenfolge eingefuegt.
dann ist es doch egal, ob liste oder bintree, oder? weil durch die voraussetzung der worst case des bintrees erreicht wird, der mit der liste und damit der komplexitaet o(n) gleichzusetzen ist… ?
Aus der “Musterlösung”:
Aufgabe 7 (03/2002)
Eine verkette Liste würde zwar schnelles Einfügen ermöglichen, für das Suchen wäre jedoch ein Aufwand von O(n) nötig.
Da die Daten bereits sortiert vorliegen ist ein binärer Baum auch nicht besser, da er entarten würde. Suchen sonst wieder O(n).
→ verkettete Liste, da schneller Einfügen möglich (O(1)) im Vergleich zum binären Baum (O(n)).
Beide nicht wirklich geeignet, besser wäre AVL-Baum.
PS:
Die Musterlösung zur 03/02 Klausur findest Du hier: http://uni.unclassified.de/forum/thread.php?id=758
ok, thx, das hatte ich uebersehen.
die loesung haette ich ungefaehr genauso gemacht - motivierend!