Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
Datenstrukturen und Algorithmen, Übung 3, Aufgabe 2 f+g
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, November 3rd 2005, 11:08pm
Klar. Er gehört auch zur Klasse O(n^n). Aber Sinn der O-Notation ist es natürlich, möglichst kleine obere Schranken anzugeben. Und O(0) = {0} ist eine echte Teilmenge von O(1) = N.
Quoted
Original von migu
Auch wenn das alles ja eigentlich Unsinn ist: wenn der Code nie ausgeführt wird, hat er doch auch konstante Laufzeit, er gehört also zur Klasse O(1).
Original von DrChaotica
Wieso sollten O(0) - Funktionen nicht existieren?, das ist doch nur Code, der nie ausgeführt wird. Und der hat laut Monsieur LaMothe die beste Laufzeit...
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, November 3rd 2005, 11:13pm
Hinweis: Ein binärer Baum muß keine Wurzel enthalten.
Original von DrChaotica
Übung 4, Aufgabe 1 a)
a) Geben Sie alle binären Bäume an, deren Knoten beim
1. Preorder- und Inorder-,
2. Preorder- und Postorder-,
3. Inorder- und Postorderdurchlauf
in genau derselben Reihenfolge durchlaufen werden. Begründen Sie Ihre Antworten.
Seltsam: Ist das nicht in allen drei Fällen nur ein Baum, der lediglich aus einer Wurzel besteht?
Thursday, November 3rd 2005, 11:27pm
Original von Joachim
Hinweis: Ein binärer Baum muß keine Wurzel enthalten.
Original von DrChaotica
Übung 4, Aufgabe 1 a)
a) Geben Sie alle binären Bäume an, deren Knoten beim
1. Preorder- und Inorder-,
2. Preorder- und Postorder-,
3. Inorder- und Postorderdurchlauf
in genau derselben Reihenfolge durchlaufen werden. Begründen Sie Ihre Antworten.
Seltsam: Ist das nicht in allen drei Fällen nur ein Baum, der lediglich aus einer Wurzel besteht?
Ich vermute, daß diese Aufgabe aber in der Tat so gemeint ist wie Du sie verstanden hast. Wäre sie aufwendiger, so wären daraus statt einem Aufgabenteil wohl drei Teile (1a, 1b, 1c) geworden.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, November 4th 2005, 12:05am
OK, das kenne ich anders. Ich halte es für sinnvoll, den leeren Baum zuzulassen, um auch den Fall des "daten-losen" Baumes abbilden zu können (das ist nützlich, wenn jeder Knoten des Baumes einen bestimmten Datensatz repräsentieren soll und alle Datensätze nacheinander eingefügt werden sollen, ausgehend vom leeren Baum). Und zum Beispiel in der Theorie der Formalen Sprachen ist das leere Wort ja auch ein Wort.
Original von DrChaotica
Allerdings besteht wohl nach unserer Definition jeder Baum aus mindestens einer Wurzel, der Skript sagt hierzu:
Definition: Ein Baum (tree) T ist eine Menge von “Knoten”, die in einer ElternKind(parentchild) Beziehung mit folgenden Eigenschaften stehen:
– T hat genau einen ausgezeichneten Knoten r , der keinen Elternknoten hat; dies ist die Wurzel (root) von T.
Tja, das finde ich jetzt wirklich nicht gut durchdacht.
3.3 Zugehörige ADTen: zunächst der ADT Tree für Bäume
Allgemeine Methoden7:
- size(): int — liefert die Anzahl der Knoten des Baums T
- isEmpty(): boolean — prüft, ob der Baum keinen Knoten hat (->siehe Fußnote 9)
Fußnote 9 sagt dann:
9) da die Wurzel immer in einem Baum enthalten ist, liefert diese Methode allerdings immer false
Lustig, oder? Ist schon seltsam, was die sich so ausdenken...
This post has been edited 2 times, last edit by "Joachim" (Nov 4th 2005, 12:07am)
