2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 1
Bäume
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 2
Inhalt
• Grundbegriffe: Baum, Binärbaum
• Binäre Suchbäume (Definition)
• Typische Aufgaben
• Suchaufwand
• Löschen allgemein, Methode „Schlüsseltransfer“
• Programmiertechnik
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 3
Baum: Grundbegriffe #1
• Graph: gerichtet, ungerichtet
Komponenten:
Knoten Elemente: Eigenschaften
Kanten Beziehungen zwischen Elementen
• Baum: 1. Spezielfall eines Graphen
2. Verallgemeinerung der Liste
Liste: 1 Element: 1 Nachfolger
Baum: 1 Element: ≥ 1 Nachfolgerd
t-ärer Baum, Baum der Ordnung t
zu jedem Element sind höchstens t Nachfolger festgelegt
t=1 Spezialfall: Liste; t=2 Binärbaum; t=3 Ternärbaum, ...
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 4
Baum: Grundbegriffe #2
• Knotensorten Vorgänger = Vater
Nachfolger = Sohn = Kind
Wurzel Knoten ohne Vorgänger
Blatt=äußerer K. Knoten ohne Nachfolger
innerer Knoten Knoten mit Vorgänger und Nachfolger
Randknoten Knoten mit < t Nachfolger
• Pfad Weg von der Wurzel zu jedem Knoten
• Pfadlänge Anzahl von Knoten im Pfad
• Voller Baum alle Blätter haben die gleiche Pfadlänge
• Quasivoller Baum nur die unterste Ebene ist nicht voll besetzt
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 5
Varianten von Bäumen
• Zahl der Nachfolger: fest oder beliebig
• Sortierung: Ungeordneter Baum: Nachfolger unsortiert
Geordneter Baum: 1., 2., ...,k-ter Nachfolger;
beim Binärbaum: linker, rechter Nachfolger
W
3.
4. 2.3 1.21.
1. 2.
2.1.
Ebene 1
Ebene 2
Ebene 3
W
R
RL
L
RL
Linker Teilbaum von WBeide Beispielsbäume: Höhe h=3
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 6
Einige Beispiele:
• als 2 Felder
• als Struktur (C++:Klasse) mit Zeigern ...
natürlich
Implementierung von Bäumen
v(2) v(3)v(1)
1
32
e(1,1)=0 e(1,2)=1 e(1,3)=1
e(1,1)=0 e(1,2)=0 e(1,3)=0e(2,1)=0 e(2,2)=0 e(2,3)=0
e(3,1)=0 e(3,2)=0 e(3,3)=0
e[i][j]==1 g.d.w. e[j] Nachfolger von e[i]
Knoten: Kanten:
1
32
Knoten-Daten
Knoten-Nr.=1
Knoten-Daten
Knoten-Nr.=2
null null
Knoten-Daten
Knoten-Nr.=3
null null
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 7
Zusammenhänge
• Mit der GraphentheorieEin Baum ist ein gerichteter zusammenhängender
kreisfreier Graph mit einer speziellen Eigenschaft:
Jeder Knoten hat bis auf einen (Wurzelknoten)
genau einen Vorgänger.
• Mit der linearen AlgebraBaum ~ Basis
kreisfrei ~ linear unabhängig
zusammenhängend ~ Erzeugendensystem
Kantenzahl ~ Dimension eines Vektorraumes
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 8
Bäume und lineare Algebra• Satz: Charakterisierung von Bäumen
Es sei G = (V,E) ein endlicher Graph; V ... Knotenmenge, E ... Kantenmenge.
Folgende Eigenschaften sind äquivalent:
(1) G ist ein Baum
(2) G ist kreisfrei, und das Hinzufügen einer beliebigen Kante zu E erzeugt einen Kreis (G ist
maximal kreisfrei)
(3) Zwischen je zwei Knoten gibt es genau einen einfachen Weg in G
(4) G ist zusammenhängend, und die Wegnahme einer beliebigen Kante aus E zerstört den
Zusammenhang von G (G ist minimal zusammenhängend)
(5) G ist kreisfrei und seine Kantenzahl ist |E| = |V| - 1
(6) G ist zusammenhängend und |E| = |V| - 1
• analoge Eigenschaften in Vektorräumen(2) Eine Basis ist eine maximal linear unabhängige Menge, d.h. bei Hinzufügen eines Vektors wird
die Unabhängigkeit zerstört
(4) Eine Basis ist eine minimale Erzeugendenmenge, d.h. bei Wegnahme eines Vektors hat man
kein Erzeugendensystem mehr
(5),(6) In Vektorräumen haben alle Basen eines (endlichdimensionalen) Vektorraumes die gleiche
Größe, nämlich die Dimension des Vektorraumes
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 9
Binärbaum: Grundbegriffe• linker, rechter Nachfolger
• linker, rechter Teilbaum (Unterbaum) eines Knotens
• Ebenen
• Höhe des Baums: Anzahl der Ebenen; im Bild: h = 3
Ebene 1
Ebene 2
Ebene 3
W
R
RL
L
RL
Linker Teilbaum von W
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 10
Abbildung• Datenstruktur, wobei jedes Datum = Wertepaar:
Schlüssel: nach dem Schlüssel wird gesucht
Wert: ZielinformationBeispiel: Telefonbuch: Namen = Schlüssel, Telefonnummer = Werte
• Zusammenhang mit der Mathematik:A: S → W,
A...partielle Abbildung , S...Schlüsselmenge, W...WertemengePartiell: i.d.R nur ein (geringer) Teil der Schlüssel hat einen zugeordneten Wert
• Sonderform WörterbuchAbbildung, bei der das gesamte zu speichernde Datum ein Schlüssel ist
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 11
Binäre Suchbäume• Besonders geeignet für Speicherung von Daten, nach denen
später gesucht werden soll: Sie sind speziell auf Suchoperationen hin optimiert.
• Definition:Ein binärer Suchbaum ist ein binärer Baum mit folgenden Eigenschaften:(1) Jedem Knoten ist ein Schlüssel key zugeordnet(2) Sei x ein beliebiger Knoten und y ein Knoten i seinem
linken Unterbaum, so gilt key(y) < key(x)(3) Sei x ein beliebiger Knoten und y ein Knoten in seinem
rechten Unterbaum, so gilt key(y) > key(x)
• Wertepaare Schlüssel-Wert
• Englisch: Binary Search Tree, BST
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 12
Typische AufgabenTypische Operationen mit den Wertepaaren
Schlüssel-Wert sind
• SuchenFeststellen, ob ein angegebener Schlüssel im Baum enthalten ist,bzw. den zugehörigen Wert liefern.
• EinfügenEin Paar Schlüssel-Wert als einen neuen Knoten an geeignete Stelle im binären Suchbaum einfügen
• EntfernenEinen Knoten entfernen, wobei der Baum muss auch nach dem Löschen die Eigenschaft beibehalten, binärer Suchbaum zu sein.
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 13
Annahme: alle Schlüssel haben die gleiche Wahrscheinlichkeit,
dass sie gesucht werden.
Dann: Der Suchaufwand ist minimal, wenn alle Knoten Pfade
möglichst gleicher Länge haben (Vollbaum, quasivoller Baum)
Beispiel 1:
Mit einem vorhandenen (Schlüssel-)
Datenbestand ist ein binärer Suchbaum
ausgehend vom leeren Baum
aufzubauen.
Zuerst wird folgende Schlüsselreihenfolge gewählt:
57,23,37,15,30,27,79,33,45
Suchaufwand #1
57
23 79
15 37
30 45
27 33Ergebnis: Pfadlängen-Differenz = 3
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 14
Beispiel 2:
Eine andere Reihenfolge ergibt eine andere
Suchbaum-Struktur:
33,23,45,15,27,30,37,57,79
Suchaufwand #2
33
23 45
15 27
30
57
79
37
Die Baumstruktur ist von der Schlüsselreihenfolge abhängig.
Ergebnis: Pfadlängen-Differenz = 1
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 15
Für Knoten mit 0-1 Nachfolger ist das Löschen einfach:
BST programmieren:Löschen
45
25
31
27
57
79
3715
23
33
27
45
30
15
23
27
30
57
79
37
45
Funktioniert, aber...
457
25
31
27
39
Bei anderen Knoten ist es schwieriger. Z.B.
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 16
57
79
3715
23
33
27
45
30
oder
BST programmieren:Löschen• Bessere Lösch-Methode: „Schlüsseltransfer“
57
79
3715
23
33
27
45
30
57
79
3715
23
30
27
45
57
79
15
23
37
27
45
30
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 17
25
573715
23
33
27
45
25
Beispiel: Einfügen
Neuer Knoten:
Programmiertechnik
1
2
3
Einf
Ein_r(nS, nW, root)
Einf_r
RET
RET
nS<dK.S?
dK ex?
nS>dK.S?
New Kn(nS,nW,NULL,NULL)
Ein_r(nS, nW, RN)
Ein_r(nS, nW, LN)
N
N
N
J
J
J
dK ...ist dieser Knoten
bereits drin?
nS ... neuer Schlüssel
nW... neuer Wert
LN ... linker Nachfolger
RN ... rechter Nachfolger
dK.S ... S.v. diesem Knoten
dK = 33
dK ex? J
25 < 33? J
Ein_r(..., LN)
1
2
1
23
dK = 23
dK ex? J
25 < 23? N
25 > 23? J
Ein_r(..., RN)
1
2
dK = 27
dK ex? J
25 < 27? J
Ein_r(...,LN)
1dK = NULL
dK ex? N
New Kn (nS,nW,
NULL,NULL)
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 18
BST: andere Aufgaben #1Bisher: Suchen, Einfügen, Löschen. Was gibt es noch?
• Durchlauf durch einen Binärbaum- In-Ordnungen
LWR-Ordnung: aufgesucht wird:
1. linker Unterbaum, 2. Wurzel, 3. rechter Unterbaum
RWL-Ordnung: aufgesucht wird:
1. rechter Unterbaum, 2. Wurzel, 3. linker Unterbaum
- Prä-Ordnung: WLR, WRL
- Post-Ordnung: LRW, RLW
Aufgaben z.B.:
- Bestimmen aller Blätter, der Anzahl aller Blätter, aller Knoten
- Bestimmen der rechtesten Ecke im linken Unterbaum
- Kopieren, Löschen des Baums
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 19
BST: andere Aufgaben #2
• FädelungBeim Durchlauf eines Baums sind stets Rückläufe
notwendig. Der Durchlauf kann beschleunigt werden,
indem die Leerzeiger in den Blättern mit
entsprechenden „Zieladressen“ belegt werden.
• Bsp: Fädelung bei LWR
57
79
3715
23
33
27
45
30
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 20
1 2
3
4
5
6
Alternative graphische Darstellung von Bäumen1
2 3
4 5 6 7 8
5
4 6
2
7 8
3
1
(1 (2 (4, 5 (9,10), 6), 3 (7, 8)))
1 2 9, 10 , 6 , 3 7, 8
9
10
4, 5
7
8
9 10
9 10
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 21
Ausgeglichenheit der Bäume
Definition 1 (Classic):
Binäre Baume sind vollständig ausgeglichen,
wenn sich für jeden Knoten die ZAHLder Knoten in seinem
linken und rechten Teilbaum um höchstens eins unterscheiden.
Definition 2 (AVL-Bäume):
Ein Baum ist genau dann ausgeglichen,
wenn sich für jeden Knoten die HÖHEder Teibäume um höchstens eins unterscheiden
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 22
AVL-BäumeAdelson-Velski, Landis:
Neudefinition der Ausgeglichenheit
Länge des Suchpfades: O(log2 n)
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 23
Einfügen in AVL-Bäume
h h h h
h h
l l
l
r
r
r=
>=>
Einfügen
< h hl r<
=>
Einfügen
h hl r>
Einfügen
h hl r>>
ausgeglichen
ausgeglichen
ausgeglichenun
Bsp: Einfügen im linken Teilbaum 3 Fälle:
1. H(lTb) = H(rTb) ⇒ H(lTb) > H(rTb),
Baum bleibt ausgeglichen
2. H(lTb) < H(rTb) ⇒ H(lTb) = H(rTb)
Baum bleibt ausgeglichen
3. H(lTb) > H(rTb) ⇒
die Ausgeglichenheit wird zerstört,
der Baum muß neu strukturiert werden
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 24
Rotation bei AVL-BäumenWiederherstellung der Ausgeglichenheit
LR(b,a) RR(b,a)
Ziel: Ebene(b)-- //höher
Ebene(a)++ //tiefer
Dabei:
(1) Falls Vater(a) vorhanden:
Vater(a) abhängen, er wird zum Vater(b)
(2) Falls LSohn(b) vorhanden: Falls RSohn(b) vorhanden:
LSohn(b) abhängen und RSsohn(b) abhängen und
als RSohn(a) anhängen als LSohn(a) anhängen
DR=LR+RR
a
bn
n+1
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 25
Rotationsbeispiele#1
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 26
Rotationsbeispiele#2n+1
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 27
Rotationsbeispiele#34
5
+ 7 = 4
5
7
LR =>5
4 7+ 2 =
5
4
27 + 1 =
5
4
2
1
7 RR =>
5
2
1 4
7 + 3 =
<
>
<
>
5
2
1 4
3
7
LR
RR DR =>
4
2
1 3
5
7
+ 6 =
4
2
1 3
5
76
LR
LR =>
4
2
1 3 5
7
6
4
2
1 3 5 7
6
LR
RR
DR =>
LR
RR
ana a
ana a
na ana
naa
mit: a=ausgeglichen, na=nicht ausgeglichen
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 28
Vielweg-BäumeAnzahl Nachfolger eines Knotens: >2
Nachfolger4
Abb. 29a
Anwendung: Verwaltung großer Datenmengen
Zeiger auf Knoten: Plattenadressen statt Speicheradressen
Zugriffszeiten: Platte: ca. 10 ms
Speicher: 10 ns
(Faktor 106)
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 29
Aufteilung eines Baumes in Seiten
Seite = Teibaum
entspricht:
Abb. 30
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 30
Bayer-Bäume (B-Bäume)
Eingeführt 1970 von Bayer und McCreight
Eigenschaften von Bayer-Bäumen der Ordnung n:• Jeder Knoten (Seite) bis auf den Wurzelknoten enthält
m Einträge (Schlüssel), mit n<=m<=2*n• Die Wurzel enthält 1<=m<=2*n Einträge• Jeder Knoten (Seite) hat 0 oder m+1 Nachfolger, d.h.
Anzahl der Nachfolger = Anzahl der Einträge + 1• Alle Blätter (Blattseiten) haben die gleiche Höhe h.
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 31
Beispiel für einen B-Baum
10 20
2 5 7 8 13 14 15 18 22 2410 20 26 27 2825 30 32 35 38 40 41 42 45
25
30 40
Wurzel
m=2
Ordnung n=2
Seite
m+1=3
Blattseiten 2n=4 n=2
Abb.31
n <= m <= 2n
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 32
Suchen in einem B-Baum1. Man lese eine Seite in den Hauptspeicher ein (falls existiert).
Hat die angegebene Referenz (Zeiger) den Wert Null, dann
existiert der Schlüssel S nicht.
2. Man prüfe, ob der gesuchte Schlüssel S vorhanden ist.
Diese Suchzeit ist im allgemeinen kleiner als die Zeit zum
Einlesen der Seite vom Hintergrundspeicher.
3. Hat die Suche keinen Erfolg, so liegen folgende Situationen vor:
3.1. Ki < S < Ki+1, für 0 <= i < m-1 mit Ki Schlüssel an der
Stelle i.
Dann setzen wir die Suche auf der Seite Pi fort.
3.2. Km-1 < S . Die Suche wird auf der Seite Pm fortgesetzt.
3.3. S < K1 . Die Suche wird auf der Seite P0 fortgesetzt.
D1
P0 K1
D2
P1 K2 Pm-1Pm-2….x
Dm-1
Km-1P2
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 33
Löschen aus dem B-Baum#1
Situation 1: Suchargument ist im Blatt:1.1 Blatt hat mehr als n Elemente (normal):
lösche Element20 30
7 10 15 18 22 26 35 40 41
20 30
22 26 35 40 417 15 18
n=2
Abb. 33a
zu löschen: 10
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 34
Löschen aus dem B-Baum#21.2 Blatt hat genau n Elemente (Unterlauf):
betrachte linken (rechten) Bruder
1.2.1 linker (rechter) Bruder hat mehr als n Elemente:
dann ‘verschiebe’ Wurzel ins Blatt und Blatt in die Wurzel
22 26 35 40 417 15 18
n=2
7 15 18
20 35
26 30
20 30
löschen
40 41
Abb. 33b
zu löschen: 22
Unterlauf droht:
Ein Knoten muss min.
2 Elemente haben
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 35
Löschen aus dem B-Baum#31.2.2 linker und rechter Bruder hat genau n Elemente:
dann ‘verkette’n=2
20 35
26 30 40 41
20
30 35 40 41
7 15
7 15
Abb. 33c
zu löschen: 26
2006 Jiri Spale, Algorithmen und Datenstrukturen - Bäume 36
Löschen aus dem B-Baum#4Situation 2: Suchargument ist nicht im Blatt:
rechtes Element im linken Teilbaum ‘hochziehen’
22 26 35 40 417 15 18
n=2
7 15 18
20 30 löschen
20 26
dann Unterlauf , weiter wie unter 2
18 26
7 15
35 40 4122
20 22 35 40 41
Abb. 33d
zu löschen: 30