Vielwegbäume: echt kleiner und kleiner gleich

[uiop]

Hallo,

mir ist aufgefallen, dass die Folien zu Vielwegbäumen immer

Code: Alles auswählen

<=

verwenden um Bereiche zu beschreiben. Ab Folie 4 in MultiWayTrees.pdf "Keys in Nachfolgern" überlappen die Bereiche:

x<=357

,

357<=x<=1229

,

1229<=x<=4095

,

4095<=x<=5621

und

5621<=x

. Schlüssel die bereits im übergeordneten Knoten stehen können entweder links oder rechts gespeichert werden. Das bedeutet es genügt nicht mehr nur einen Pfad zu durchsuchen um alle Einträge zu einem Schlüssel zu finden. Ich gehe davon aus, dass

x<=357

,

357<x<=1229

,

1229<x<=4095

,

4095<x<=5621

und

5621<x

gemeint war. Oder haben die überlappenden Bereiche doch einen Sinn?

Viele Grüße
uiop

[Prof. Karsten Weihe]

Das bedeutet es genügt nicht mehr nur einen Pfad zu durchsuchen um alle Einträge zu einem Schlüssel zu finden.

Das ist richtig. Aber in unserer Methode find reicht ein einzelner Pfad, da nur die Information zurückgeliefert wird, ob der gesuchte Schlüsselwert überhaupt einmal im Baum vorkommt oder nicht. Bei insert reicht ebenfalls ein Pfad.

Auch dann, wenn Sie alle Vorkommen eines Schlüsselwertes suchen, geht es immer noch schnell: Sie steigen zwei Pfade herab, einmal bis zum "linkesten", einmal bis zum "rechtesten" Vorkommen des gesuchten Schlüsselwertes. Alles dazwischen sind genau die Vorkommen des gesuchten Schlüsselwertes in diesem Baum.

Ist Ihre Frage damit beantwortet?

KW

[uiop]

Danke, das beantwortet meine Frage.