Delete mehrere Werte

[Francis C.]

Servus an Alle da draußen!
Habe mir jetzt alle Posts angeschaut und auch in den Videos wird meine Frage nicht einen Pfifferling erwähnt meines Wissens.

Meine Frage ist eigentlich ganz einfach, wenn in einem B-Baum ein Wert öfter vorkommt, welcher wird dann gelöscht?
Möglich das ich mich irre, aber ich hab in der Lösung einmal den 1. und einmal den am weitesten unten stehenden gelöscht bekommen.

Und bitte nicht antworten "Der zuerst gefunden wird", denn dann bräuchte ich noch eine Erklärung in welcher Reihenfolge er durchläuft, ob erst Key[First] oder erst Children[First] innerhalb eines Nodes abgefragt wird.

Danke im Voraus und eine schöne heiße End-Phase der Testate euch noch.

Wie immer,
Euer Francis C.

[Nullmann]

Frage wurde hier schon gestellt:viewtopic.php?f=561&t=32525

Der "erste" Wert ist hier der in der obersten Ebene. Also von links nach rechts und dann von oben nach unten. Wie beim Lesen

[Francis C.]

Sowohl die Verlinkung zum anderen Post als auch deine Antwort ist (zumindest Teilweise)falsch.

Die Verlinkung beantwortet eine ganz andere Frage, die sich meiner Meinung nach eigentlich gar nicht stellt, da immer klar ist welcher der Algos benutzt werden muss.

Habe eben einen erneuten foo-Test gemacht und da wurde eben der allererste Wert, der in einem "Endblatt" ist, gelöscht. Hierbei ist anzumerken, das der Wert in der Anfangswurzel, als auch im Nachbarsknoten als auch im "Knoten oben drüber" vorkam.. also nicht der erste der gefunden wird wie beim lesen^^
Echt strange..

Ich werde meine Erfahrungen hier teilen, solange ich keine zufriedenstellende Antwort habe, vllt find ichs ja sleber raus :p

As usual your
Francis C.

[steffen12]

Ok, ich versuche die Vorgehensweise, des Algorithmus grob zusammenzufassen, obwohl sich das AlgoWiki an dieser Stelle als Lektüre wesentlich besser eignet, weil die Beschreibung dort vollständig und präszise ist.

Ein Zeiger (p) auf den (in der jeweiligen Iteration) aktuellen Knoten steigt nach und nach durch die Knoten, in deren Range der Suchschlüssel liegt, im Baum hinab.
Wenn der gesuchte (zu löschende) Schlüssel sich im Baum befindet wird er in diesem Pfad gefunden. Wenn der Knoten in dem der Schlüssel gefunden wurde kein Blatt ist, wird die Position markiert, found = true gesetzt und der Zeiger p steigt weiter entlang des Suchpfades hinab.
Während der Traversierung des Suchpfades kann es immer wieder zu merge und Shift_key_to_sibling -Operationen kommen, um die Invariante des Algos zu erhalten.
Erreicht der Zeiger p das Blatt des Pfades, und ist found == true, dann wird der Schlüssel an der zuvor markierten Position mit dem größten Schlüssel im aktuellen Knoten (Blatt) überschrieben, denn dies ist der unmittelbare Vorgänger des Suchschlüssels in Sortierreihenfolge. Falls found == false, wird etweder der im Blatt gefundene Suchschlüssel entfernt, oder der Algo gibt false zurück, da der Schlüssel nicht im Baum gefunden wurde.

Grüße, Steffen

[Nullmann]

Ups, tut mir Leid. Da war ich wohl mit dem Verlinken zu voreilig. Wusste aber, dass es einen ähnlichen Post schonmal gibt, und zwar hier:
viewtopic.php?f=561&t=32512

Wegen deiner Frage: Bin mir nicht sicher, was dort mit "totaler Ordnung" gemeint ist. Bei mir hat die "Löschen in Lesereihenfolge" bei den letzten ~20 bestandenen Beispielen gepasst. Eventuell könntest du einen Screenshot eines solchen Beispiels posten? Könnte mir auch vorstellen, dass diese totale Ordnung die Knoten-ID's sein können.

[steffen12]

Bin mir nicht sicher, was dort mit "totaler Ordnung" gemeint ist.

Es ist lediglich die Ordnung gemeint, die durch die < -Relation auf den natürlichen Zahlen (unsere Schlüsselmenge) induziert wird.

[Lysoland]

Bei mir auch sehr merkwürdig.


Bei mir wurde einmal der erste Wert gelöscht der "gelesen" wurden und nun der in einem Blatt

[M3ph1st0]

Prinzipiell kann man doch sagen, dass es egal ist, welcher Wert gelöscht wird.
Löscht man den Wert in einem Knoten und geht nach links und immer weiter nach rechts, erreicht man irgendwann den äußersten rechten Wert, dieser ist entsprechend des Baum Aufbaus gleich dem zu löschenden Wert. Vertauscht man nun die beiden Werte, hat das den selben Effekt, wie ein Löschen von dem Wert im Blatt. Da man aber nicht kontrollieren kann, welcher Wert gelöscht/ersetzt wurde, ist es für eine korrekte Bearbeitung der Foo-Aufgabe unerheblich wie man vorgeht oder sehe ich das falsch?

[hololol2]

Wenn ich es richtig verstanden habe ist es so:
1) Unabhängig davon, ob der zu löschende Wert doppelt vorkommt, wird immer erst gelöscht, wenn in ein Blatt abgestiegen wurde. Für den Abstieg wird immer der Knoten gewählt, der die größten Elemente enthält, die kleiner als der gesuchte sind.
2) Wenn der zu löschende Wert doppelt vorkommt, gibt es zwei Fälle:
a) Der zweite zu löschende Wert wurde gar nicht "entdeckt". Folglich kann er auch nicht gelöscht werden.
b) Ansonsten tritt ein, was Mephisto gesagt hat

[KaeferZuechter]

Wenn der Schlüssel \(K\) in einem Knoten \(p\) gefunden wird, wird dieser Knoten markiert/gespeichert. (\(p'\) im Algowiki)
Der Zeiger steht jedoch immer noch davor und wandert (im davorliegenden Kind \(p.children[k]\)) bis zum Blatt. Dort wird entweder der Schlüssel gelöscht (wenn doppelt vorhanden) oder aber der letzte Schlüssel wird entfernt und in \(p'\) an die Stelle von \(K\) kopiert. Im Grunde das gleiche Prinzip wie bei remove des binären Baumes. Man ersetzt den zu löschenden Schlüssel durch seinen Vorgänger.

Andere Strategien sollten ebenfalls möglich sein, sind in Foo (und wohl auch im Theorietestat) jedoch nicht gefragt.