# AD Aufgabe 4
## A Handprotokoll Rot-Schwarz-Baum
Konstruieren Sie für die Eingabe A N G E L S P I T Z den Rot-Schwarz-Baum. Zeichnen Sie
dazu alle Zwischenschritte bis zum 5’ten Schritt einschließlich.
---
Großbuchstaben sind schwarz
Kleinbuchstaben sind rot
1.
root einfügen
```
A
```
2.
$n$ einfügen
```
A
\
n
```
Linksrotation
```
N
/
a
```
3.
$g$ einfügen
```
N
/
a
\
g
```
Linksrotation
```
N
/
g
/
a
```
Rechtsrotation
```
G
/ \
a n
```
Farbwechsel
```
G
/ \
A N
```
4.
$e$ einfügen
```
G
/ \
A N
\
e
```
Linksrotation
```
G
/ \
E N
/
a
```
5.
$l$ einfügen
```
G
/ \
E N
/ /
a l
```
## B Schlechteste / beste Eingabe für einen Rot-Schwarz-Baum
1. Wie müsste eine Eingabe für einen Rot-Schwarz-Baum aussehen, der nur mit Farbwechsel die Balance wiederherstellt? Zeigen Sie Ihre Behauptung mit Hilfe der Eingabe aus A.
---
Anname die Eingabe aus A sind die ersten 5 Buschstaben von (A N G E L S P I T Z).
Die optimale Eingabe ist GENAL, resultierend aus dem folgenden Algorithmus.
+ Füge Menge der Eingabeelemente einer Liste hinzu.
+ Solange die Liste nicht leer ist, wiederhole:
+ Entnehme erste Menge der Liste von Mengen
+ Wähle daraus größeres mittleres Element, füge es der Ausgabe an.
+ Hänge Menge der Elemente kleiner des gewählten Elements der Liste hinzu
+ Hänge Menge der Elemente größer des gewählten Elements der Liste hinzu
``` python
def best_input(input):
lists = [input]
output = []
while lists is not []:
list = lists.pop()
median = get_median(list)
output.append(median)
bigger = []
smaller = []
for e in list:
if e < median:
smaller.append(e)
if e > median:
bigger.append(e)
if smaller is not []:
lists.append(smaller)
if bigger is not []:
lists.append(bigger)
return output
def get_median(list):
"""
:return the median Element. (If there are tow, return the bigger one)
"""
```
```
G
```
```
G
/
e
```
```
G
/ \
E N
```
```
G
/ \
E N
/
a
```
```
G
/ \
E N
/ /
a l
```
Optimale eingabe für (A N G E L S P I T Z) ist NGTELSZAIP.
2. Welche Eingabe löst in einem Rot-Schwarz-Baum die meisten Rotationen aus? Zeigen Sie Ihre Vermutung am Beispiel von 7 Schlüsseln.
---
A N G E L S P
AEG L NPS
4: acbd
```
-> b false
left: b -> a false
right: b -> d false
left: d -> c true
```
5: acbed
```
-> d false
left: d -> b true
left: b -> a false
right: b -> c false
right: d -> e false
```
6: acbedf
```
-> d false
left: d -> b true
left: b -> a false
right: b -> c false
right: d -> f false
left: f -> e true
```
7: acbgfed -> 12
```
-> d false
left: d -> b false
left: b -> a false
right: b -> c false
right: d -> f false
left: f -> e false
right: f -> g false
```
8: acbgfedh
```
-> d false
left: d -> b false
left: b -> a false
right: b -> c false
right: d -> f false
left: f -> e false
right: f -> h false
left: h -> g true
```
Nach Betrachtung dieser Eingaben scheint es als würden die meisten Rotationen auftreten wenn man den neuen Knoten möglichst weit unten rechts einfügt.
3. Geben Sie ein Beispiel für einen Rot-Schwarz-Baum der Größe 𝑁 (𝑁 > 7), in dem die Anzahl der Vergleiche 2 ∗ ⌊log2 𝑁⌋ und das 𝑁 minimal ist. Beginnen Sie mit 𝑁 > 4 und versuchen Sie Ihre Beobachtungen zu übertragen.
---
$N = 6 > 4$, $2*\lfloor log2(6)\rfloor = 4, Vergleiche 4$
```
s
/ \
r s
/
s
/
r
```
$N = 15 > 7$, $2*\lfloor log_2(15)\rfloor = 6, Vergleiche 6$
```
s
/ \
r s
/ \ / \
s ss s
/ \ /\
r ss s
/ \
s s
/
r
```
## D Handprotokoll lineares Sondieren
Gegeben die Eingabe (A,0) (R,1) (I,2) (C,3) (H,4) (N,5) (O,6) (S,7), sowie die Hashwerte für die Schlüssel für unterschiedliche 𝑀. Vervollständigen Sie die nach folgende Tabelle. Achten Sie darauf, dass ab einem gewissen Wert für 𝑁 die Tabelle vergrößert wird und sich damit auch der Wert von 𝑀 ändert.
| N | key | $hash_8$ | $hash_{16}$ | val |
|---|-----|----------|-------------|-----|
| 1 | A | 1 | 1 | 0 |
| 2 | R | 2 | 2 | 1 |
| 3 | I | 1 | 9 | 2 |
| 4 | C | 3 | 3 | 3 |
| 5 | H | 0 | 8 | 4 |
| 6 | N | 6 | 14 | 5 |
| 7 | O | 7 | 15 | 6 |
| 8 | S | 3 | 3 | 7 |
---
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|-----|---|-------|-------|-------|-------|---|---|---|-------|-------|----|----|----|----|-------|-------|
| key | | **A** | | | | | | | | | | | | | | |
| val | | 0 | | | | | | | | | | | | | | |
| key | | **A** | **R** | | | | | | | | | | | | | |
| val | | 0 | 1 | | | | | | | | | | | | | |
| key | | **A** | **R** | **I** | | | | | | | | | | | | |
| val | | 0 | 1 | 2 | | | | | | | | | | | | |
| key | | **A** | **R** | **I** | **C** | | | | | | | | | | | |
| val | | 0 | 1 | 2 | 3 | | | | | | | | | | | |
| key | | **A** | **R** | **C** | | | | | **H** | **I** | | | | | | |
| val | | 0 | 1 | 3 | | | | | 4 | 2 | | | | | | |
| key | | **A** | **R** | **C** | | | | | **H** | **I** | | | | | **N** | |
| val | | 0 | 1 | 3 | | | | | 4 | 2 | | | | | 5 | |
| key | | **A** | **R** | **C** | | | | | **H** | **I** | | | | | **N** | **O** |
| val | | 0 | 1 | 3 | | | | | 4 | 2 | | | | | 5 | 6 |
| key | | **A** | **R** | **C** | **S** | | | | **H** | **I** | | | | | **N** | **O** |
| val | | 0 | 1 | 3 | 7 | | | | 4 | 2 | | | | | 5 | 6 |
## E Löschen bei linearem Sondieren
Zeigen Sie für die Tabelle unter D, welche Effekte auftreten, wenn Sie
1. das Löschen eines Schlüssels implementieren, indem Sie den Schlüsselwert in dem keys-Array auf null setzen.
---
C aus der Liste löschen.
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|-----|---|-------|-------|-------|-------|---|---|---|-------|-------|----|----|----|----|-------|-------|
| key | | **A** | **R** | **C** | **S** | | | | **H** | **I** | | | | | **N** | **O** |
| val | | 0 | 1 | 3 | 7 | | | | 4 | 2 | | | | | 5 | 6 |
| key | | **A** | **R** | | **S** | | | | **H** | **I** | | | | | **N** | **O** |
| val | | 0 | 1 | | 7 | | | | 4 | 2 | | | | | 5 | 6 |
Suche $S$: $hash_{16}(S) \equiv 3 , keys[3] \equiv null$ -> S nicht in der Hashtable.
2. das Löschen eines Schlüssels implementieren, indem Sie Schlüssel eines Clusters rechts des gelöschten Schlüssels um eine Position nach links kopieren.
---
A aus der Liste löschen.
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|-----|---|-------|-------|-------|-------|---|---|---|-------|-------|----|----|----|----|-------|-------|
| key | | **A** | **R** | **C** | **S** | | | | **H** | **I** | | | | | **N** | **O** |
| val | | 0 | 1 | 3 | 7 | | | | 4 | 2 | | | | | 5 | 6 |
| key | | **R** | **C** | **S** | | | | | **H** | **I** | | | | | **N** | **O** |
| val | | 1 | 3 | 7 | | | | | 4 | 2 | | | | | 5 | 6 |
Suche $C$: $hash_{16}(C) \equiv 3 , keys[3] \equiv S , S ≠ C, keys[4] \equiv null$ -> C nicht in der Hashtable.
## F Hashcodes und Hashfunktion
1. Geben Sie für eine Hashfunktion, die die Hashwerte von Gleitkommazahlen durch Multiplikation mit 𝑀 und anschließendes Abrunden berechnet, Beispiele für eine schlechte Schlüsselverteilung.
---
Ziel sind große Cluster, hier zu erreichen durch geringe Abweichungen der Schlüssel bei möglichst kleinem M.
$hash_8(0.0944)=0$
$hash_8(0.1522)=1$
$hash_8(0.2864)=2$
$hash_8(0.1047)=0$
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|-----|------------|------------|-------------|------------|---|---|---|---|---|
| key | **0.0944** | **0.1522** | **0.2864** | **0.1047** | | | | | |
| val | A | B | C | D | | | | | |
$R = \{ x | 1 < x < 1+10^{-M} \}$
2. Gegeben sie für Zeichenketten eine hashCode-Implementierung an, die
1. alle Zeichenketten auf einen Wert abbildet.
---
$hash(x)=0$
``` java
public int hash(Sting s) {
return 0;
}
```
2. Zeichenketten garantiert ungleichmäßig verteilt, wenn die Schlüssel der üblichen Verteilung der Wörter einer Sprache entsprechen.
---
``` java
public int hash(String s) {
int hash = 0;
int R = 31;
int M = Integer.MAX;
for(int i = 0; i < s.length(); i++) {
hash = (R * hash + s.charAt(i)) % M;
}
}
```
3. Worauf verlässt sich die Hashfunktion in Java in der Hashtabellen-Implementierung, damit die Schlüsselverteilung möglichst gleichmäßig streut?
---
Die Hashtable.rehash Funktion verlässt sich darauf, dass Keys ein gleichmäßig streuende Hashfunktion haben. Auch vergrößert sie die Hashtabelle sobald diese halbvoll ist und verringert somit den Lastfaktor $∝$.
## G Einzelfragen
1. Was bedeutet 𝛼 für lineare Sondierung?
---
Für die größe der Cluster.
2. Wofür steht 𝛼 bei Hashing mit Verkettung?
---
Für die größe der Verkettetenlisten.
3. Können Sie, auch wenn Ihre Schlüsselmenge nicht 100% gleichverteilt ist aber die Hashwerte um den optimalen Wert schwanken, dennoch eine Abschätzung für die maximale Listenlänge bei Hashing mit Verkettung angeben? Auf welcher theoretischen Überlegung basiert diese Abschätzung?
---
Ja. Die Abschätzung über die maximale Listenlänge basiert auf der Binomialverteilung. Es wurde experimentel geziegt das dies auch für nicht 100%ige Gleichverteilungen gilt.
4. Welche Größe beeinflusst die Clusterbildung bei linearer Sondierung? Wo findet sich diese Größe in der Implementierung der LinearProbingHashST wieder?
---
Der Lastfaktor $∝$ beeinflusst die Clusterbildung. Er berechnet sich als $∝=\frac{N}{M}<1$.
In der Implementierung der LinearProbingHashST wird beim Einfügen die Arraygröße verdoppelt, wenn $N ≥ \frac{M}{2}$ ist, was dazu führt das $∝$ nicht größer werden kann als $0.5$.
5. Welcher Zustand darf in einer LinearProbingHashST nie eintreten?
---
Im LinearProbingHashST darf niemals $N>M$ eintreten. In dem Fall ist im Array kein Platz mehr für das einzufügende Element. Dieser Fall kann aber, abhängig von der Implemntierung der resize-Funktion, nicht eintreten.
6. Sie kennen die maximale Schlüsselanzahl (Schlüssel sind alle unterschiedlich), die in eine Hashtabelle mit Verkettung eingetragen wird. Können Sie dann in jedem Fall eine Empfehlung für die Größe 𝑀 der Hashtabelle angeben? Begründen Sie die Antwort.
---
$N\equiv M$
Da die Schlüssel alle unterschiedlich sind können wir davon ausgehen das die Wahrscheinlichkeit jeden Schlüssel in eine eigene Liste einzuordnen bei nahezu 100% liegt. (Siehe Skript Satz 3-K)
Daraus resultiert eine Hashtabellengröße von $N$.
Falls mehrere Schlüssel doch den selben Hashwert haben, wird eine Liste etwas länger. Aber das ist nicht so ein großes Problem wie bei der linearen Sondierung, da die Nachberindices nicht betroffen sind.
7. Wann würden Sie für Hashing mit Verkettung dynamisches Hashing empfehlen? Würde dynamisches Hashing die Größe der längsten Liste in jedem Fall verkürzen? Begründen Sie Ihre Antwort.
---
Dynamisches Hashing würden wir empfehlen wenn N unbekannt ist oder sich stark ändert. Wenn N unbekannt ist, ist es nicht möglich ein passendes M zu wählen. Wenn N sich stark ändert, kann viel Speicherplatz mit resizing gespart werden.
Dynamisches Hashing verkürzt die längste Liste nicht wenn die Hashfunktion suboptimal, wie z.B. $hash(x)=0$, ist. In diesem Fall sind alle Elemente in der ersten Liste, egal wie gorß $M$ ist.
Sign in with Wallet
Connect another wallet