View
221
Download
0
Category
Preview:
Citation preview
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Diskrete Mathematik I
Binärer Suchbaum IVAVL-Baum I
Vorlesung 8
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 191
• Preorder– Die Wurzel wird vor den Unterbäumen besucht,
die Unterbäume werden von links nach rechts abgearbeitet
• Breitendurchlauf– Mit einem Knoten werden seine Nachbarn
von links nach rechts besucht
Durchlaufstrategien
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16Warteschlan
ge
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
16Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
10 24Ws
16
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
10
10 24Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
10
1424 9Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
10
24 9Ws 14
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
10
9 14Ws 18
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
10
189 14Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
14
10
14 18Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
14
10
18 13Ws 15
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
14
18
10
1518 13Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
14
13
18
10
13 15Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
14
13
18
15
10
15Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192
A 26x
Durchlaufstrategie: Breitendurchlauf
18149
10 24
16
13 15
16
24
9
14
13
18
15
10
Ws
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 193
Durchlaufstrategie: Breitendurchlauf
class BST { ... void Breitendurchlauf() {
SohnListe ws = new SohnListe(); Knoten aktuell;ws.FügeAn(wurzel); while ((aktuell = ws.Entferne()) != null) { System.out.println(aktuell.GibWert()); ws.FügeAn(aktuell.GibLinks()); ws.FügeAn(aktuell.GibRechts()); }
} ...}
A 2x
entf
erne
Test
auf
End
e
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 194
class SohnElem {private Knoten wert; private SohnElem weiter;SohnElem(Knoten k) { wert = k; weiter = null; }void SetzeWert(Knoten k) { wert = k; }Knoten GibWert() { return wert; }void SetzeWeiter(SohnElem s) { weiter = s; }SohnElem GibWeiter() { return weiter; }
}
Breitendurchlauf: SohnElem
knoten (statt int)
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 195
Breitendurchlauf: SohnListe, FügeAn (hinten)class SohnListe {
private SohnElem kopf, fuß;Sohn Liste() {kopf = fuß = null;}void FügeAn(Knoten an) {
SohnElem neu = new SohnElem(an);if (fuß != null) {
fuß.SetzeWeiter(neu);fuß = neu;
}else
kopf = fuß = neu;}
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 196
Breitendurchlauf: Entferne vorne
.
.
.Knoten Entferne() {
Knoten erster = null;if (kopf != null) {
erster = kopf.GibWert(); kopf = kopf.GibWeiter();if (kopf == null)
fuss = null;}return erster;
}}
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197
Vergleich „Binäre Suchbäume“ - „Liste“
• in einem binären Suchbaum findet man schneller ein vorhandenes Objekt
• in einem binären Suchbaum stellt man schneller fest, daß ein Objekt nicht vorhanden ist
• warum?– der Weg vom Kopf zur Wurzel ist im allgemeinen kürzer als der Weg
vom Anfang zum Ende eine Liste– (kann man das genauer, d. h. quantitativ angeben?
• später)• es gibt aber auch ungünstige Fälle, wo der Baum aussieht wie eine Liste• diese Fälle treten stets bei der iterativen Eingabe sortierter Elemente
auf
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 198
Beispiele für den Aufbau binärer Suchbäume
A 7x
Eingabefolge 1-2-3
1
2
3
Eingabefolge 3-2-1
Eingabefolge 2-3-1 oder 2-1-3
2
1 3
Eingabefolge 3-1-2
1
2
3
1
2
3
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
AVL-Baum (Definition)
Ein binärer Baum heißt ausgeglichener Baum oder AVL-Baum (nach Adelson-
Velskij und Landis), falls sich für jeden Knoten k die Höhen h der beiden Teilbäume um höchstens 1 unterscheiden.
9
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1910
AVL-Baum: Beispiel
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1911
Balancefaktor
Balancefaktor bal(k)
bal(k) = h(rechter Teilbaum von k) - h(linker Teilbaum von k)
Für AVL-Bäume gilt: bal(k) { 1,0, 1}
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1912
AVL-Baum: Beispiel
A 2x
0 0
0
+1
+1-1
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1912
AVL-Baum: Beispiel
A 2x
0 0
0
+1
+1-1
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1912
AVL-Baum: Beispiel
A 2x
0
0
+1
+10
+2
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
00
00 0 0
0 +1
+1
26 39
17113
208
33
14
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
00
0
00
0 0
+1
+114
113
8
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
00
0
00
0 0
+1
+114
113
8
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
0
00
000
0 +1
+1
17
20
14
26 39
33113
8
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
0
00
000
0 +1
+1
17
20
14
26 39
33113
8
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
00
000
0
0
+1
0
+114
30
26 39
33113
8
17
20
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
+1
00
0
0
+1
0
0
0
+114
113
8
17
20
30
26 39
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
000
0 +1
-1
0+1
0
+1
17
20
14
113
8
26 39
33
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
000
0 +2
0+1
-1
0
Ausgeglichenheit ist verletzt
+1
17
20
14
113
8
26 39
33
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
000
0 +2
0+1
-1
0Ausbalancierendurch Rotation
+1
17
20
14
113
8
26 39
33
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
0+1
00 0 -1
0 +2
0R- Rotation
+1
26 39
17113
208
33
14
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
000
0 +2
0+1
-1
0
+1
17
20
14
113
8
26 39
33
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
0+1
00 0 -1
0 +2
0
+1
26 39
17113
208
33
14
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
000
0 +2
L- Rotation
+1
17
20
14
113
8
26
30 39
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
000
0 +2
+1
17
20
26
14
113
8
30 39
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
00 0
0 +2
+1
17113
208
26
14
30 39
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
00
0 0
00
0 0
0
+1
26
14
113
8
39
20 33
17 30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
Einfügen von k = 30
A 36x
0
00
0 0
0
0 0
0
+1
113
268
14
17 39
20 33
30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913
Einfügen von Knoten
A 36x
00
00 0 0
0 0
0
+1
39
20113
268
33
14
17 30
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914
Löschen von Knoten
Löschen von k = 8
A 9x
0
00 0 0
0 +1
+1
026 39
17113
208
33
14
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914
Löschen von Knoten
Löschen von k = 8
A 9x
00
00 0 0
0 +1
+1
26 39
17113
208
33
14
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914
Löschen von Knoten
Löschen von k = 8
A 9x
00
0
00
0 0
+1
+1
113
8
14
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914
Löschen von Knoten
Löschen von k = 8
A 9x
0
-1
00
0 0
+1
+1
3
14
11
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914
Löschen von Knoten
Löschen von k = 8
A 9x
0
-1
00
0 0
+1
+1
3
14
11
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914
Löschen von Knoten
Löschen von k = 8
A 9x
0
-1
00
0 0
+1
+1
3
14
11
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
-1
00
0 0
+1
+1
3
14
11
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
-1
00
0 0
+1
+1
3
14
11
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
-1
00
0 0
+1
+1
3
14
11
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
00
0 0
+1
+114
3
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
00
0 0
+1
+2
L- Rotation
14
3
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
00
0 0
+1
+214
3
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
0
00
0 0
+1
+214
3
26 39
17
20
33
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
Löschen von k = 11
A 15x
Löschen von Knoten
00
0
0 0
0
020
173
14
26
33
39
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915
A 15x
Löschen von Knoten
00 0 0
0 0
0
26173
3314
39
20
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1916
L-Rotation
Knoten x wird eingefügt und verletzt dadurch die Ausgeglichenheit an einem
höher gelegenen Knoten k1
Notwendige Korrektur durch L-Rotation (symmetrisch: R-Rotation): Umhängen
von zwei Kanten
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1917
A 7x
L-Rotation
T1T2 T3
k1
k2
0
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1917
A 7x
L-Rotation
T1T2 T3
k1
k2
x
+1
+2
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1917
A 7x
L-Rotation
T1T2 T3
k1
k2
x
+1
+2
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1917
A 7x
L-Rotation
T1T2 T3
k1
k2
x
+1
+2
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1917
A 7x
L-Rotation
T1
k1
k2
x
0
T2
T3
0
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918
LR-Rotation
x wird eingefügt und verletzt dadurch die Ausgeglichenheit an einem höher gelegenen Knoten k1.
Notwendige Korrektur durch LR- Rotation (symmetrisch: RL-, RR- und LL- Rotation): Umhängen von vier Kanten
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
T1
k2
k10-1
T3
T4
k3
T2
0
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
T1
k2
k1
x
+1-2
T3
T4
k3
T2
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
k1
-2
T4T1
k2
x
+1
T3
k3
T2
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
k1
-2
T1
k2
x
+1
T3
T4
k3
T2
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
T1
k2
k1
x
+1-2
T3
T4
k3
T2
+1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
k1
-2
T4
T1
k2
x
-1
T3
k3
T2
-1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
k1
-2
T1
k2
x
-1
T3T4
k3
T2
-1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
T1
k2
k1
x
-1-2
T3T4
k3
T2
-1
Diskrete Mathe11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919
LR-Rotation
A 14x
T1
k2
k1
x
0
0
T3
T4
k3
T2
-1
Recommended