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