Fachrat Informatik - Forum

Wenn die Wurzel gelöscht wird, müssen die beiden Kinder 6 und 14 verschmolzen werden (fuse). Das führt automatisch dazu, dass auch 11 und 13 verschmolzen werden. Es ergibt sich folgender Baum:

Ebene 0: (6 14)
Ebene 1: (5) (11 13) (15)

Quoted

Original von migu
Wenn die Wurzel gelöscht wird, müssen die beiden Kinder 6 und 14 verschmolzen werden (fuse). Das führt automatisch dazu, dass auch 11 und 13 verschmolzen werden. Es ergibt sich folgender Baum:

Ebene 0: (6 14)
Ebene 1: (5) (11 13) (15)

Mhh...das hier ist jetzt zwar schon etwas älter, aber weil ich mir zu dem Thema auch gerade wieder etwas durchlese, versuchte ich mal die Aufgabe streng nach dem Skript zu bearbeiten:

Gegeben ist der (2,4)-Baum
Ebene 0: (12)
Ebene 1: (6) (14)
Ebene 2: (5) (11) (13) (15)

Gelöscht werden soll die Wurzel, also die (12).

Quoted

Skript 4.45
Finde mit multiwaySearch das zu löschende Item.
Falls es sich nicht in einem Knoten auf dem untersten Level befindet,
vertausche es erst mit seinem “Inorder”Nachfolger.
Nun lösche auf dem untersten Level.

Vertausche nun also mit dem Inorder-Nachfolger:
Ebene 0: (13)
Ebene 1: (6) (14)
Ebene 2: (5) (11) (12) (15)

Lösche 12 auf dem untersten Level:
Ebene 0: (13)
Ebene 1: (6) (14)
Ebene 2: (5) (11) () (15)

Quoted

Skript 4.47
Fall 3: Löschen in (2,4)–Bäumen aus 2erKnoten nur mit 2erGeschwisterknoten:
Verschmelze den Knoten mit
einem direkten Geschwisterknoten
unter Einbeziehung des Zwischenitems
aus dem Elternknoten. (fuse)

Führe fuse durch:
Ebene 0: (13)
Ebene 1: (6) ()
Ebene 2: (5) (11) (14 15)

Hier nochmal die gleiche Situation wie eben, also nochmal fuse machen:
Ebene 0: ()
Ebene 1: (6 13)
Ebene 2: (5) (11) (14 15)

Quoted

Skript 4.48
Ein entleerter Wurzelknoten ist zu löschen.

Zack, weg:
Ebene 0: (6 13)
Ebene 1: (5) (11) (14 15)

Fertig.

Auch auf die Gefahr hin, dass ich mich lächerlich mache: Was ist denn nun mit dieser Lösung, habe ich vllt etwas übersehen? Ich meine mich daran zu erinnern, dass Migus Vorschlag von oben ("Wenn die Wurzel gelöscht wird, müssen die beiden Kinder 6 und 14 verschmolzen werden") in der Übung auch schon so erwähnt wurde, aber aus dem Skript geht es nicht direkt hervor, oder?
Und wenn sowas in der Klausur drankommt, wie sollten wir es dann lösen?
Wer korrigiert denn diese Aufgabe...Migu, du?

... wird durch den Inorder-Nachfolger ersetzt.

Hey Doc,
nur um zu zeigen, dass ich's mit lernen schon bis hierher geschafft habe (und weil es meine Meinung ist), stimme ich deiner Lösung zu.

Ich weiß noch, dass es bei uns in der Übung auch ein wenig Verunsicherung gab... aber ich denke, gerade was das Vertauschen vor dem Löschen angeht, ist das Skript doch sehr eindeutig!

Wünsche noch einen schönen Abend...
derSmutje

Und IHR Übungsleiter habt gesagt, dass DEFINITIV keine genaue Analyse dran kommt, was? Naja, MIR macht das nicht so viel aus, aber andere ärgerten sich schon drüber.

Insgesamt fand ich die Klausur aber fair, mit mehr Zeit oder weniger Aufgaben wäre natürlich auch eine sauberere Handschrift drin gewesen, aber wer will schon immer alles haben, niemand.