| Zeige Beiträge 1 bis 6 von 6 Treffern |
|
 Thema: universelles Hashing |
|
|
Guten Abend,
ich habe eine Frage zum universellem Hashing. Wenn wir drei Hash-Funktionen (h1,h2,h3) gegeben haben (die in dem Falle unwichtig sind) und Zahlen in diese einfügen, erhalten wir Ergebnisse die man z.B. in eine Tabelle einordnen kann:
-- 7 15 20 34 42
h1 1 0 2 1 0
h2 1 0 0 2 1
h3 2 1 0 2 1
Ich habe mal gelesen dass wenn in der Tabelle 2 gleiche Kollisionen auftreten, die Familie nicht universell ist. Die Frage ist hierbei: hier kollidieren die 7 und 34 beide sowohl in h1 und in h3. Allerdings einmal in Spalte drei und einmal in Spalte eins. Zeigt dies schon, dass die Familie nicht universell ist, oder ist es nur nicht universell, wenn diesselbe Kollision auch in der selben Spalte auftreten?
Vielen Dank im Voraus!
LG Ic3Cub3
|
|
| Thema: Beweis Anzahl Blätter vollständiger Binärer Baum |
|
|
Hallo nochmal,
ich habe da noch eine Frage. Sollte sich der Induktionsschritt nicht auf den Induktionsanfang beziehen, da falls man sich auf die Induktionshypothese bezieht und diese falsch ist man sozusagen in eine Schleife mit Fehlern gerät?
LG Ic3Cub3
|
|
| Thema: Beweis Anzahl Blätter vollständiger Binärer Baum |
|
|
Hallo Marco,
Vielen Dank für deine Antwort!
| Zitat: |
Auch das würde ich anders machen. Du gehst ja quasi von einem größeren Baum aus und halbierst den dann. Das mag zwar letztlich auch funktionieren indem Du das Ergebnis dann quasi rumdrehst, aber da bin ich mir nicht ganz sicher.
Eigentlich musst Du ja von einem Baum mit Tiefe h (zuerst mit einem Knoten, also h=1, dann aber für alle folgenden) auf einen Baum mit Tiefe h+1 kommen.
Da an jedes Blatt des Baumes mit Tiefe h jeweils zwei neue Knoten angehängt werden, die dann zu den neuen Blättern werden, ist es klar, dass sich bei h -> h+1 auch die Blattzahl verdoppeln muss, also b -> 2*b.
Hier siehst Du vielleicht dann auch nochmal meine Bauchschmerzen mit Deinem Induktionsanfang: Wenn ich mit 0 Knoten anfange, dann kann ich an kein Blatt zwei weitere Blätter anhängen. Ich komme so nie mit meinem Induktionsschritt vom Induktionsanfang auf die nächste Baumtiefe. |
bei h=0 hat der Baum genau h^0=1 Knoten, was ich im IA gezeigt habe.
Ich beziehe mich auf deine Idee und gehe eine Ebene tiefer auf h+1.
Die Knoten verdoppeln sich, also habe ich 2*1=2 Blätter.
h+2<=>h=2: 2*2*1=2^2 Blätter
h+3<=>h=3: 2*2*2*1=2^3 Blätter
.
.
.
h: 2^h Blätter
--> ein vollständiger binärer Baum hat 2^h Blätter
Ist das was du meinst? Und könntest du mir bei der Formailtät helfen? :)
Vielen Dank im Voraus!
LG Ic3Cub3
|
|
| Thema: Beweis Anzahl Blätter vollständiger Binärer Baum |
|
|
Meine Frage:
Hallo,
da ich neu in diesem Forum bin, bitte ich um Nachsicht, falls ich Fehler machen sollte 
Aufgabe: Wie viele Blätter hat ein vollständiger binärer Baum der Höhe h? Beweis per vollständiger Induktion.
Meine Ideen:
Behauptung:
Baum der Höhe h hat 2^h Blätter
Induktionsanfang:
für h=0 --> 2^0=1 Blatt
stimmt.
Induktionsschritt:
T ist ein Baum der Höhe h
die Wurzel von T hat zwei Teilbäume als Söhne, die jeweils die Höhe h-1 haben
Diese Teilbäume haben eine Blätteranzahl von 2^(h-1)
Somit hat T 2*2^(h-1)=2^(h) Blätter.
Ich denke, dass die Grundidee hierbei richtig ist.
Allerdings glaube ich, dass dieser Beweis nicht vollständig ist. Z.B. weiß ich nicht, wie ich beweisen soll, dass die Teilbäume eine Blätternanzahl von 2^(h-1) haben.
Außerdem bin ich mir auch nicht sicher wie ich den Beweis formal korrekt aufschreiben soll...
Ich wäre sehr dankbar für eure Hilfe!
LG Ic3Cub3
|
|
|
| Zeige Beiträge 1 bis 6 von 6 Treffern |
|
|
|
