Ferienübungsblatt

[SophiaLi1]

Und nun nochmal zu meiner anderen Frage, die mir noch zum Verständnis sehr helfen würde: Angenommen, in der Klausur komme ich auf den Fall, dass ich auch nach dem zweiten Durchlauf der HashFunktion den Wert nicht einspeichern kann, weil sie eben nur endlich definiert ist. Kann ich dann davon ausgehen, dass ich mich verrechnet habe oder kann sowas in der Praxis durchaus vorkommen und der Wert wird dann einfach nicht gespeichert?

Ob eine Formel fehlerhaft ist oder nicht, erkennst du daran, dass am Ende des gesamten Ausdrucks auf jeden Fall "mod N_max", also ein Modulo stehen müsste. Dadurch ist garantiert, dass das Ergebnis zwischen 0 und N_max - 1 liegt, also immer ein möglicher Index raus kommt.

[TobiTobske]

Ob eine Formel fehlerhaft ist oder nicht, erkennst du daran, dass am Ende des gesamten Ausdrucks auf jeden Fall "mod N_max", also ein Modulo stehen müsste.

Mmmh, aber in diesem Fall steht das doch bei der Gesamtfunktion F auf jeden Fall dabei?! F setzt sich ja aus F1 und F2 mit Linearfaktor zusammen. Und bei F steht ja ganz am Ende das mod Nmax. Mein Problem ist halt, dass ich ja auf einen sinnvollen Index (0-12) komme, der aber schon belegt ist und ich einen dritten Versuch starten müsste, um den Wert einzufügen.

[import java.noob]

Beispiel (k=100000)

F2 = k + (k mod 13) => 100000 + 4 = 100004

Sagen wir es ist der 6. Versuch (i-1 = 5)

F = (4 + 5*100004) mod 13 = 5

Wo ist das Problem mit großen Zahlen?

[import java.noob]

Kannst du das etwas genauer ausführen, denn ich bin der Meinung es ist unmöglich einen ungültigen Index mit mod zu kriegen

Außerdem verstehe ich dein Problem mit der F2 nicht, denn dort kann etwas gegen Unendlich rauskommen das ist doch egal

[import java.noob]

Es ist nur durch mod N_max sichergestellt, dass man als Index auch einen gültigen Index aus dem Bereich 0 bis (N_max - 1) erhält, das heißt, einen Index, der innerhalb des Arrays liegt. Würde man versuchen, auf einen Index zuzugreifen, der außerhalb dieses Bereichs liegt, so würde man eine IndexOutOfBounds Exception erhalten und das Programm würde abbrechen. (Also der Fall, in dem man auf einen "unendlich hohen" Index zugreifen will.)

Das ist nicht egal, da der Indexbereich für jeden Array endlich ist und ich keinen beliebig großen Index finden kann, sondern nur solche, die als Index für den Array in Frage kommen.

Also beim ersten stimme ich dir vollkommen zu und damit wollte ich meine Argumentation machen

Die Funktion zur Bestimmung des Indexes setzt sich zusammen aus F = (IRGENDWAS) mod 13. F1 und F2 können meiner Meinung nach unendlich sein, denn wie du ja selbst gesagt hast stellt mod sicher dass der Index nicht überschritten wird. Das Ergebnis von F2 ist ja nur eine Hilfsfunktion, warum soll das denn eingeschränkt sein?

[import java.noob]

Ok, ich glaube ich verstehe was du meinst, aber wo steht denn das F nur für i>2 benutzt wird. Ich habe das so verstanden, dass es die Funktion F
zur Index-Berechnung gibt und diese sich auch den anderen Funktionen zusammensetzt.

[import java.noob]

Laut dem Aufgabenblatt hängt F nicht von einem Index ab

[import java.noob]

Das mit dem Fi scheint mir sehr weit hergeholt. Wenn man sagt dass die Funktion Fi(i,nmax,k) ist
Dann müsste man auch so weitermachen, d.h. man bräuchte F3. F4 etc.

Aber das ganze ist unnötig denn wenn man einfach die Funktion F nimmt und brav die Werte aus den anderen Beiden Funktionen
einsetzt kommt man auch auf korrekte Indizes. Wo hast du denn das mit fk her? Und wo das mit i > 2? In den Vorlesungsfolien
steht nämlich immer F(...)

[import java.noob]

Kann mir jemand bei Aufgabe 3 weiterhelfen ich verstehe nicht wie es nach der Merge-Operation von 100, 200, 400 weitergehen soll.

[midstar]

Wieso, was ist das Problem? Was würdest du denn vermuten, was richtig wäre, hast du überhaupt schon einen denkansatz?

Ich persönlich bin mir recht unsicher, meine Überlegung wäre wie folgt:

Merge 180,200,300 zur Wurzel. Jetzt das ganze dabei umlegen, dass es den Vorgaben entspricht, da die Knoten nie voll belegt sein dürfen, damit du ohne probleme einfügen könntest.

Nun wird die 500 gelöscht.

Reicht das als ansatz?


mfg jan

[import java.noob]

Hi,

danke für die Antwort, aber wie hast du es hingekriegt dass 180,200 und 300 in der Wurzel stehen?

Ich frage mich sowieso warum das löschen der 500 so kompliziert ist und man nicht einfach eine Rotation anwenden darf

[SvenF]

moin moin,

import java.noob schau vllt. nochmal die Videos und Folien an, habe da gestern auch nur im Kopf gehabt und Sophia ihre kostbare Zeit gestohlen,

Nach einigen Wdh. der Videos hat es dann klick gemacht
An manchen Stellen überhört man so Tips wie: der Pointer kann nur auf Knoten zeigen die noch Werte entbehren könnten etc. wenn er minimal ist, musst du ihn vorher "umbauen". da ein Merge nach den Wurzel Mergen nicht mehr geht und auch wenig Sinnmachen würde, gibts laut Videos die Rotate-Funktion, die aus so einem Fall helfen kann. somit steht die 500 nicht mehr alleine da und kann gelöscht werden

MfG
Sven

PS:
Auf Seite 2 Findest du auch noch Tipps von Sophia als sie an mir verzweifelte xd^^

[import java.noob]

Hi,

danke, aber man kann doch gleich die Rotate-Funktion anwenden. Was hält einen denn davon ab?

400

300/350 500

Funktion der Rotate funktion ist dass ich den oberen Wert mit dem Vorgänger/Nachfolger ersetze.

350 wäre der Vorgänger von 400, also nach oben

400 350

300 - 500

jetzt noch die 400 in den Rechten Knoten um rotate abzuschließen und dann die 500 löschen - fertig.

Wenn du mir nochmal einen Hinweis geben könntest wäre super ich stehe ziemlich auf dem Schlauch

[SophiaLi1]

Mhm, ich muss gleich weg, aber ich versuchs. Wir haben folgende Situation:

• die Wurzel hat nur einen Key
• die beiden Nachfolger der Wurzel haben nur minimale Anzahl an Keys
• man kann also mit dem Pointer nicht auf einen ihrer Nachfolger zeigen
• in diesem Fall wendet man "Merge Root" an, siehe Foliensatz dazu

[SvenF]

Sophia hat eben den Hauptdenkfehler angesprochen,

Ich dachte auch immer, dass ist so ein konstrukt, und egal wie ich wohin rotiere es passt wenn danach die logische Sichtweise passt. ABER das geht so nicht, weil du siehst den Baum als Visualisierung, und in REALITÄT kommt der Pointer ja von der Wurzel an und muss sich zum Wert durchschlagen, weshalb der Pointer nicht den ganzen komplexen baum kennt wie du der ihn sieht, sondern nur seinen weg. Dieser ist so definiert, dass er auf minimale Knoten beim löschen und auf maximale beim einfügen nicht zugreifen kann. ALSO musst du ihn erst so umbauen, dass der Pointer hindarf und die gewünschte Operation ausführen kann.

MfG