Seite 1 von 1

B-Baum Range

Verfasst: 20. Sep 2017 16:38
von goerlibe
Für eine (rein exemplarische) Wurzel mit den Keys 5, 10, 15 ergeben sich laut Folien und dem Erklärungsvideo die folgenden Ranges für NachfolgerKnoten:

1.Nachfolger: MIN_VALUE - 5
2.Nachfolger: 5 - 10
3.Nachfolger: 10 - 15
4.Nachfolger: 15 - MAX_VALUE

Aber ist nicht Folgendes sinnvoller? Denn in obigem Beispiel hat man das Problem, dass nicht eindeutig definiert ist, ob zb der neue Key 5 im ersten oder zweiten Nachfolger eingefügt werden soll.

1.Nachfolger: MIN_VALUE - 5
2.Nachfolger: 6 - 10
3.Nachfolger: 11 - 15
4.Nachfolger: 16 - MAX_VALUE

Nun die eigentlich wichtigere Frage: Ist die hier vorgeschlagene Lösung falsch? (Mir ist bewusst, dass meine Lösung auch falsch ist..)

Wie wäre eine korrekte Lösung? (falls der Vorschlag von Nabla tatsächlich nicht stimmt)

Re: B-Baum Range

Verfasst: 21. Sep 2017 11:15
von mdk
Darüber bin ich auch schon gestolpert. In Nabla ist es so, dass nach links für "<=" abgestiegen wird und nach rechts für ">".

Re: B-Baum Range

Verfasst: 21. Sep 2017 11:54
von goerlibe
leider ist es eben nicht so...
Betrachte die Vorkommen von 67 in der vorgeschlagenen Lösung:
am ersten Knoten (und key 67) ist die nächste 67 links zu finden, also wenn x<=67 gesucht wird müssen wir links abbiegen;
dann biegen wir jedoch (obwohl der key wieder 67 ist) nach rechts ab, um die nächste 67 zu finden, also x>=67 bedeutet rechts abbiegen;

damit ist für x=67 nicht eindeutig definiert, in welche Knoten wir schauen müssen, ergo müssen wir links und rechts schauen, das erhöht sowohl den Aufwand beim Programmieren (da wir Sonderfälle behandeln müssen), als auch die Laufzeit des geschriebenen Programms.

Laut den Folien ist dies seltsamerweise korrekt jedoch kommt mir das absolut unsinnig vor: Es werden die Ranges immer als Intervalle einschließlich der zuvor gesehenen Key-Werte betrachtet, also immer mit <= und >= in beide Richtungen beschränkt.
Mir ist nicht klar, was der Mehrwert dieser Uneindeutigkeit ist und daher frage ich mich, ob sich hier ein Fehler durch die gesamte Veranstaltung zieht. (Folien, Nabla, Erklärungen von KW)

Re: B-Baum Range

Verfasst: 21. Sep 2017 12:01
von mdk
Ich verstehe dein Problem nicht. Du suchst den Wert 67. In der Wurzel steht 67. Es gilt also 67 <= 67, also nach links absteigen. Dann gilt 67 >55, also nach rechts absteigen. Dort ist dann der gesucht Wert. Passt doch alles. Oder habe ich dein Problem noch nicht ganz erfasst?

Re: B-Baum Range

Verfasst: 21. Sep 2017 12:04
von Hans123
Das Problem ist, dass mit unserer momentanen Definition es auch möglich sein kann, dass eine 67 erscheint, wenn man am Anfang rechts runter geht.

Re: B-Baum Range

Verfasst: 21. Sep 2017 12:42
von goerlibe
mdk, schau dir den Lösungsvorschlag an, nicht die Aufgabenstellung (und auf gar keinen Fall meine Lösung :oops: )
Dort ist das große Chaos, von dem ich rede

Re: B-Baum Range

Verfasst: 21. Sep 2017 15:57
von mdk
Also wenn man der Definition von Herrn Weihe folgt, dann ist es in der Tat nicht eindeutig, wohin jetzt welcher Wert gehört. Deshalb muss man sich für eins entscheiden, wie z.B. in Nabla. Für <= nach links und > nach rechts. Andersherum wäre ja auch ok, denke ich. Man muss es nur definieren.