Original von 6oeser6u6e
Moin,
die DuA Übungen sind ja schon schwer genug, aber wenn nicht mal erklärt wird wie sie zu schaffen sind bin ich hilflos...
deswegen:
Wie erstellt man aus der r(i,j) Matrix graphisch einen optimalen Suchbaum???
In der Übung wurde das zwar gemacht, aber ohne jegliche erklärung oder konzept/rezept... in der Vorlesung steht lediglich, dass es schwer ist -.-
Vier Stunden und 25 Minuten vor Abgabe der Übung fällt dir aber reichlich spät auf, dass das nicht so einfach ist.
Da das ja auch in der Klausur drankommen kann, will ich es kurz erklären.
Beispiel aus der Vorlesung (Folie 4.29 - 4.35):
Gegeben sind Schlüssel k_i mit (i=1, ..., n). In der Matrix r(i,j) steht oben rechts der Index des Schlüssels, der in der Wurzel zu stehen hat. Hier ist das k_4. (Im folgenden schreibe ich kurz "Knoten 4", wenn ich Knoten für Schlüssel k_4 meine.)
Daraus folgt, dass der linke Teilbaum vom Intervall (k_0, k_3) abgedeckt wird und der rechte Teilbaum vom Intervall (k4, k_{n+1}). (In den beiden Teilbäumen können also jeweils nur Schlüssel mit Indizes aus den jeweiligen Intervallen enthalten sein.)
Für das Intervall (k_0, k_3) wollen wir die Wurzel (den Schlüsselindex) wissen. Wir schauen also r(0,3) nach. Es ist r(0,3)=2. Also ist Knoten 2 linker Kindknoten von 4. Rechts: r(4,n+1) existiert nicht. Also hat Knoten 4 keinen rechten Kindknoten!
Weiter mit dem linken Teilbaum für Knoten 2: Dafür gilt Intervall (k_0, k_2), also r(0,2)=1. Linker Kindknoten von Knoten 2 ist demnach Knoten 1.
Für den rechten Teilbaum von Knoten 2 gilt Intervall (k_2, k_3). r(2,3)=3. Also ist Knoten 3 der rechte Kindknoten von Knoten 2.
Wir sind fertig, da alle Schlüssel verteilt sind. An Knoten 1 hängt links als externer Knoten das Intervall (k_0, k_1), rechts (k_1, k_2), an Knoten 3 hängt links (k_2, k_3) und rechts (k_3, k_4) und an Knoten 4 (Wurzel) hängt rechts (k_4, k_5). (k_0 = minus unendlich, k_5 = unendlich)
Merke: In der Matrix r(i,j) stehen die Indizes für die Wurzelschlüssel in Intervallen (i,j).
Quoted
Original von 6oeser6u6e
