Seite 1 von 1

Lösungsstrategie für foo #4

Verfasst: 26. Jun 2015 10:49
von h_ar
Hat jemand bei diesem schweren foo-Testat eine Strategie?
Ich und sicherlich viele andere wären dankbar über jeden Tipp.

Re: Lösungsstrategie für foo #4

Verfasst: 26. Jun 2015 11:14
von KaeferZuechter
Ich hatte gerade das Testat.

a) Double-Hashing ist sehr einfach (lösbar unter 1 Minute)
1. Bei jeder Gelegenheit modulo rechnen um die Zahlen klein zu halten
2. Zahlen nahe n kann man auch durch ihre kleinen negativen Gegenstücke ersetzen
3. Die zweite Hashfunktion ist hier immer \(2\cdot k \mod n\)

b) BTree delete ist schwieriger, jedoch ebenfalls nicht sondernlich aufwendig (lösbar in etwa 2-3 Minuten selbst bei "schwierigen" Fällen)
1. Wenn das Kind auf das man hinabsteigen will nur M (sprich: 1) Schlüssel hat:
1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit rechtem Nachbarn zu mergen
1.3 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.4 Sonst versuche mit linkem Nachbarn zu mergen
2. Wenn der zu löschende Schlüssel gefunden ist, ersetze durch Vorgänger und lösche Vorgänger (1 Wert überschreiben)
3. Wenn der zu löschende Schlüssel in einem Blatt ist, entferne ihn einfach (1 Wert löschen)

Rotieren (Nachbar muss mehr als M Schlüssel besitzen):
1. Verschiebe den Elterschlüssel in das minimale Kind A (1 Wert eintragen und löschen)
2. Verschiebe den Nachbarschlüssel aus dem anderen Kind B in das Elter (1 Wert eintragen und löschen)
3. Verschiebe das mittlere Enkel von B nach A (1 Kante ID und Index ändern)
4. Korrigiere Indizes in B (bis zu 3 Indizes ändern)

Mergen:
1. Ziehe Kinderschlüssel in das Elter (2 Werte eintragen)
2. Lösche Kinderknoten und Verknüpfungen zu selbigen (2 Knoten und 2 Kanten löschen)
3. Verknüpfe frühere Enkel direkt mit Elter (in 4 Kanten ID und Index ändern)

Foo erklärt bei der BTree-Korrektur eigentlich perfekt, was zu tun ist.
Man muss beim Löschen übrigens niemals Knoten oder Kanten erstellen.

Re: Lösungsstrategie für foo #4

Verfasst: 26. Jun 2015 13:35
von Nullmann
KaeferZuechter hat geschrieben: a) Double-Hashing ist sehr einfach (lösbar unter 1 Minute)
1. Bei jeder Gelegenheit modulo rechnen um die Zahlen klein zu halten
Immer benutzen, egal wann!

Mir hat es geholfen, die ersten 5 Multiplikationen zuerst hinzuschreiben, um so einfacher die Modulo-Rechnungen durchführen zu könnnen.
Bsp:
Bei n = 12 habe ich mir aufgeschrieben:
12|24|36|48|60

Selbst bei "großen" Zahlen wie 56 lässt sich so einfach ablesen, dass 58 mod 12 = 56-48 = 8 ist. Die 48 wurde hier genommen, weil sie die größte Zahl in der Reihe, aber nicht größer ist.

B-Tree:

Generell gilt: Wenn man den zu löschenden Key sucht oder diesen mit dem direkten Vorgänger (erst eins nach links, dann immer nach rechts herabsteigen) tauschen möchte, darf man nur hinabsteigen, wenn der jeweilige Knoten mehr als einen Key besitzt. Ansonsten muss Merge oder Rotate eingesetzt werden.
KaeferZuechter hat geschrieben: 1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.3 Sonst versuche mit rechtem Nachbarn zu mergen
1.4 Sonst versuche mit linkem Nachbarn zu mergen
Dieser Reihenfolge kann ich so nicht zustimmen. Es wird immer erst versucht, mit dem rechten Nachbarn zu mergen (falls Anzahl keys = 1) oder zu rotaten (falls Anzahl keys > 1). Nur, wenn kein rechter Nachbar existiert, wird der linke Nachbar genommen. Sodass sich ergibt:

Zusätzlich: Bei so ziemlich jeder Aufgabe muss die Höhe verringert werden, also findet ein Merge an der Wurzel statt. Dies ist der Fall, wenn Sowohl die Wurzel als auch beide Knoten nur einen Key besitzen.
KaeferZuechter hat geschrieben:Foo erklärt bei der BTree-Korrektur eigentlich perfekt, was zu tun ist.
Dem kann ich so vollkommen zustimmen.

"Spezialfälle" von Rotate und Merge sind diese, welche eine "Zwischenebene" darstellen, also sowohl Eltern als auch Kinder besitzen. Bei diesen muss man aufpassen, dass man sowohl die Referenzen auf diese Knoten von den Eltern, als auch die Referenzen von diesen Knoten zu ihren Kindern ändert.

Mfg,
Nullmann

Re: Lösungsstrategie für foo #4

Verfasst: 26. Jun 2015 14:01
von KaeferZuechter
Nullmann hat geschrieben:B-Tree:

Generell gilt: Wenn man den zu löschenden Key sucht oder diesen mit dem direkten Vorgänger (erst eins nach links, dann immer nach rechts herabsteigen) tauschen möchte, darf man nur hinabsteigen, wenn der jeweilige Knoten mehr als einen Key besitzt. Ansonsten muss Merge oder Rotate eingesetzt werden.
KaeferZuechter hat geschrieben: 1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.3 Sonst versuche mit rechtem Nachbarn zu mergen
1.4 Sonst versuche mit linkem Nachbarn zu mergen
Dieser Reihenfolge kann ich so nicht zustimmen. Es wird immer erst versucht, mit dem rechten Nachbarn zu mergen (falls Anzahl keys = 1) oder zu rotaten (falls Anzahl keys > 1). Nur, wenn kein rechter Nachbar existiert, wird der linke Nachbar genommen. Sodass sich ergibt:
Danke! Da habe ich Unsinn geschrieben und es jetzt oben korrigiert.

Re: Lösungsstrategie für foo #4

Verfasst: 26. Jun 2015 15:28
von h_ar
Danke! :)

Re: Lösungsstrategie für foo #4

Verfasst: 1. Jul 2015 11:40
von Smith
KaeferZuechter hat geschrieben:1. Wenn das Kind auf das man hinabsteigen will nur M (sprich: 1) Schlüssel hat:
1.1 Versuche mit rechtem Nachbarn zu rotieren/shiften
1.2 Sonst versuche mit rechtem Nachbarn zu mergen
1.3 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
1.4 Sonst versuche mit linkem Nachbarn zu mergen
2. Wenn der zu löschende Schlüssel gefunden ist, ersetze durch Vorgänger und lösche Vorgänger (1 Wert überschreiben)
3. Wenn der zu löschende Schlüssel in einem Blatt ist, entferne ihn einfach (1 Wert löschen)
Aus den Lernvideos geht meiner Meinung nach hervor, dass ein Merge einem Shift vorzuziehen ist.
Wäre denn nicht diese Reihenfolge die korrekte?:

1.1 Versuche mit rechtem Nachbarn zu mergen
1.2 Sonst versuche mit rechtem Nachbarn zu rotieren/shiften
1.3 Sonst versuche mit linkem Nachbarn zu mergen
1.4 Sonst versuche mit linkem Nachbarn zu rotieren/shiften
2. Wenn der zu löschende Schlüssel gefunden ist, ersetze durch Vorgänger und lösche Vorgänger (1 Wert überschreiben)
3. Wenn der zu löschende Schlüssel in einem Blatt ist, entferne ihn einfach (1 Wert löschen)

Übersehe/missverstehe ich hier etwas?

Re: Lösungsstrategie für foo #4

Verfasst: 1. Jul 2015 12:11
von KaeferZuechter
Merge funktioniert nur, wenn der Nachbar höchstens M Schlüssel enthält und Shift in die gleiche Richtung funktioniert nur für mehr als M Schlüssel.
Die Fälle schließen sich aus und damit ist deren Reihenfolge egal (sofern man wie in Foo arbeitet und nicht wie im oben zitierten, unkorrigierten Post).

Re: Lösungsstrategie für foo #4

Verfasst: 1. Jul 2015 12:16
von Smith
Danke, das macht Sinn : )