View
225
Download
6
Category
Preview:
Citation preview
Binärbäume
2
BaumWurzelKnoten ohne Vorgänger
KnotenbeinhaltenDatenz.B. Zahlen Innerer Knoten
Kein Blatt
Blatt Knoten ohne Nachfolger
AstKante
Ein Baum ist eine Datenstruktur die folgende Eigenschaften besitzt: Es gibt genau einen Knoten, der keinen
Vorgänger besitzt. Dieser wird als Wurzel bezeichnet.
Alle Knoten des Baumes, außer Wurzel besitzen genau einen Vorgängerknoten.
Ein Baum ist eine rekursive Datenstruktur ⇒ Der Baum besteht aus einer Wurzel und einer Reihe von Teilbäumen.
Baum
4
BinärbaumBinärbaum ist entweder ein leerer Baum
oder er besteht aus einer Wurzel und zwei Binärbäumen.
Begriffe:
Knoten, Wurzel, innerer Knoten, Blatt, Ast
Knoten sind die eigentlichen Elemente, die über alle Informationen wie Daten und Zeiger zum rechten und linken Knoten verfügen.
Wurzel – Dieser Knoten ist der einzige, der keinen Vorgänger besitzt.
Ast = Kante. Die Knoten werden mit einem Ast verbunden.
Blatt – Blätter sind Knoten, die keinen Nachfolger besitzen.
Begriffe
Binärer Suchbaum - AufbauFür jeden Knoten K eines Suchbaumes gilt: Die Schlüssel im linken Teilbaum von K sind kleiner als der Schlüssel von K Die Schlüssel im rechten Teilbaum von K sind größer als der Schlüssel von K
Schlüssel ist die Zahl im Knoten
Was passiert, wenn eine Zahl doppelt vorkommen würde?
Binärer Suchbaum - AufbauFür jeden Knoten K eines Suchbaumes gilt: Die Schlüssel im linken Teilbaum von K sind kleiner oder gleich als der Schlüssel von K Die Schlüssel im rechten Teilbaum von K sind größer als der Schlüssel von K
Es sind folgende Schlüssel gegeben bauen Sie einen Baum 5,2,3,1,8,9
Suchbaum erstellen
Es sind folgende Schlüssel gegeben bauen Sie einen Baum 5,2,3,1,8,9
Suchbaum erstellen
5
2
318
9
Es sind folgende Schlüssel gegeben bauen Sie einen Baum 5,12,3,1,8,7,15,4,3
Suchbaum erstellen
Es sind folgende Schlüssel gegeben bauen Sie einen Baum 5,12,3,1,8,7,15,4,3
Suchbaum erstellen
5
41
123
8
7
15
3
In einem binären Suchbaum kann man Zahlen schnell finden.
Finde die 9
Warum Suchbaum
5
2
318
9
Wie viele Elemente (Knoten) gab es? 6 Wie viele Vergleiche mussten wir machen? 3 Wie viele müssten wir im Besten Fall machen müssen? Wie viele im schlimmsten Fall?
Zeitkomplexität 5
2
318
9
7 wäre rechts von 5 8 ist größer, also müsste die 7 links stehenLinks ist kein Weg => 7 gibt es nicht!
Suche die Zahl 7
5
2
318
9
Wie viele Vergleiche mussten wir machen? 2 Wie viele müssten wir im Besten und im
schlimmsten Fall machen?
Suchbaum ist effektiv beim Suchen (auch wenn die gesuchte Zahl nicht vorhanden wird).
Zeitkomplexität 5
2
318
9
Den kleinsten (bzw. größten) Schlüssel im Suchbaum findet man, indem man solange in den linken (bzw. rechten) Teilbaum absteigt, bis man nicht mehr weiterkommt.
Minimum und Maximum
Das einfachste: einen Blatt löschen.
Wenn der Knoten ein Kind hat? Z.B. die 8.
Knoten entfernen
5
2
318
9
Wenn der Knoten zwei Kinder hat? Z.B. die 5.Dann kommt an seiner StelleDer rechteste Knoten von linken Teilbaum oder das linkeste Vom rechten Teilbaum.
Knoten entfernen
5
2
318
9
Wenn der Knoten zwei Kinder hat? Z.B. die 5.Dann kommt an seiner StelleDer rechteste Knoten von linken Teilbaum oder das linkeste Vom rechten Teilbaum.
Knoten entfernen
3
2
318
9
Wenn der Knoten zwei Kinder hat? Z.B. die 5.Dann kommt an seiner StelleDer rechteste Knoten von linken Teilbaum oder das linkeste Vom rechten Teilbaum.
Knoten entfernen
8
2
318
9
Es sind folgende Schlüssel gegeben bauen Sie einen Baum 8,5,3,1
Suchbaum erstellen
8
5
13
Was fällt Dir auf?
Auch dieser nicht.
Suchbaum ist nicht balanciert
6
5
13
8
wenn für jeden Knoten gilt: Die Höhe seines linken und rechten Teilbaums unterscheidet sich höchstens um 1.
Bäume sind ausgeglichen (balanciert)
Ausgeglichene (balancierte) Bäume
Wie hoch wird der Baum bei 255 Elementen?
Höhe der balancierten Bäume
5
2
31
8
97
Anzahl Ebenen
Anzahl der Elemente
1 1 21-12 3 22-13 7 23-14 155 316 637 127Anzahl der Ebenen ist log2(255+1).
28 = 256 Anzahl der Ebenen ist 8
Wie hoch wird der Baum bei 9 Elementen?
Höhe der balancierten Bäume
5
3
41
8
97
23 = 824 = 16log2(9+1) = 3,..
=> Drei Ebenen voll und die 4. Ebene wurde angefangen.
21
Höhe der balancierten Bäume
Die Höhe des balancierten Baumes bei n Elementen:
log2(n+1) nach oben gerundet
Alle Levels sind vollständig besetzt (bis auf die unterste Schicht).
Höhe des Baumes log2(n+1). Dies ist die minimale Höhe für alle Suchbäume:
=> Optimaler Zeitaufwand für Suche
Optimal balancierte Bäume
Zeitaufwand für Suche O(log n)
bis zu den Blättern kommen. Der Zeitaufwand entspricht der Höhe des Baumes => log2(n+1)
Es ist deutlich effektiver als in einem Array!
Suchbäume werden in der Praxis oft genutzt beim Wörterbuch, oder Suche beim Google…
Zeitkomplexität
Füge in einen Baum folgende Knoten ein6,1,9,8,4,3,7,11,2
Stelle dar, wie die 7 gesucht wird
Entferne die 2,4 und 6
Aufgabe
https://www.youtube.com/watch?v=xfhfRAccL2w
Traversierungen
PRE-ORDERV-L-R =5 2 1 3 4 8 9
POST-ORDERL-R-V =1 4 3 2 9 8 5
IN-ORDERL-V-R =1 2 3 4 5 8 9
Traversierungen
5
2
318
94
PRE-ORDERV-L-R =5 2 1 3 4 8 9
POST-ORDERL-R-V =1 4 3 2 9 8 5
IN-ORDERL-V-R =1 2 3 4 5 8 9
Traversierungen
5
2
318
94
Der folgende Schlüssel enthält: 12,5,3,1,8,7,15,4
Zahlen zuerst sortieren1,3,4,5,7,8,12,15Diese Reihenfolge muss dem IN-ORDER entsprechen. Danach einen balancierten Baum zeichnen. Dann mit Zahlen füllen.
Gib einen balancierten Baum an
IdeeDie zu sortierende Elemente werden einfach in einem binären Suchbaumgespeichert.
Um die Elemente in einer sortierten Reihenfolge zu erhalten, muss der Baum nur inorder traversiert werden.
Binary Tree Sort
Beim Einfügen eines Elements muss im Suchbaum sein Platz gefunden werden. Suchen benötigt O(log n) Zeit.
Für n Elemente wären das insgesamt O(n log n) Zeit.
Die Inorder-Traversierung benötigt nur O(n).
Die Gesamtlaufzeit beträgt somit O(n log n).
Zeitkomplexität - Binary Tree Sort
Recommended