Widerspruch Videos Sose2013 und Wiki

TobiasL
Neuling
Neuling
Beiträge: 2
Registriert: 22. Jun 2013 11:48

Widerspruch Videos Sose2013 und Wiki

Beitrag von TobiasL »

Hallo,
ich beschäftige mich gerade mit der aktuellen GdI Hausübung Nr. 9 und soweit ich das einschätzen kann, ist mir ein Widerspruch zwischen Aussagen aus den Videos SoSe 2013 von Herrn Weihe und dem Wiki aufgefallen, was bestimmte Kriterien zur Entfernung von Werten aus B-Bäumen angehen. Herr Weihe versuchte in seinem Video zu den Btrees (etwa ab Minute 11:30) die 99 aus dem gegeben Baum (Ordnung 3) zu löschen. Dabei passierte er auf dem Weg nach unten mit dem Pointer p einen Knoten, der exakt M-1, also 2 befüllte Keys enthielt. Laut späteren Aussagen von Herrn Weihe (Minute 14) und der Beschreibung im Wiki, zeige der "Pointer p immer grundsätzlich nur auf ein Knoten, der MEHR als M-1 Keys enthält und aus dem ein Key entfernt werden könnte..." Gilt dieser Satz bei allen Entfernungsprozessen in einem B-Baum, oder ist dies eine Ausnahme bei Merge und Rotate Entfernungen? Wenn die Aussage allerdings allgemein gültig ist, dann wäre dies ein Widerspruch mit dem ab Minute 11:30 gezeigten Beispiel, da p dort eben auf einen Knoten mit Genau M-1, also 2 Keys und nicht auf einen Knoten mit einer Anzahl von beschriebenen Keys > M-1, zeigte.
Ich hoffe, dass mein Problem verstanden wurde.

LG,
Tobias

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Widerspruch Videos Sose2013 und Wiki

Beitrag von JannikV »

Hallo,

wenn es nach der Iteration (und nicht mittendrin) weniger als M sind und p nicht die Wurzel war und
wenn du das p aus B-Tree: remove meinst und nicht das aus dem Scope der Hilfsmethoden shift, rotate und merge und
wenn Prof. Weihe zu einem späteren Zeitpunkt im Video nochmal gesagt hat dass es min. M sein müssen und
wenn es im Wiki so steht (was es tut ^^)

dann hast du recht und da wurde wahrscheinlich einfach was vergessen.

VG

TobiasL
Neuling
Neuling
Beiträge: 2
Registriert: 22. Jun 2013 11:48

Re: Widerspruch Videos Sose2013 und Wiki

Beitrag von TobiasL »

Hey,
Vielen Dank für die schnelle Antwort.
Das bedeutet dann, dass der p nach jeder Iteration praktisch nur dann weiter nach unten vorrückt, wenn das p auf ein Knoten zeigt, der mindestens mit M Werten befüllt ist?
Bei der Hausübung würde man da beispielsweise auf die 95 stoßen, wenn man die 99 löschen wollte, oder? p zeigt ja nach der Wurzel auf einen Knoten, der nur mit einem Wert (95) gefüllt ist und bevor wir nun weiterrücken dürfen müssen wir erstmal diesen Knoten mit mindestens 2 Werten, also M werten befüllen und dazu wenden wir ja beispielsweise die rotate Operation an.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Widerspruch Videos Sose2013 und Wiki

Beitrag von JannikV »

TobiasL hat geschrieben:Das bedeutet dann, dass der p nach jeder Iteration praktisch nur dann weiter nach unten vorrückt, wenn das p auf ein Knoten zeigt, der mindestens mit M Werten befüllt ist?
Nunja, dafür sorgen ja eben die Hilfsmethoden.

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: Widerspruch Videos Sose2013 und Wiki

Beitrag von AnnaW »

Wenn mein Knoten jetzt genau m Elemente hält und ich aus diesem Knoten ein Element lösche, muss ich dann rotieren oder mergen, damit in dem Knoten aus dem gelöscht wurde, wieder mindestens m Elemente enthalten sind? Ich denke nicht, da mein p nach dem Löschvorgang ja nicht mehr auf das Blatt zeigt, oder?

Viele Grüße

Anna

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Widerspruch Videos Sose2013 und Wiki

Beitrag von JannikV »

Nachdem gelöscht wurde sollte das egal werden und es muss nichts mehr geshiftet werden.
Das kannst du aber auch nachsehen wenn du dir im wiki anguckst an welchen stellen geshiftet und gemerged wird.

VG

Antworten

Zurück zu „Archiv“