Vielwegbäume: echt kleiner und kleiner gleich

uiop
Neuling
Neuling
Beiträge: 2
Registriert: 27. Apr 2017 08:20

Vielwegbäume: echt kleiner und kleiner gleich

Beitrag von uiop » 27. Apr 2017 08:31

Hallo,

mir ist aufgefallen, dass die Folien zu Vielwegbäumen immer 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
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Vielwegbäume: echt kleiner und kleiner gleich

Beitrag von Prof. Karsten Weihe » 27. Apr 2017 11:42

uiop hat geschrieben: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
Neuling
Neuling
Beiträge: 2
Registriert: 27. Apr 2017 08:20

Re: Vielwegbäume: echt kleiner und kleiner gleich

Beitrag von uiop » 29. Apr 2017 13:39

Danke, das beantwortet meine Frage.

Antworten

Zurück zu „Archiv“