Dein Fortschritt:
0 / 0 Aufgaben
1
Die Mediathek
AFB I–IIDie Mediathek einer Schule verwaltet ihre Medien in einem binären Suchbaum vom Typ BinTree<Medium>. Geordnet wird nach der Mediennummer; jede Nummer kommt höchstens einmal vor. Die Klasse Medium bietet die Operationen getNummer(): Ganzzahl und getTitel(): Zeichenkette.
Material: Ausschnitt des Suchbaums der Mediathek (Mediennummern)
- Beschreiben Sie die Eigenschaft, die einen binären Suchbaum auszeichnet, und zeigen Sie an zwei Knoten des Materials, dass sie erfüllt ist. 3 BE
- Stellen Sie die Suche nach den Nummern 3100 und 8500 jeweils in einer Tabelle mit den Spalten Knoten, Vergleich und weiter dar. 4 BE
- Implementieren Sie die Methode
static String titelZu(BinTree<Medium> b, int nr), die den Titel des Mediums mit der Nummernrliefert oder den leeren Text, falls es keines gibt. 5 BE - Die Kreismediathek hat 100 000 Medien. Schätzen Sie ab, wie viele Vergleiche eine Suche im ungünstigsten Fall braucht, wenn der Baum ausgeglichen ist bzw. wenn die Medien in der Reihenfolge ihrer Nummern eingefügt wurden. 4 BE
Insgesamt 16 BE
Hinweise
Hinweis zu Aufgabe a)
Die Eigenschaft gilt für ganze Teilbäume, nicht nur für die Kinder.
Hinweis zu Aufgabe b)
Eine erfolglose Suche endet an einem leeren Teilbaum — nennen Sie ihn in der letzten Zeile.
Hinweis zu Aufgabe c)
Eine Schleife mit einer Hilfsvariablen genügt; vergleichen Sie
nr mit getItem().getNummer().Hinweis zu Aufgabe d)
Nutzen Sie \(n\le 2^h-1\). Was passiert, wenn aufsteigend sortierte Nummern eingefügt werden?