Fachrat Informatik - Forum

Quoted

Original von cowhen
Oder meint "günstig" etwas anderes? z.B. die Anzahl der Knoten im Baum? Oder kann ich in die Blatt-Buckets mehr als einen Zahl packen?

Dazu steht etwas auf Seite 90 des Skripts. Ich glaube, ungünstig hat auch etwas mit der "Missverteilung" der Schlüssel in den Knoten zu tun (wirkt sich ggf. auf den Durchschnitt der Suchlänge aus). Mit den Plattenzugriffen hat es in diesem Falle nichts zu tun, da die Höhe (und damit die Anzahl der Zugriffe) ja fest steht.
Ich denke, möglichst wenig Schlüssel in der Wurzel sind ein guter Anfang für "Ungunst", maximale Anzahl (2m = 4) dagegen günstig.

Bei der Anzahl der Knoten bin ich mir nicht so sicher, was da günstig ist und was nicht, eine frühe Begrenzung auf wenige Möglichkeiten klingt für mich aber erstrebenswert, und damit oben erwähnte Maximalfüllung der Wurzel.

Alternativ: Warte auf fundierte Antworten .

Aufgabe 2:
Den Wert 35 kann man doch auf zwei arten einfügen. Ganz normal, wie im Skript steht oder mit einer Ausgleichsoperation (auch im Skript beschrieben). Auf welche Art und Weise sollen wir denn die Werte einfügen? Wenn ich mit einer Ausgleichsoperation den Wert 35 einfüge, dann ist das Entfernen des Wertes 30 sehr einfach hinterher.
mfg
MAX

Quoted

Original von MAX
Aufgabe 2:
Den Wert 35 kann man doch auf zwei arten einfügen. Ganz normal, wie im Skript steht oder mit einer Ausgleichsoperation (auch im Skript beschrieben). Auf welche Art und Weise sollen wir denn die Werte einfügen? Wenn ich mit einer Ausgleichsoperation den Wert 35 einfüge, dann ist das Entfernen des Wertes 30 sehr einfach hinterher.
mfg
MAX

Ich sehe da nur die Möglichkeit, den Knoten zu "suchen", wo der Pfad zum Schlüssel 35 reingeschrieben werden muss, zu erkennen, dass dieser mit 35 mehr als 2m Einträge hätte und somit gespalten werden muss. Du hast 5 Einträge, nimmst davon den mittleren und schreibst ihn in den Vorgängerknoten. Meine Wurzel hat dann also die Einträge 5 20 35 50. Der "Rest" bleibt im Knoten.

Das Entfernen von 30 hat dann zur Folge, dass der Baum äusserlich wie "vor 35" aussieht, nur eben statt 30 37 die Schlüssel 35 37.

Quoted

Original von MAX
Aufgabe 2:
Den Wert 35 kann man doch auf zwei arten einfügen. Ganz normal, wie im Skript steht oder mit einer Ausgleichsoperation (auch im Skript beschrieben). Auf welche Art und Weise sollen wir denn die Werte einfügen?

Da die Ausgleichsoperation im Skript nur als Variante erwähnt ist, die Aufgabenstellung die Verwendung selbiger aber nicht explizit fordert, würde ich es ohne machen.


Zu Aufgabe 3:
Wie sich schnell zeigen läßt, benötigt man zwingend einen zweistufigen B+-Baum. Prinzipiell sind daher alle (13 möglichen) Bäume gleichwertig. Da eine genauere Analyse (z. B. Bestimmung des mittleren Suchaufwandes) jedoch IMHO Angaben zum verwendeten Suchalgorithmus und zu den an den B+-Baum gestellten Anforderungen erfordert, kann man diese hier nicht durchführen. Ich werde daher wohl schreiben, daß ohne weitere Angaben alle möglichen B+-Bäume gleich "günstig" sind (oder in der gleichen "Günstigkeitsklasse" liegen). Für die Komplexität der Suchoperation ist ja ohnehin nur die Stufenzahl relevant.