B-Tree: remove - Falsches Ergebnis?

MOuli
Neuling
Neuling
Beiträge: 1
Registriert: 21. Sep 2015 21:14

B-Tree: remove - Falsches Ergebnis?

Beitrag von MOuli »

Hallo liebes Team.

Ich habe ein Fehler in "B-Tree: remove" gefunden. Laut Lösung soll meine Identische Lösung Falsch sein.

Lösungs Hash: a56021436011acb8e0d0d8e3d2f370a5

Anbei noch Screenshots von meiner Lösung und die als Korrekt angesehene Lösung.
Dateianhänge
Screenshots.zip
(119.97 KiB) 37-mal heruntergeladen

bekir
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 16. Okt 2014 20:35

Re: B-Tree: remove - Falsches Ergebnis?

Beitrag von bekir »

Hast du die ID der Wurzel verändert?

Alby407
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 19. Jul 2014 15:40

Re: B-Tree: remove - Falsches Ergebnis?

Beitrag von Alby407 »

viewtopic.php?f=561&t=32509
Gab mal vor den "B-Tree: remove" Testaten auch Fehler, bei denen eine korrekte Lösung als falsch gewertet wurde.

Aber deine Lösung ist ja richtig, sollte also kein großes Problem darstellen :D

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Re: B-Tree: remove - Falsches Ergebnis?

Beitrag von ob1 »

Ich schließe mich hier mal mit an, weil ich mir den Lösungsvorschlag von foo nicht erklären kann:

Gelöscht werden soll ein Wert im Blatt, dessen Anzahl von Elementen nicht minimal ist. Deshalb sollte meiner Meinung nach der Wert einfach gelöscht werden können. Foo optimiert aber viel weiter oben noch irgendwas herum (siehe Screenshots). Hab ich jetzt etwas Grundlegendes übersehen??

Edit: Dieses Phänomen tritt offenbar öfter auf. Ich habe foo im Semester nicht benutzt da ich meine Studienleistung schon habe, wurde hierzu etwas gesagt? Wird, gerade im Hinblick auf die Klausur, erwartet dass man einen B-Baum zusätzlich noch in der Höhe optimiert? Denn die Eingabe für so eine Aufgabe sollte ja eigentlich ein gültiger B-Baum sein, d.h. nach einem einfachen Löschen oder einfügen sollte der Baum immernoch gültig sein.
Dateianhänge
screenshots.zip
(95.51 KiB) 24-mal heruntergeladen

Loriot2015
Erstie
Erstie
Beiträge: 20
Registriert: 20. Apr 2015 21:03

Re: B-Tree: remove - Falsches Ergebnis?

Beitrag von Loriot2015 »

Hallo,

auch bei mir sieht foo die Lösung als falsch an, obwohl sie identisch ist mit der "korrekten Lösung".
Hier der Seed: 4ca1fa04e7170441de34b58a84065b5e

@ob1
Du musst beachten, dass du nur auf Knoten hinabsteigen darfst, deren Anzahl Keys n > M-1 ist, also größer als minimale Anzahl an Keys - auch wenn du den Key aus einem Blatt löschst.
Also auf dem Pfad zum zu löschenden Key alle Knoten durch geeignete Operationen anpassen, die diese Bedingung nicht erfüllen.

Ähnlich bei B-Tree insert: Nicht auf Knoten hinabsteigen, deren Anzahl Keys bereits maximal ist-

Grüße

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Re: B-Tree: remove - Falsches Ergebnis?

Beitrag von ob1 »

Ah, ok so ist das gemeint. Danke. Das ist wohl eine Implementations-abhängige Eigenheit der bei uns benutzten gedanklichen B-Tree Implementation. Die Frage ist natürlich, wie konnte der Ausgangsbaum dann überhaupt entstehen :wink: Aber ich will mich ja nicht beschweren...

Antworten

Zurück zu „Archiv“