B-Baum Range

Ist die Lösung von Nabla richtig?

Umfrage endete am 28. Sep 2017 18:20

Ja
1
33%
Nein
2
67%
 
Abstimmungen insgesamt: 3

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

B-Baum Range

Beitrag von goerlibe » 20. Sep 2017 16:38

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)
Dateianhänge
Screenshot (18).png
Mir ist bewusst, dass meine Lösung falsch ist,. Ist jedoch auch der Lösungsvorschlag falsch, da die Suchbaumeigenschaft verletzt ist?
Screenshot (18).png (33.19 KiB) 1153 mal betrachtet
Screenshot (17).png
Die Aufgabenstellung
Screenshot (17).png (36.99 KiB) 1153 mal betrachtet

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

Re: B-Baum Range

Beitrag von mdk » 21. Sep 2017 11:15

Darüber bin ich auch schon gestolpert. In Nabla ist es so, dass nach links für "<=" abgestiegen wird und nach rechts für ">".

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: B-Baum Range

Beitrag von goerlibe » 21. Sep 2017 11:54

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)

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

Re: B-Baum Range

Beitrag von mdk » 21. Sep 2017 12:01

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?

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: B-Baum Range

Beitrag von Hans123 » 21. Sep 2017 12:04

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.

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: B-Baum Range

Beitrag von goerlibe » 21. Sep 2017 12:42

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

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

Re: B-Baum Range

Beitrag von mdk » 21. Sep 2017 15:57

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.

Antworten

Zurück zu „Archiv“