Algorithmen[8]#1

[elTybbq]

Hab grad ein Problem bei remove 73. Logisch wär imo:

Code: Alles auswählen

22 40 91
      |
  65 76 78 88
   |  |  |  | \
  65 76 78 88 91

Im Buch steht aber beim Pseudocode zu ABItem::RemoveRec:

Code: Alles auswählen

s' := concatenate(c[i]→s, <s[i]>, c[i+1]→s))

und s ist ja 73, d.h. die Splitter des gefusten Knotens müssten 65, 73, 76, 78, 88 sein, was aber obv. keinen Sinn macht. Help?

[Thomas]

im tutorium bei mir wurde gesagt man löscht dann nicht aus der wurzel sondern den splitter unten also die 65 und lässt die 73 in der wurzel stehen. dafür zieht man dann die 40 runter. so hab ichs zumindest gemacht.

[kimbo]

ich hätte auch ne frage:
woher weiß ich, ob ich mir die kinder vom linken oder vom rechten nachbar borgen soll bzw ob ich nach links oder rechts verleihe?
ich hab dazu in den folien nix gefunden...

[Thomas]

um welchen konkreten fall geht es denn? allg. fügt man ja die elemente immer zu einer bestehenden gruppe hinzu und verschiebt dann. beim löschen löscht man einfach den splitter und das element. wenn man dadurch nen ganzen knoten löscht muss man halt schauen wies am besten passt würde ich sagen.

[Christian S.]

Hier allgemeiner: https://ilias.rz.uni-karlsruhe.de/goto. ... 2Tut08.pdf
Hier spezielle Anleitung: http://www.tommytt.de/tutorium/algorith ... ttachments
Mit den beiden ist es mir klar geworden .

[elTybbq]

ich hätte auch ne frage:
woher weiß ich, ob ich mir die kinder vom linken oder vom rechten nachbar borgen soll bzw ob ich nach links oder rechts verleihe?
ich hab dazu in den folien nix gefunden...

Im Buch wird immer der rechte Nachbar genommen, außer der betroffene Knoten ist selbst ganz rechts.

Hab jetzt in meiner Lösung mit dem rechten Nachbarn balanciert, da auf den VL-Folien, anders als im Buch, bevorzugt balanciert und nicht gefused wird. Ich denke mal im Prinzip ist alles richtig, ob linker oder rechter Nachbar, fusen oder balancieren, hängt halt von der konkreten Implementierung ab. Man sieht ja schon am Unterschied zw. Buch und Folien, dass es da verschiedene Varianten gibt.