Seite 1 von 1

B-Tree: delete Vorrang?

Verfasst: 19. Jun 2015 10:01
von Lithanel
Ich wollte fragen, ob die Merge- oder die Rotate-Operation Vorrang hat, weil wenn man beide einsetzen konnte und nur eine davon aussgereicht hat, dann kam es bei mir vor, dass manchmal die Rotate-, aber in anderen Fällen die Merge-Operation verwendet wurde. Nun weiß ich nicht wirklich, welches nun wirklich Vorrang hat.

Re: B-Tree: delete Vorrang?

Verfasst: 19. Jun 2015 11:05
von Nullmann
Wenn der Knoten, zu dem man hinabsteigt, Mindestanzahl an Keys hat (d.h. bei Foo mit M=2: Nur M-1= 1 key), dann muss man eine der beiden Operationen anwenden.
In der Implementation im Algowiki wird das bestimmt auch nochmal so in Quellcode-Format hinterlegt sein, aber meine Beobachtungen des Algos über Foo lautet:
Es wird immer erst der rechte Nachbar betrachtet und die Operation mit diesem bevorzugt.
Heißt in der Praxis an dem Beispiel: Linker Nachbar hat zwei Keys, Knoten an sich ein Key, rechter Nachbar hat ein Key. Hier wäre eine Rotate-Operation mit dem linken Nachbarn möglich und auch einfacher (in der Handhabung mit Foo mMn), es wird aber eine Merge-Operation mit dem rechten Nachbar durchgeführt.

Re: B-Tree: delete Vorrang?

Verfasst: 19. Jun 2015 15:36
von Lithanel
Also soll es heißen, dass keiner von den beiden Operationen Vorrang hat? Also wäre es z.B. in der Klausur egal welchen wir verwenden?

Re: B-Tree: delete Vorrang?

Verfasst: 19. Jun 2015 16:05
von Nullmann
Soll heißen, dass die Operation Vorrang hat, die mit dem rechten Nachbar (dem Nachfolger) durchführbar ist. Hat der Rechte Nachbar M - 1 keys, dann wird eine Merge-Operation durchgeführt. Hat der Nachbar mehr >=M Keys, dann wird eine Rotate-Operation durchgeführt.
Nur, wenn es keinen rechten Nachbar gibt, wird der linke Nachbar verwendet.