Informatik II, SS 2008Algorithmen und Datenstrukturen
Vorlesung 18Prof. Dr. Thomas Ottmann
Algorithmen & Datenstrukturen, Institut für InformatikFakultät für Angewandte WissenschaftenAlbert-Ludwigs-Universität Freiburg
Natürliche Suchbäume
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 2
Bäume (1)
Bäume sind
verallgemeinerte Listen(jedes Knoten-Element kann mehr als einen Nachfolger haben)
spezielle Graphen:– Ein allgemeiner Graph G = (V,E) besteht aus Knoten V (vertices) und Kanten E V × V (edges).– Die Kanten sind entweder gerichtet oder ungerichtet.– Knoten und Kanten können markiert sein (sie tragen weitere Informationen).
Ein Baum ist ein zusammenhängender azyklischer Graph. Es gilt:# Knoten= # Kanten+1
ein allgemeines & zentrales Konzept zur hierarchischen Strukturierung vonInformationen:– Entscheidungsbäume– Codebäume– Syntaxbäume
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 3
Bäume (2)Ungerichteter Baum (kein Knoten ist als Wurzel ausgezeichnet)
Gewurzelter Baum (Wurzelbaum, ein Knoten ist als Wurzel ausgezeichnet)
– Von jedem Knoten k führt genau ein Pfad (Folge paarweise benachbarter Kanten) zur Wurzel– Vater (Elter, direkter Vorgänger) eines Knotens k ist der erste Nachbar auf dem Pfad von k zur Wurzel– Söhne (Kinder, direkte Nachfolger) sind die anderen Nachbarn von k– Der Rang von k ist die # Söhne des Knotens k
4
65
2
13
Wurzel
65
1
4
3
2
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 4
Bäume (3)
Gewurzelter Baum:– Wurzel: einziger Knoten ohne Vater– Blätter: Knoten ohne Söhne– innere Knoten: alle Knoten, die kein Blatt sind– Ordnung eines Baumes T: maximaler Rang eines Knotens von T– Der Begriff Baum wird oft als Synonym für Wurzelbaum gebraucht
Geordneter Wurzelbaum: Unter den Söhnen jedes Knotens ist eine Ordnungfestgelegt, etwa über < -Relation unter Schlüsseln in Knoten
Binärbaum: Geordneter Wurzelbaum der Ordnung 2, Söhne werden mit linker Sohn, rechter Sohn bezeichnet
Vielwegbaum: geordneter Wurzelbaum der Ordnung > 2
1 < 2
3 < 5 <
4
6
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 5
Bäume (4)
Exaktere Definition für die Menge Md
der geordneten Wurzel-Bäume der Ordnung d (d ≥ 1):
Ein einzelner Knoten ist in Md
Sind t1, . . .,td in Md und ist w ein Knoten, dann ist w mit den Wurzeln von
t1, . . .,td als Nachfolgern (v.l.n.r.) ein Baum t. Die ti sind Teil-Bäume von t.
– Nach dieser Definition muss jeder Knoten Rang d haben.
– Allgemeiner darf der Rang auch kleiner sein.
– Knoten von Binär-Bäumen haben entweder 0 oder 2 Söhne.
– Man könnte auch Knoten mit genau 1 Sohn zulassen, indem in obiger Definition auch leere Teil-Bäume erlaubt werden.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 6
Rekursive Definition
ist ein Baum der Ordnung d, mit Höhe 0.
Sind t1,…,td beliebige, disjunkte Bäume der Ordnung d, so erhält maneinen (weiteren) Baum der Ordnung d, indem man die Wurzeln vont1,…,td zu Nachfolgern einer neu geschaffenen Wurzel w macht. DieHöhe h des neuen Baums ist dann max {h(t1),…,h(td)}+1.
Festlegung: d = 2 Binärbäume, d > 2 Vielwegbäume.
w
t1t2 td
..................
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 7
Beispiele
Baum kein Baum kein Baum (aber zwei
Bäume)
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 8
Strukturelle Eigenschaften von Bäumen
Tiefe eines Knotens k: # Kanten von der Wurzel des Baums bis k(Abstand von k zur Wurzel)
Höhe h(t) eines Baumes t: Maximale Tiefe eines Blattes von t.Alternative (rekursive) Definition:– h(Blatt) = 0– h(t) = 1 + max{ti |Wurzel von ti ist Sohn von Wurzel von t} (ti ist Teil-Baum von t)
Niveau i: alle Knoten in Tiefe i
Vollständiger Baum: Baum, bei dem jedes nichtleere Niveau volle Knotenanzahl hat. alle Blätter haben die gleiche Tiefe.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 9
Anwendung für Bäume
Verwendung von Bäumen für die Lösung des WBP:
Knoten: Speicher für Datensätze
Baum: Speicher für Datenmengen
Besonderer Vorteil (gegenüber Hash-Tabellen): Durchlauf der gesamten Menge von Sätzen (etwa in sortierter Reihenfolge) leicht möglich.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 10
Natürliche, binäre Suchbäume (1)
Ziel: Speichern, Wiederfinden von Datensätzen (allgemeiner: WBP)
Zwei alternative Speicherungsformen:
Suchbäume: Schlüssel werden in inneren Knoten gespeichertBlätter sind leer (oft=null) sie repräsentieren Intervalle zwischen den Schlüsseln
Blattsuchbäume: Schlüssel werden in Blättern gespeichertinnere Knoten enthalten Wegweiser zum Auffinden
Suchbaum-Bedingung:für jeden inneren Knoten k gilt: alle Schlüssel links unterhalb von k (im linkenTeil-Baum tl) sind < als der Schlüssel in k und alle Schlüssel rechts unterhalb von k (im rechtenTeil-Baum tr) sind > als der Schlüssel in k
k
tl tr
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 11
Blätter in Suchbaum repräsentieren Intervalle zwischen den Schlüsseln der inneren Knoten
Wie sucht man in einem Suchbaum nach Schlüssel s? (Blatt null)
k = wurzel;while (k != null) { if (s == k.key) return true; if (s < k.key) k = k.left; else k = k.right}return false;
Natürliche Bäume (2)
(9,12)
(4,9)(3,4)
(12, )(- ,3)
9
3 12
4
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 12
Beispiel (ohne Stopper)
Wurzel 27
393
15
14
1
Suche nach Schlüssel s endet beim Suchbaum in Knoten k mit k.key == s oder in
Blatt, dessen Intervall s enthält
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 13
Natürliche Bäume (3)
Blattsuchbaum:
Schlüssel werden in Blättern gespeichert
Hinweise (Wegweiser) werden in inneren Knoten gespeichert, so dass sl ≤ sk ≤ sr (sl : Schlüssel in linkem TB, sk : Wegweiser in k, sr Schlüssel in rechtem TB)= sollte nicht doppelt vorkommen
Wahl für s: entweder maximaler Schlüssel von tl (üblich) oder minimaler Schlüsselvon tr.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 14
Blätter enthalten die Schlüssel, innere Knoten Wegweiser.
Beispiel: Blattsuchbaum
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 15
Natürliche Bäume (4)
Wie sucht man in einem Blattsuchbaum nach Schlüssel s? (Blatt = Knoten mit 2null-Ref.) k = wurzel; if (k == null) return false; while (k.left != null) { // damit auch k.right != null if (s <= k.key) k = k.left; else k = k.right; } // jetzt in Blatt return s==k.key;
Im Folgenden werden Suchbäume (nicht Blatt-) betrachtet.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 16
Natürliche Bäume (5)
class SearchNode { int content; SearchNode left; SearchNode right; SearchNode (int c){ // Konstruktor fuer einen Knoten content = c; // ohne Nachfolger left = right = null; }} //class SearchNode
class SearchTree { SearchNode root; SearchTree () { // Konstruktor fuer leeren Baum root = null; } // ...
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 17
Natürliche Bäume (6)
/* Suche nach c im Baum */boolean search (int c) { return search (root, c);}boolean search (SearchNode n, int c){ while (n != null) { if (c == n.content) return true; if (c < n.content) n = n.left; else n = n.right; } return false;}
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 18
Natürliche Bäume (7)
Alternative Baumstruktur:
Statt Blatt null verwende: Blatt Referenz auf besonderen Stopper-Knoten b
Bei Suche stecke Such-Schlüssel s in b und spare Vergleiche in inneren Knoten.
Verwendung eines Stoppers für die Suche!
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 19
Beispiel (mit Stopper)
27
393
15
14
1
Wurzel
x
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 20
Natürliche Bäume (7)
Einfügen eines Knotens mit Schlüssel s in Suchbaum t:
Suche nach s endet in Knoten mit s: nicht einfügen, da sonst doppelte Schlüssel
Suche endet in Blatt b: Mache b zu innerem Knoten mit s als Schlüssel und zweineuen Blättern.
Baum bleibt Suchbaum!
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 21
Natürliche Bäume (8)
• Baum-Struktur hängt von Einfügereihenfolge in anfangs leeren Baum ab
• Höhe kann linear zunehmen, sie kann aber auch in O(log n) sein, genau
log2 (n+1).
9
3 12
4
9
3 12
5
4
Einfügen 5
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 22
Natürliche Bäume (9)int height (){ return height (root);}int height (SearchNode n){ if (n == null) return 0; else return 1 + Math.max (height (n.left), height (n.right));}/* Fuege c im Baum ein; gib true zurueck, falls erfolgreich und false, falls schon vorhanden */boolean insert (int c) { // Fuege c ein; if (root == null){ root = new SearchNode (c); return true; } else return insert (root, c);}
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 23
Natürliche Bäume (10)
boolean insert (SearchNode n, int c){ while (true){ if (c == n.content) return false; if (c < n.content){ if (n.left == null) { n.left = new SearchNode (c); return true; } else n = n.left; } else { // c > n.content if (n.right == null) { n.right = new SearchNode (c); return true; } else n = n.right; } }}
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 24
Sonderfälle
Die Struktur des resultierenden Baums hängt stark von der Reihenfolge ab, in
der die Schlüssel eingefügt werden. Die minimale Höhe ist log2n + 1 und die
maximale Höhe ist n.
Resultierende Suchbäume für die Reihenfolgen 15, 39, 3, 27, 1, 14 und 1, 3,
14, 15, 27, 39:
15
393
14 271
1
3
14
15
27
39
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 25
Natürliche Bäume (11)Ein Natürlicher Baum entsteht durch iteriertes Einfügen in den anfangs leeren Baum.
Welche Bäume sind die häufigeren/typischeren, die ausgeglichenen, diedegenerierten?
Wie teuer ist das Einfügen?
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 26
Natürliche Bäume (11)
Entfernen eines Knotens mit Schlüssel s aus einem Baum (Beibehaltung der Suchbaum Eigenschaft)
1. Suche nach s, falls nicht da: fertig; sonst endet die Suche mit k.key == s und
2. k hat keinen, einen oder zwei Söhne:(a) kein Sohn: fertig, Vater bekommt Zeiger auf null(b) nur ein Sohn ist da : lasse Vater v von k darauf statt auf k zeigen(c) zwei Söhne: suche kleinsten Wert in rechtem Teilbaum, d.h. mache einen Schritt nach rechts und beliebig viele nach links bis zu p (symmetrischer Nachfolger von k); kopiere p.key nach k, lösche p (max. einen Sohn, also nach a, b behandeln)
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 27
Symmetrische Nachfolger
Definition: Ein Knoten q heißt der symmetrische Nachfolger eines Knotens p,
wenn q den kleinsten Schlüssel enthält, der größer oder gleich dem Schlüsselvon p ist.
Beobachtungen:
Der symmetrische Nachfolger q von p ist der am weitesten links stehendeKnoten im rechten Teilbaum von p.
Der symmetrische Nachfolger hat höchstens einen Nachfolger, welcherder rechte ist.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 28
Auffinden des symmetrischen Nachfolgers
Beobachtung: Wenn p einen rechten Nachfolger hat, gibt es immer einen
symmetrischen Nachfolger.
• Zunächst gehen wir zum rechten Nachfolger von p.
• Von dort aus gehen wir solange jeweils zum linken Nachfolger, bis wir
einen Knoten ohne linken Nachfolger finden.
p
q
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 29
Idee der Löschoperation
Wir löschen p, indem wir den Inhalt von p durch den seines symmetrischen
Nachfolgers q ersetzen. Danach löschen wir q.
Löschen von q ist einfach, weil q höchstens einen Nachfolger hat.
xp
yq
xp
yq
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 30
Beispielek hat keinen, einen oder zwei innere Söhne:
v
v
tl
v
tr
v
sk
tr
v
sk
v
sk
tl
v
sk
tl
tr
p
a)
b)
c) d)
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 31
Natürliche Bäume (12)
boolean delete (int c){ return delete (null, root, c);}// loesche c im Baum mit Wurzel n, deren Vorgaenger vn istboolean delete (SearchNode vn, SearchNode n, int c){ if (n == null) return false; if (c < n.content) return delete (n, n.left, c); if (c > n.content) return delete (n, n.right, c); // jetzt gilt: c == n.content if (n.left == null) { point (vn, n, n.right); return true; } if (n.right == null) { point (vn, n, n.left); return true; } // ...
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 32
Natürliche Bäume (13)
// jetzt ist n.left != null und n.right != null SearchNode q = vSymNach (n); if (n == q) { // rechter Sohn von q ist vSymNach (n) n.content = q.right.content; q.right = q.right.right; return true; } else { // linker Sohn von q ist vSymNach (n) n.content = q.left.content; q.left = q.left.right; return true; }} // boolean delete (SearchNode vn, SearchNode n, int c)
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 33
Natürliche Bäume (14)
// vn soll auf m statt auf n zeigen; ist vn == null, zeigt root aufvoid point (SearchNode vn, SearchNode n, SearchNode m){ if (vn == null) root = m; else if (vn.left == n) vn.left = m; else vn.right = m;}// liefert Vater des symmetrischen Nachfolgers:SearchNode vSymNach (SearchNode n) if (n.right.left != null) { n = n.right; while (n.left.left != null) n = n.left; } return n;}
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 34
Binärbäume zur Speicherung von Mengen von Schlüsseln (in den inneren Knoten
der Bäume), so dass die Operationen
• Suchen (find)
• Einfügen (insert)
• Entfernen (remove, delete)
unterstützt werden.
Suchbaumeigenschaft: Die Schlüssel im linken Teilbaum eines Knotens p
sind alle kleiner als der Schlüssel von p, und dieser ist wiederum
kleiner als sämtliche Schlüssel im rechten Teilbaum von p.
Implementierung:
Binäre Suchbäume
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 35
Natürliche Bäume
• Baum-Struktur hängt von Einfügereihenfolge in anfangs leeren Baum ab
• Höhe kann linear zunehmen, sie kann aber auch in O(log n) sein, genau
log2(n+1)
9
3 12
4
9
3 12
5
Einfügen 5
4
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 36
Durchlaufreihenfolgen in Bäumen
Durchlaufreihenfolgen zum Besuchen der Knoten des Baums
• zur Ausgabe,
• zur Berechnung von Summe, Durchschnitt, Anzahl der Schlüssel . . .
• zur Änderung der Struktur
Wichtigste Durchlaufreihenfolgen:
• Hauptreihenfolge = Preorder = WLRbesuche erst Wurzel, dann rekursiv linken und rechten Teil-Baum falls vorhanden
• Nebenreihenfolge = Postorder = LRW
• Symmetrische Reihenfolge = Inorder = LWR
die Spiegelbild-Varianten von 1-3
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 37
Hauptreihenfolge (Preorder)
Ausgehend von der Wurzel p eines Baums ist die Hauptreihenfolge wie
folgt rekursiv definiert:
Durchlaufen aller Knoten eines Binärbaumes mit Wurzel p in Hauptreihenfolge:Besuche p, durchlaufe den linken Teilbaum von p in Hauptreihenfolge,durchlaufe den rechten Teilbaum von p in Hauptreihenfolge.
17
11 22
7 14
12
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 38
Hauptreihenfolge Programm
// Hauptreihenfolge; WLRvoid preOrder (){ preOrder (root); System.out.println ();}void preOrder (SearchNode n){ if (n == null) return; System.out.print (n.content+" "); preOrder (n.left); preOrder (n.right);}// Nebenreihenfolge; LRWvoid postOrder (){ postOrder (root); System.out.println ();}// ...
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 39
Symmetrische Reihenfolge (Inorder)
Die Durchlaufreihenfolge ist: erst linker Teilbaum, dann Wurzel, dann rechter
Teilbaum:
// Symmetrische; LWRvoid inOrder (){ inOrder (root); System.out.println ();}void inOrder (SearchNode n){ if (n == null) return;
inOrder (n.left);
System.out.print (n.content+" ");
inOrder (n.right);}// Nebenreihenfolge; LRW// ...
Die anderen Durchlaufreihenfolgen werden analog implementiert.
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 40
Beispiel
Preorder:17, 11, 7, 14, 12, 22
Postorder:7, 12, 14, 11, 22, 17
Inorder:7, 11, 12, 14, 17, 22
17
11 22
7 14
12
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 41
Binärbäume zur Speicherung von Mengen von Schlüsseln (in den inneren Knoten
der Bäume), so dass die Operationen
• Suchen (find)
• Einfügen (insert)
• Entfernen (remove, delete)
unterstützt werden.
Suchbaumeigenschaft: Die Schlüssel im linken Teilbaum eines Knotens p
sind alle kleiner als der Schlüssel von p, und dieser ist wiederum
kleiner als sämtliche Schlüssel im rechten Teilbaum von p.
Implementierung:
Binäre Suchbäume
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 42
Natürliche Bäume
• Baum-Struktur hängt von Einfügereihenfolge in anfangs leeren Baum ab
• Höhe kann linear zunehmen, sie kann aber auch in O(log n) sein, genau
log2(n+1)
9
3 12
4
9
3 12
5
Einfügen 5
4
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 43
Beispiel für Suchen, Einfügen, Entfernen
17
11 22
7 14
12
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 44
Sortieren mit natürlichen Suchbäumen
Idee: Bau für die Eingabefolge einen natürlichen Suchbaum auf und gib dieSchlüssel in symmetrischer Reihenfolge (Inorder) aus.
Bemerkung: Abhängig von der Eingabereihenfolge kann der Suchbaumdegenerieren.
Komplexität: Abhängig von der internen Pfadlänge
Schlechtester Fall: Sortierte Eingabe: (n2) Schritte.
Bester Fall: Es entsteht ein vollständiger Suchbaum mit minimal möglicher Höhe von etwa log n. n mal Einfügen und Ausgeben ist daher in Zeit O(n log n) möglich.
Mittlerer Fall: ?
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 45
Analyse natürlicher Suchbäume
Zwei alternative Vorgehensweisen zur Bestimmung der internen Pfadlänge:
1. Random-Tree-Analyse, d.h. Mittelwert über alle möglichen Permutationen der (in den anfangs leeren Baum) einzufügenden Schlüssel.
2. Gestaltanalyse, d.h. Mittelwert über alle strukturell möglichen Bäume mit n Schlüsseln.
Unterschied des Erwartungswertes für die interne Pfadlänge:
1. 1.386 n log2n – 0.846 n + O(log n)
2. nn + O(n)
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 46
Ursache für den Unterschied
Bei der Random-Tree-Analyse werden ausgeglichene Bäume häufiger gezählt.
3
2
1
3
1
2
1
3
2
1
2
3
3
2
1
3,2,1 3,1,2 1,3,2 1,2,3 2,1,3 und 2,3,1
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 47
Interne Pfadlänge
Interne Pfadlänge: Maß zu Beurteilung der Güte eines Suchbaumes.
Rekursive Definition:
1. Ist t der leere Baum, so istI(t) = 0.
2. Für einen Baum mit Wurzel t, linkem Teilbaum tl und rechtem Teilbaum tr gilt:
I(t) := I(tl) + I(tr)+ Zahl der Knoten von t.
Offensichtlich gilt:
p
tI
P innerer Knoten von t
pTiefe 1)()(
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 48
Durchschnittliche Suchpfadlänge
Für einen Baum t ist die durchschnittliche Suchpfadlänge definiert durch:
D(t) = I(t)/n, n = Anzahl innerer Knoten in t
Frage: Wie groß ist D(t) im
• besten• schlechtesten• mittleren Fall
für einen Baum t mit n inneren Knoten?
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 49
Interne Pfadlänge: Bester Fall
Es entsteht ein vollständiger Binärbaum
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 50
Interne Pfadlänge: Schlechtester Fall
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 51
Zufällige Bäume
Seien oBdA die Schlüssel {1,…,n} einzufügen.
Sei ferner s1,…, sn eine zufällige Permutation dieser Schlüssel.
Somit ist die Wahrscheinlichkeit P(s1 = k), dass s1 gerade den Wert k hat, genau 1/n.
Wenn k der erste Schlüssel ist, wird k zur Wurzel.
Dann enthalten der linke Teilbaum k – 1 Elemente (nämlich die Schlüssel 1,…,k - 1) und der rechte Teilbaum n – k Elemente (d.h. die Schlüssel k + 1,…,n).
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 52
Erwartete interne Pfadlänge
EI(n) : Erwartungswert für die interne Pfadlänge eines zufällig
erzeugten binären Suchbaums mit n Knoten
Offensichtlich gilt:
Behauptung: EI(n) 1.386n log2n - 0.846n + O(logn).
n
k
n
k
n
k
knEIkEIn
n
nknEIkEIn
nEI
EI
EI
1 1
1
))()1((1
))()1((1
)(
1)1(
0)0(
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 53
Beweis (1)
und daher
Aus den beiden letzten Gleichungen folgt
n
k
kEIn
nnEI0
)(*1
2)1()1(
1
0
2
0
2
)(*2*
)(*2)1()1(*)1(
n
k
n
k
kEInEIn
kEInnEIn
).(1
2
1
12)1(
12)()2()1()1(
)(*212)(*)1()1(
nEIn
n
n
nnEI
nnEInnEIn
nEInnEInnEIn
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 54
Beweis (2)
Durch vollständige Induktion über n kann man zeigen, dass für alle n ≥ 1 gilt:
ist die n -te harmonische Zahl, die wie folgt
Abgeschätzt werden kann:
Dabei ist die so genannte Eulersche Konstante.
nHn
1...
2
11
)1
(2
1ln 2nn
nHn
...5772.0
nHnnEI n 3)1(2)(
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 55
Beweis (3)
Damit ist
Und daher
)1(21ln2*)23(ln2)(n
nnnnnEI
...ln2
)23(log386.1
...ln2
)23(log*log
2log2
...ln2
)23(log*log
2
...ln2
)23(ln2)(
2
210
10
22
n
nn
n
nn
e
n
nn
e
n
nn
n
nEI
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 56
Beobachtungen
Suchen, Einfügen und Entfernen eines Schlüssels ist bei einem zufällig erzeugten binären Suchbaum mit n Schlüsseln im Mittel in O(log2 n) Schritten möglich.
Im schlechtesten Fall kann der Aufwand jedoch Ω(n) betragen.
Man kann nachweisen, dass der mittlere Abstand eines Knotens von der Wurzel in einem zufällig erzeugten Baum nur etwa 40% über dem Optimum liegt.
Die Einschränkung auf den symmetrischen Nachfolger verschlechtert jedoch das Verhalten.
Führt man in einem zufällig erzeugten Suchbaum mit n Schlüsseln n2 Update-Operationen durch, so ist der Erwartungswert für die durchschnittliche Suchpfadlänge lediglich Θ(n).
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 57
Typischer Binärbaum für eine zufällige Schlüsselsequenz
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 58
Resultierender Binärbaum nach n2 Updates
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 59
Strukturelle Analyse von Binärbäumen
Frage: Wie groß ist die durchschnittliche Suchpfadlänge eines Binärbaumes mit N inneren Knoten, wenn man bei der Durchschnittsbildung jeden strukturell möglichen Binärbaum mit N inneren Knoten genau einmal zählt?
Antwort: Sei
IN = gesamte interne Pfadlänge aller strukturell verschiedenen Binärbäume mit N inneren Knoten
BN = Anzahl aller strukturell verschiedenen Bäume mit N inneren Knoten
Dann ist IN/BN =
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 60
Anzahl strukturell verschiedener Binärbäume
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 61
Gesamte interne Pfadlänge aller Bäume mit N Knoten
Für jeden Baum t mit linkem Teilbaum tl und rechtem Teilbaum tr gilt:
Informatik II: Algorithmen und Datenstrukturen, SS 2008Prof. Dr. Thomas Ottmann 62
Zusammenfassung
Die durchschnittliche Suchpfadlänge in einem Baum mit N inneren Knoten (gemittelt über alle strukturell möglichen Bäume mit N inneren Knoten) ist:
1/N IN/BN