Transcript
Algorithmen und Datenstrukturen Große Übung #4
Christian Scheffer
Jan-Marc Reinhardt
17.12.2015
Programm für heute
1. Binäre Suchbäume, insbesondere AVL-Bäume 2. Dynamische Arrays
1 / 35
Binäre Suchbäume
2 / 35
Definition: Gewurzelter Baum
I
Gerichteter Baum T = (V, A) mit
I
ausgezeichnete Wurzel w mit Eingangsgrad 0 und
I
Eingangsgrad 1 für alle v ∈ V \ {w}
w
3 / 35
Darstellung & Bezeichnungen
w
Vater H¨ ohe (hier 3)
Kinder
Bl¨ atter
4 / 35
Eigenschaften 1
I
Jeder gerichtete Baum hat einen Knoten mit Eingangsgrad 0 (d.h. eine potentielle Wurzel).
Beweis Annahme: Es existiert ein gerichteter Baum T = (V, A) ohne Knoten mit Eingangsgrad 0. Wähle v ∈ V . Betrachte die Sequenz v = v0 , v1 , v2 , . . . , vn , wobei vi der Vater von vi−1 ist (für alle 1 ≤ i ≤ n). Mindestens ein Knoten muss in dieser Sequenz zweimal auftreten. Sei u der Knoten, der zuerst zweimal auftritt. Betrachte die Teilsequenz vom ersten Auftreten von u zum zweiten Auftreten in umgekehrter Reihenfolge. Dies ist ein Kreis in T – ein Widerspruch dazu, dass T ein Baum ist.
5 / 35
Eigenschaften 2 I
In einem gewurzelten Baum T gibt es einen eindeutigen Weg von der Wurzel zu jedem anderen Knoten.
(Teil-)Beweis Annahme: Für einen Knoten v gibt es zwei unterschiedliche Wege A = (w = a0 , a1 , . . . , an = v) und B = (w = b0 , b1 , . . . , bm = v) von der Wurzel w zu v. Betrachte den vom Ende gezählt letzten Knoten u, der in beiden Sequenzen gleich ist (d.h. ai = bj = u, i, j > 0). Dann hat u zwei unterschiedliche Väter, ai−1 und bj−1 , im Widerspruch dazu, dass T ein gewurzelter Baum ist. Selbst überlegen: Warum gibt es überhaupt für jeden Knoten v einen Weg von w zu v?
6 / 35
Binäre Suche
Suche nach 10!
2
5
7 11 15 16 23 34 35
I
Voraussetzung: Elemente sortiert (Totalordnung)
I
Resultat: Suche hat O(log n) Laufzeit
I
Aber: Arrays erlauben kein (schnelles) Einfügen
7 / 35
Binäre Suchbäume
3
2
1
7
5
8
I
Gewurzelter Baum mit
I
höchstens zwei Kindern pro Knoten (linkes/rechtes Kind),
I
Schlüsseln, im linken Teilbaum ≤, im rechten >.
6
8 / 35
Definitionen
I
In einem vollen binären Baum hat jeder Knoten entweder 0 oder 2 Kinder.
I
Ein binärer Baum ist vollständig, wenn er voll ist und alle Blätter dieselbe Entfernung zur Wurzel haben.
9 / 35
Satz
I
Ein vollständiger binärer Baum der Höhe h hat 2h−1 Blätter.
Beweis per Induktion über h Für h = 1 hat ein binärer Baum nur einen Knoten, der gleichzeitig ein Blatt ist. Angenommen, jeder vollständige binäre Baum der Höhe h − 1 hat 2h−2 Blätter. Einen vollständigen binären Baum der Höhe h erhält man aus einem der Höhe h − 1, indem man jedem Blatt 2 Kinder gibt. Dies ergibt 2 · 2h−2 = 2h−1 Blätter. Selbst überlegen: Ein vollständiger binärer Baum der Höhe h hat 2h − 1 Knoten.
10 / 35
Speicherung im Rechner
S0 / S1
S2
...
...
/
...
11 / 35
Traversierung
3
2
1
7
5
8
I
in-order: 1, 2, 3, 5, 6, 7, 8
I
pre-order: 3, 2, 1, 7, 5, 6, 8
I
post-order: 1, 2, 6, 5, 8, 7, 3
6
12 / 35
Operationen: Search(6)
3
≥6
2
1
<6
<6
7
5
8
6
=6
13 / 35
Operationen: Minimum, Maximum
3
3
2
1
7
5
2
8
6
1
7
5
8
6
14 / 35
Operationen: Predecessor(7), Predecessor(5)
3
3
2
1
7
5
2
8
6
1
7
5
8
6
15 / 35
Operationen: Successor(3), Successor(6)
3
3
2
1
7
5
2
8
6
1
7
5
8
6
16 / 35
Operationen: Insert(4)
3
2
7
1
5
4
8
6
17 / 35
Operationen: Delete(2)
3
3
2
1
7
5
1
8
6
7
5
8
6
18 / 35
Operationen: Delete(3)
3 5 2
7 2
1
5
7
8 1
6
8
6 Selbst überlegen: Warum funktioniert das immer?
19 / 35
Laufzeit I
Jeweils O(h), wobei h die Höhe des Baumes ist
I
Ist das gut? 1 2 3 4 5 6 7 8 20 / 35
AVL-Bäume Definition Ein binärer Suchbaum heißt höhenbalanciert (oder AVL-Baum), wenn sich für jeden Knoten die Höhe der Kinder um höchstens 1 unterscheidet. 4 3 2
3 7
2 1
2 1
1 5
8
1 6 21 / 35
AVL-Bäume cont’d
Satz aus der Vorlesung Die Höhe eines AVL-Baumes mit n Knoten ist in O(log n). I
Wie erhalten wir die AVL-Eigenschaft beim Einfügen und Löschen?
I
Lokal restrukturieren!
22 / 35
Insert(0)
4
4
3
3 3 2 2
1
8
7 1
0
2 2
1 5
8
1
1 0
1
1 5
3 1
7 2
1
2
3
6
6
23 / 35
Restructure
I
Sei v der eingefügte/entfernte Knoten.
I
z ist der erste unbalancierte Knoten auf dem Weg von v zur Wurzel.
I
y ist das höhere Kind von z.
I
x ist das höhere Kind von y (falls gleich hoch: beliebig).
I
Sei a ≤ b ≤ c die Größensortierung von x, y, z und T0 , T1 , T2 , T3 die Größensortierung der Teilbäume an den übrigen Kindern von x, y, z.
I
Dann: Ersetze z durch b mit linkem Kind a, rechtem Kind c und hänge die Teilbäume T0 und T1 als linkes/rechtes Kind an a und T2 und T3 als linkes/rechtes Kind an c.
24 / 35
Fall 1
z y y
T0
z
x
x
T1
T0 T2
T1
T2
T3
T3
25 / 35
Fall 2
z y y
T3 x
x
T0 T0
z
T2 T1
T2
T3
T1
26 / 35
Fall 3
z x y
T0
y
z x
T3 T0
T1
T1
T2
T3
T2
27 / 35
Fall 4
z x y
T3 y
z
x
T0
T0 T1
T1
T2
T3
T2
28 / 35
Delete(2) 3
z 5
1
7
y 3
5
x
7
8 1
6
8
6 I
Achtung: Nach dem Löschen können durch Restructure weitere Knoten unbalanciert werden.
I
Weiter restrukturieren! (Insgesamt maximal O(log n) mal) 29 / 35
Dynamische Arrays
30 / 35
Arrays vs. verkettete Listen
A A[0]
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
L I
Arrays: schneller wahlfreier Zugriff (O(1)), feste Größe
I
Listen: dynamische Größe, langsamer Zugriff (O(n))
31 / 35
Idee: dynamische Arrays
I
I
Bei vollem Array einfach in ein größeres verschieben!
0
1
2
3
0
1
2
3
4
Viele unterschiedliche Bezeichnungen: Vector (C++), ArrayList (Java), list (Python), . . .
32 / 35
Laufzeit für eine Einfügeoperation
I
Im schlimmsten Fall Ω(n)
I
Aber: oft nur O(1)
I
Spannende Frage: Wie oft?
I
Wenn man die Größe des Arrays immer verdoppelt, müssen n/2 Objekte eingefügt werden bevor n Objekte verschoben werden.
I
Im Mittel müssen für jedes eingefügte Objekt zwei verschoben werden.
I
Amortisierte Zeit O(1)
33 / 35
Vor- und Nachteile
Vorteile: I
wahlfreier Zugriff in O(1)
I
Einfügen in O(1) amortisierter Zeit
I
Räumliche Lokalität
Nachteile: I
Worst Case: Ω(n) Zeit für eine Einfügeoperation
I
ggf. viel verschwendeter Platz
34 / 35
Fragen?
Schöne Weihnachtsferien!
35 / 35
