tree

#Definition #IntroProg #Informatik #MINTgrün #Studium

Bäume

Definition

Ein Baum ist eine hierarchische Datenstruktur, die aus Knoten besteht. Es gibt einen einzigen Wurzelknoten, von dem aus jeder andere Knoten über genau einen Pfad erreichbar ist. Jeder Knoten kann mehrere Kindknoten haben, wobei die Anzahl der Kindknoten je nach Baumtyp variieren kann:

Binärer Baum: Jeder Knoten hat höchstens zwei Kindknoten (linkes und rechtes Kind).
Allgemeiner Baum: Jeder Knoten kann eine beliebige Anzahl von Kindknoten haben.

Definition

Ein t-ärer Baum ist entweder die leere Menge oder ein Knoten (ein Objekt), welcher ein Datum und t Kindbäume enthält, welche t-äre Baume sind.

Definition

Ein Binär-Baum ist formal auch ein 2-ärer Baum.

Knotenorientierte Bäume: Daten liegen in den Knoten.
- z.B. Speicherung von unterschiedlich großer Werte
Blattorientierte Bäume: Daten liegen nur in den Blättern. − Innere Knoten enthalten nur Zugriffsinformation
Kantenorientierte Bäume: Daten in den Kanten
- z.B. sind auf einer Karte die Kanten Entfernungen

Warum gibt es trees?

grundlegendes Problem der Programmierung:
- Speicherung von Datensätzen
- Listen oft nicht ausreichend, da O(n) zu langsam ist (suchen, einfügen, löschen, etc.).
Beispiele
- Stammbaum
- Dateisysteme
- Entscheidungsbäume
- Suchbäume, z.B. für Lexikon, Daten
- Rekursionsbäume
Anforderungen an Datenstruktur
- Schneller Zugriff, d.h. schneller als O(n)
- Schnelles Einfügen neuer Datensätze
- Schnelles Löschen bestehender Datensätze

Binärbaum

!introprog-v05-baeume, p.9

Definition

Ein Binärbaum T ist eine Struktur, die auf einer endlichen Menge definiert ist. Diese Menge nennt man auch die Knotenmenge des Binärbaums.
Die leere Menge ist ein Binärbaum. Dieser wird auch als leerer Baum bezeichnet.
Ein Binärbaum ist ein Tripel $(v, T_{1}, T_{2})$ , wobei $T_{1}$ und $T_{2}$ Binärbäume mit disjunkten Knotenmengen $V_{1}$ und $V_{2}$ sind, d.h. Und $V_{1} \cap V_{2} = \emptyset$ , und $v \notin V_{1} \cup V_{2}$ Wurzelknoten heißt. Die Knotenmenge des Baums ist dann ${v} \cup V_{1} \cup V_{2}$ . $T_{1}$ heißt linker Unterbaum von $v$ und $T_{2}$ heißt rechter Unterbaum von $v$ .

häufig lässt man die leeren Bäume in der Darstellung eines Binärbaums weg

Liste der Begriffe

Begriff	Erläuterung	Beispiel
Vorgänger (predecessor)	-	A ist Vorgänger von B
Nachfolger (successor)	-	B ist Nachfolger von A
Wurzel (root)	kein Vorgänger	A
Blatt (leaf)	kein Nachfolger	D, H, I, J, K
interner Knoten (inner node)	alle Nachfolger besetzt	A, B, C, G
Randknoten (boundary node)	nicht alle Nachfolger besetzt	D, E, F, H, I, J, K
Pfad (path)	Knotenfolge von einem Anfangs-	Pfad von der Wurzel nach F: A, C, F
	bis zum Endknoten
Pfadlänge (path length)	Anzahl der Kanten des Pfads	Pfadlänge von A nach F: 2
Tiefe eines Knotens (depth)	Pfadlänge zur Wurzel	Tiefe von F: 2
Höhe eines Baumes (height)	Größte Tiefe	3
Höhe eines Knotens v	Höhe des Teilbaums von v	Höhe von F: 1

Darstellung im Rechner

Schlüssel key und ggf. weitere Daten
Zeiger lc(v) bzw. rc(v) auf linkes bzw. rechtes Kind von v
Elterzeiger p(v) auf Vater/Mutter von v (blau) −
Wurzelzeiger root(T)
!introprog-v05-baeume, p.13

Binäre Suchbäume

Verwende Binärbäume
Speichere Schlüssel "geordnet"
Binäre Suchbaumeigenschaft
- Sei x ein Knoten im binären Baum
- Ist y ein Knoten im linken Unterbaum von x, dann gilt key(y) ≤ key(x)
- Ist y ein Knoten im rechten Unterbaum von x, dann gilt key(y) > key(x)
unterschiedliche Suchbäume
- !introprog-v05-baeume, p.15
- Schlüsselmenge: 3,4,6,7,7,9
- Wirerlauben mehrfache Vorkommen desselben Schlüssels

Operationen

Durchlaufen

Gegeben binärer Suchbaum
Wie kann man alle Schlüssel aufsteigend sortiert in O(n) Zeit ausgeben

Inorder-Tree-Walk(x)          //Aufruf über Inorder-Tree-Walk(root(T))
1. if x ≠ nil then
2.    Inorder- Tree-Walk(lc(x))
3.    Ausgabe key(x)
4.    Inorder-Tree-Walk(rc(x))

Laufzeit
- Ausgeben aller Schlüssel
  - Gegeben binärer Suchbaum
  - Wie kann man alle Schlüssel aufsteigend Sortiert in O(n) Zeit ausgeben?
  - !introprog-v05-baeume, p.56
  - Der Algorithmus ist optimal. Schneller gehts nicht

Suchen – Rekursiv

1. if x =nil or k=key(x) then return x
2. if k<key(x) then return Baumsuche(lc(x),k) // Entweder links
3. else return Baumsuche(rc(x),k)             // oder rechts

funktioniert nur, wenn sortiert
Laufzeit
- wenn Suchbaum balanciert ist O(h)
- Höhe h von Baum ist Zweierpotenz aber umgekehrt, also log* (Anzahl Knoten)
- Laufzeit ist durch Höhe beschränkt

Suchen – Iterativ

IterativeBaumsuche(x,k)
1. while x ≠ nil and k ≠ key(x) do
2.    if k < key(x) then x ← lc(x)
3.    else x ← rc(x)
4. return x

MIN/MAX Suche

MinimumSuche(x)
1. ehile lc(x) ≠ nil do x ← lc(x)
2. return x

MaximumSuche(x)
1. while rc(x) ≠ nil do x ← rc(x)
2. return x

Nachfolgersuche

Nachfolger bzgl. Inorder-Tree-Walk
Wenn alle Schlüssel unterschiedlich, dann ist das der nächstgrößere Schlüssel (nicht notwendigerweise das direkte nächste Kind!)
Fall 1 (rechter Unterbaum von x nicht leer): Dann ist der linkeste Knoten im rechten Unterbaum der Nachfolger von x
Fall 2 (rechter Unterbaum von x leer und x hat Nachfolger y): Dann ist y der erste Knoten auf dem Pfad zur Wurzel, der größer als x ist

Nachfolgersuche(x)
1. if rc(x) ≠ nil then return Minimumsuche(rc(x))
2. y ← p(x)
3. while y ≠ nil and x=rc(y) do
4.    x ← y
5.    y ← p(y)
6. return y

Vorgängersuche

Analog zur Nachfolgersuche
Daher ebenfalls O(h) Laufzeit

Einfügen

Ähnlich wie Baumsuche: Finde Blatt, an das neuer Knoten angehängt wird
Danach wird nil-Zeiger durch neues Element ersetzt

Einfügen(T,z) 
1. y ← nil; x ← root(T) 
2. while x ≠ nil do 
3.    y ← x 
4.    if key(z) <= key(x) then x ← lc(x) 
5.    else x ← rc(x) 
6. p(z) ← y 
7. if y=nil then root(T) ← z 
8. else 
9.    if key(z)<= key(y) then lc(y) ← z 
10.   else rc(y) ← z

Löschen

gegeben: binärer Suchbaum und zu löschendes Element z
3 unterschiedliche Fälle
1. Zu löschendes Element z hat keine Kinder
  !250
  - entferne Element z
2. Zu löschendes Element z hat ein Kind
  !250
  - ersetze Element z durch das Kind
3. Zu löschendes Element z hat zwei Kinder
  !250
  1. Bestimme Nachfolger von z
  2. Entferne Nachfolger von z
  3. Ersetze z durch Nachfolger

Pseudocode

Löschen(T, z)
1. if lc(z) = nil or rc(z) = nil then y ← z
2. else y ← NachfolgerSuche(z)
3. if lc(y) ≠ nil then x ← lc(y)
4. else x ← rc(y)
5. if x ≠ nil then p(x) ← p(y)
6. if p(y) = nil then root(T) ← x
7. else if y = lc(p(y)) then lc(p(y)) ← x
8. else rc(p(y)) ← x
9. key(z) ← key(y)

Höhe eines Binärbaumes

Definition

Die Höhe eines Binärbaumes mit Wurzel v ist die Länge (Anzahl der Kanten) des längsten einfachen Weges (keine mehrfach vorkommenden Knoten) von der Wurzel zu einem Blatt #Definition

Beispiel
- Ein Baum hat die Höhe 0
- Damit gilt: !100
  - Höhe eines Baumes mit Wurzel v und Teilbäumen A und B ist 1 + max(Höhe(A), Höhe(B))
- Baum der Höhe 3: !100

Dynamische Bäume

Ein Grundlegendes Datenbank-Problem
- Speicherung von Datensätzen
Beispiel
- Kundendaten (Name, Adredse, Wohnort, Kundennummer, offene Rechnungen, offene Bestellungen,…)
Anforderungen
- Schneller Zugriff
- Schnelles Einfügen neuer Datensätze
- Schnelles Löschen bestehender Datensätze

Dynamische Baumoperationen

Binäre Suchbäume
- Aufzählen der Elemente mit Inorder-Tree-Walk in O(n) Zeit
- Suche in O(h) Zeit
- Minimum/Maximum in O(h) Zeit
- Vorgänger/Nachfolger in O(h) Zeit
Dynamische Operationen?
- Einfügen und Löschen
- Müssen Suchbaumeigenschaft aufrecht erhalten
- Auswirkung auf Höhe des Baums?

Traversierung von Bäumen

Definition

Die Traversierung eines Baum beschreibt die Reihenfolge in der alle Knoten eines Baumes besucht werden

Pre-order: Knoten -> Links -> Rechts
Post-order: Links -> Rechts -> Knoten
In-order: Links -> Knoten -> Rechts
Level-order: Schicht nach Schicht von der Wurzel aus

Tiefen- und Breitensuche in Bäumen

!AlgoDat-LectureNotes, p.62

Kernkonzept

Tiefensuche in Bäumen

Bei der Tiefensuche (depth-first search) geht die Suche zunächst in die Tiefe und erst mit niedrigerer Präferenz in die Breite.
Man geht von einem Knoten zu dem Nachfolger, von dort wieder zu dessen Nachfolger usw. bis man an ein Blatt stößt. Dann geht man einen Schritt zurück und besucht den nächsten Nachfolger.
!AlgoDat-LectureNotes, p.58

Breitensuche in Bäumen

Bei der Breitensuche (breadth-first search) geht die SUche zunächst in die Breite und erst mit niedrigere Präferenz in die Tiefe.
Man geht von einem Knoten der Reihe nach zu allen direkten Nachfolgern und erst dann zu deren Nachfolgern.
!AlgoDat-LectureNotes, p.58

Pseudocode

Tiefensuche:

1 // Tiefensuche
2 D : ein Stapel ([[Stack]])
3 D ← {Wurzel}
4 while D̸ = ∅
5   v ← D.get () // pop()
6   besuche Knoten v
7   for all w Nachfolger von v
8     D.put(w) // push()
9   end
10 end

Rekursive Tiefensuche:

1 procedure DFS(v)
2   besuche Knoten v
3   for all w Nachfolger von v
4     DFS(w)
5   end
6 end
7
8 Aufruf durch: DFS( Wurzel )

Breitensuche:

1 // Breitensuche
2 D : eine Warteschlange (Queue)
3 D ← {Wurzel}
4 while D̸ = ∅
5   v ← D.get () // dequeue()
6   besuche Knoten v
7   for all w Nachfolger von v
8     D.put(w) // enqueue()
9   end
10 end