Datenstrukturen - uni-frankfurt.de · 2012. 6. 19. · Priorit atswarteschlangen: Zusammenfassung (a)Ein Heap mit n Priorit aten unterst utzt jede der Operationen insert, delete max,

Datenstrukturen

Mariano Zelke

Sommersemester 2012

Prioritatswarteschlangen: Zusammenfassung

(a) Ein Heap mit n Prioritaten unterstutzt jede der Operationeninsert, delete max, change priority und removein Zeit O(log2 n).

I Fur die Operationen change priority und remove muss diePosition der zu andernden Prioritat bekannt sein.

(b) build heap baut einen Heap mit n Prioritaten in Zeit O(n).

(c) heapsort sortiert n Zahlen in Zeit O(n log2 n).

Mariano Zelke Datenstrukturen 2/29

Das Single-Source-Shortest-Path-Problem

Ein gerichteter Graph G = (V ,E ) und eine Langen-Zuweisunglange: E → R≥0 an die Kanten des Graphen ist gegeben.Bestimme kurzeste Wege von einem ausgezeichneten Startknoten s ∈ Vzu allen Knoten von G .

I Die Lange eines Weges ist die Summe seiner Kantengewichte.

I Mit Hilfe der Breitensuche konnen wir kurzeste-Wege Problemelosen, falls lange(e) = 1 fur jede Kante e ∈ E gilt.Fur allgemeine nicht-negative Langen brauchen wir eineausgeklugeltere Idee.

I Kantengewichte sind nicht-negativ: Die kurzeste, mit s verbundeneKante (s, v) ist ein kurzester Weg von s nach v .

I Dijkstras Algorithmus setzt diese Beobachtung wiederholt ein.


Dijkstras Algorithmus

(1) Setze S = {s} und fur alle Knoten v ∈ V \ {s} setze

distanz[v] =

{lange (s, v) wenn (s, v) ∈ E∞ sonst.

/* distanz[v] ist die Lange des bisher festgestellten kurzesten Wegesvon s nach v . */

(2) Solange S 6= V wiederhole

(a) wahle einen Knoten w ∈ V \ S mit kleinstem Distanz-Wert./* distanz[w] ist die tatsachliche Lange eines kurzesten Wegesvon s nach w . */

(b) Fuge w in S ein.(c) Aktualisiere die Distanz-Werte der Nachfolger von w :

Setze fur jeden Nachfolger u ∈ V \ S von wdistanz[u] = min(distanz[u], distanz[w]+lange(w,u));


Datenstrukturen fur Dijkstras Algorithmus

In der Vorlesung”Algorithmentheorie“ wird gezeigt, dass Dijkstras

Algorithmus korrekt ist und das Kurzeste-Wege-Problem effizient lost.

I Darstellung des Graphen G : Wir implementieren G alsAdjazenzliste, da wir dann sofortigen Zugriff auf die Nachfolger uvon w im Aktualisierungschritt (2c) haben.

I Implementierung der Menge V \ S :I Knoten sind gemaß ihrem anfanglichen Distanzwert einzufugen.I Ein Knoten w mit kleinstem Distanzwert ist zu bestimmen und zu

entfernen.

Wahle einen Min-Heap, um die entsprechendePrioritatswarteschlange zu implementieren:

I Ersetze die Funktion delete max() durch die Funktiondelete min().(Und passe repair up und repair down entsprechend an.)

I Implementiere den Aktualisierungschritt (2c) durchchange priority(wo,neue Distanz).Woher kennen wir die Position wo?


Minimale Spannbaume (Link)

Sei G = (V ,E ) ein ungerichteter, zusammenhangender Graph.Jede Kante e ∈ E erhalt eine positiv, reellwertige Lange

”lange(e)“.

I Ein Baum T = (V ′,E ′) heißt ein Spannbaum fur G , falls V ′ = Vund E ′ ⊆ E .

I Die Lange eines Spannbaums ist die Summe der Langen seinerKanten.

I Ein minimaler Spannbaum ist ein Spannbaum minimaler Lange.

I Je zwei Knoten von G bleiben auch in einem Spannbaum Tmiteinander verbunden, denn ein Baum ist zusammenhangend.Wenn wir aber irgendeine Kante aus T entfernen, dann zerstorenwir den Zusammenhang.

I Wir suchen nach einem zusammenhangenden Teilgraph in G , derminimale Lange hat.


http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php

Der Algorithmus von Prim

(1) Setze S = {0}./* B ist stets ein Baum mit Knotenmenge S . Zu Anfang besteht Bnur aus dem Knoten 0. */

(2) Solange S 6= V , wiederhole:

(a) Bestimme eine kurzeste kreuzende Kante e = {u, v}.(b) Fuge e zu B hinzu.(c) Wenn u ∈ S , dann fuge v zu S hinzu. Ansonsten fuge u zu S hinzu.

/* Beachte, dass wir neue kreuzende Kanten erhalten, namlich alleKanten die den neu hinzugefugten Knoten als einen Endpunkt undeinen Knoten aus V \ S als den anderen Endpunkt besitzen. */


Die Datenstrukturen fur Prims Algorithmus

I Fur jeden Knoten u ∈ V \ S bestimmen wir die Lange l(u) einerkurzesten Kante, die u mit einem Knoten in S verbindet.

I Wir verwalten die Knoten in V \ S mit einer Prioritatswarteschlangeund definieren l(u) als die Prioritat des Knotens u.

I Initialisiere einen Min-Heap, indem jeder Nachbar u von Startknoten0 mit Prioritat lange({0, u}) einfugt wird, bzw. mit Prioritat ∞,wenn u kein Nachbar ist.

I Wir bestimmen also eine kurzeste kreuzende Kante, wenn wir einenKnoten in u ∈ V \ S mit niedrigster Prioritat bestimmen.

I Beachte, dass sich nur die Prioritaten der Nachbarn von u andern.

I Implementiere G durch eine Adjazenzliste, da wir stets nur auf dieNachbarn eines Knoten zugreifen mussen.


Kruskals Algorithmus: Die Idee

I Prims Algorithmus lasst einen minimalen Spannbaum”Kante fur

Kante“ wachsen.I Kruskals Algorithmus beginnt mit einem Wald von Einzelknoten.

I Die Kanten werden nach aufsteigender Lange sortiert und der Reihenach, beginnend mit Kanten kurzester Lange verarbeitet.

I Wenn die Kante e an der Reihe ist und keinen Kreis schließt, dannwird die Kante e zum Wald hinzugefugt.

I Ansonsten schließt die Kante e einen Kreis und wird verworfen.


Kruskals Algorithmus

(1) Sortiere die Kanten gemaß aufsteigender Lange. Sei W = (V ,F )der leere Wald, also F = ∅.

(2) Solange W kein Spannbaum ist, wiederhole

(a) Nimm die gegenwartig kurzeste Kante e und entferne sie aus dersortierten Folge.

(b) Verwirf e, wenn e einen Kreis in W schließt.(c) Ansonsten setze F = F ∪ {e}: e wird zum Wald W hinzugefugt.

Wir beschranken uns auf die Implementierung.In der Vorlesung

”Algorithmentheorie“ wird gezeigt, dass Kruskals

Algorithmus korrekt ist.


Beispiel Kruskals Algorithmus

Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

16

8

39

10

6

2

7

12

3

14

9

1112

15

16

21

1917

18



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

168

3910

6151712

314

91112

2162119

718



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139

2



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139

2

3

67

8

9

10

11



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139

2

3

67

8

9

10

11



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139

2

3

67

8

10

129

11



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139

2

3

67

8

9

10

11



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139 3

7

8

12

16

19

11

9 2

6

10

14



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

236789

10111212141516161718192139 3

7

8

12

16

11

9 2

6

10

14



Karlsruhe

Frankfurt/M.

Hannover

Hamburg

Dort-mund

Bremen

Olden-

burg

Rostock

Berlin

Leipzig

Dresden

Nurnberg

Munchen

2

3

67

8

9

10

11

12

14

1639

Aber:

Wie stellen wir fest,ob eine Kanteeinen Kreis schließt?


Die Union-Find Datenstruktur I

I Wir sortieren die Kanten zum Beispiel mit Heapsort.

I Danach mussen wir fur jede Kante e = {u, v} entscheiden,ob e einen Kreis in W schließt.

I Die Operation find(u) bestimme die Wurzel wu des Baumes,der u enthalt.

I Die Kante e schließt genau dann einen Kreis, wennfind(u) = find(v).

I Wenn e keinen Kreis in W schließt, dann mussen wir die Baume mitden Wurzeln find(u) und find(v) vereinigen. Dazu benutzen wir dieOperation union(u, v).

Wie sollten wir den Wald W implementieren?


Die Union-Find Datenstruktur II

Wir implementieren den Wald W durch ein Vater-Array.

I Zu Anfang ist Vater[i ] = i fur alle Knoten i . (Wir fassen i immerdann als eine Wurzel auf, wenn Vater[i ] = i gilt.)

I Wie ist find(u) zu implementieren?I Klettere den Baum von u mit Hilfe des Vater-Arrays hoch.I Die

”Kletter-Zeit“ ist durch die Tiefe des Baumes beschrankt.

I Wie garantieren wir, dass die Baume nicht zu tief werden?

I Wenn wir zwei Baume vereinigen, dann hange die Wurzel deskleineren Baumes unter die Wurzel des großeren Baumes!(Achtung: hierbei wird eine Kante eingefugt, die wir moglicherweisenicht zu W hinzufugen!)

I Betrachte einen beliebigen Knoten v .I Die Tiefe vergroßert sich nur dann um 1, wenn v dem kleineren

Baum angehort. Wenn die Tiefe von v um 1 anwachst, dann wirdsich der Baum von v in seiner Große mindestens verdoppeln.

I Also ist die Tiefe aller Baume durch log2(|V |) beschrankt.


Die Union-Find Datenstruktur: Das Fazit

Ein Union-Schritt benotigt nur konstante Zeit, wahrend ein Find-Schritthochstens logarithmische Zeit benotigt.

I Mit der Union-Operation modifizieren wir den Wald!I Fur Kruskals Algorithmus benotigen zwei Datenstrukturen, namlich

I die Union-Find Datenstruktur undI eine zweite Datenstruktur, die die Kanten des minimalen

Spannbaums abspeichert.

Damit hat Kruskals Algorithmus eine Laufzeit von O(|E | · log |V |)


Kapitel 4: Das Worterbuch


Der abstrakte Datentyp”Worterbuch“

Ein Worterbuch fur eine gegebene Menge S besteht aus den folgendenOperationen:

I insert(x): Fuge x zu S hinzu, d.h. setze S = S ∪ {x}.I remove(x): Entferne x aus S , d.h. setze S = S − {x}.I lookup(x): Finde heraus, ob x in liegt, und wenn ja, greife

gegebenenfalls auf den Datensatz von x zu.

I In einer Firmendatenbank werden Kundendaten in der Form(Kundenummer, Info) abgespeichert.

I Die Kundennummer stellt den Schlussel x dar.I insert(x): Fuge den Datensatz eines neuen Kunden mit

Kundenummer x ein.I remove(x): Entferne den Datensatz des entsprechenden Kunden.I lookup(x): Greife auf den Datensatz des Kunden mit Kundennummer

x zu.


Suchmaschinen

Suchmaschinen mussen Stichworte und Webseiten verwalten.Insbesondere mussen zu jedem Stichwort alle relevanten Webseitenaufgelistet werden.

I Fur jedes Stichwort s mussen die relevanten Webseiten schnellverfugbar sein.

I Neue Stichworte sind gegebenenfalls einzufugen

I Unter einem Stichwort mussen neue Webseiten abgelegt undveraltete geloscht werden konnen

I Veraltete Stichworte sind zu entfernen


Datenstrukturen fur Worterbucher

I Wie sollten statische Worterbucher, also Worterbucher die nurlookup benutzen, implementiert werden?

I Wir konnten die Menge der n gespeicherten Schlussel zuerstsortieren. Eine lookup-Operation gelingt dann in logarithmischer Zeitdurch binare Suche.

I Oder aber wir haben noch mehr Gluck und haben eine schnellberechenbare Namensfunktion, die fur jeden Schlussel die Positiondes Schlussels bestimmt.

Leider sind die interessanten Worterbucher dynamisch.

I Konnten wir Heaps benutzen? Das Einfugen gelingt muhelos, aberschon das Suchen ist extrem muhselig. (Warum?)

Wir benotigen eine Datenstruktur, die schnell durchsuchbar und anbeliebigen Stellen modifizierbar ist.


Binare Suchbaume

T sei ein geordneter binarer Baum. Jeder Knoten v von T speichert einPaar daten(v) = (Schlussel(v), Info(v)).T heißt binarer Suchbaum, wenn T die folgenden Eigenschaften hat:

(a) Fur jeden Schlusselwert x gibt es hochstens einen Knoten v mitSchlussel (v) = x .

(b) Fur jeden Knoten v , jeden Knoten vlinks im linken Teilbaum von vund jeden Knoten vrechts im rechten Teilbaum von v gilt

Schlussel(vlinks) < Schlussel(v) < Schlussel(vrechts).

Binare Suchbaume unterstutzen die binare Suche!


Operation lookup(x)

lookup(x) sucht im Binaren Suchbaum folgendermaßen nach demKnoten mit Schlussel x :

(1) Sei r die Wurzel des binaren Suchbaums. Setze v = r ./* Wir beginnen die Suche an der Wurzel. */

(2) Wenn wir am Knoten v angelangt sind, vergleichen wirx mit Schlussel(v):

I x = Schlussel(v): Wir haben den Schlussel gefunden.I x < Schlussel(v): Wir suchen im linken Teilbaum weiter.I x > Schlussel(v): Diesmal muss im rechten Teilbaum

weitergesucht werden.

Lookup benotigt Zeit Θ(t), wobei t die Tiefe des Knoten ist, der denSchlussel x speichert.


Die Struktur Knoten

typedef struct Knoten {

schluesseltyp schluessel; infotyp info;

//Schluesseltyp und Infotyp sind vorspezifizierte Typen,

//z.B. int oder string

Knoten *links, *rechts;

Knoten(schluesseltyp s, infotyp i, Knoten *l, Knoten *r)

{ schluessel = s; info = i; links = l; rechts = r; }//Konstruktor.

};


Die Klasse Binarer Suchbaum

class bsbaum{

private:

Knoten *Kopf;

public:

bsbaum( ) { Kopf = new Knoten (0,0,0,0); }// Konstruktor

// Kopf->rechts wird stets auf die Wurzel zeigen

Knoten *lookup(schluesseltyp x);

void insert(schluesseltyp x, infotyp info);

void remove(schluesseltyp x);

void inorder( );

};


Beispiel binarer Suchbaumschluessel: 0

info: 0

*links *rechts

*Kopf

schluessel: 11

info: Saturn

*links *rechts

schluessel: 8

info: Erde

*links *rechts

schluessel: 17

info: Merkur

*links *rechts

schluessel: 3

info: Venus

*links *rechts

schluessel: 14

info: Mars

*links *rechts

schluessel: 19

info: Uranus

*links *rechts

schluessel: 5

info: Jupiter

*links *rechts

schluessel: 12

info: Erde

*links *rechts

schluessel: 15

info: Neptun

*links *rechts


Die Funktion lookup

Knoten *bsbaum::lookup (schluesseltyp x){

Knoten *Zeiger = Kopf->rechts;

while ((Zeiger != 0) && (x != Zeiger->schluessel)){

if ( x < Zeiger->schluessel )

Zeiger = Zeiger->links;

else

Zeiger = Zeiger->rechts;

}

return Zeiger;

}


Beispiel Lookup

42

23 57

12 37 53 62

7 28 41 49 56 61

10 35 44 52 59

lookup(52) 52>42

52<57

52<53

52>49

Anmerkung: In diesem Beispiel sind fur jeden Knoten im binaren Suchbaum nur der

Schlussel schluessel und nicht die Information info dargestellt.


Beispiel Lookup

42

23 57

12 37 53 62

7 28 41 49 56 61

10 35 44 52 59

lookup(19) 19<42

19<23

19>12




Binare Suchbaume: Insert

Suche zuerst nach x . Sollten wir x finden, uberschreibe den altenInfo-Teil; sonst fuge den Schlussel dort ein, wo die Suche scheitert.

void bsbaum::insert (schluesseltyp x, infotyp info){Knoten *Vater, *Zeiger;

Vater = Kopf; Zeiger = Kopf->rechts;

while ((Zeiger != 0) && (x != Zeiger->schluessel)){Vater = Zeiger;

if (x < Zeiger->schluessel) Zeiger = Zeiger->links;

else Zeiger = Zeiger->rechts;

}if (Zeiger == 0){

Zeiger = new Knoten (x, info, 0, 0);

if (x < Vater->schluessel) Vater->links = Zeiger;

else Vater->rechts = Zeiger;

}else Zeiger->info = info;

}Mariano Zelke Datenstrukturen 26/29

Beispiel Insert

42

23 57

12 37 53 62

7 28 41 49 56 61

10 35 44 52 59

insert(52,info) 52>42

52<57

52<53

52>49

Info-Teil wirdmit infouberschrieben




Beispiel Insert

42

23 57

12 37 53 62

7 19 28 41 49 56 61

10 35 44 52 59

insert(19,info) 19<42

19<23

19>12

Neuer Knoten mitSchlussel 19 undinfo als Info-Teilwird erzeugt




Binare Suchbaume: Remove

Zuerst suche den Schlussel x . Wenn die Suche im Knoten v endet:

I Wenn v ein Blatt ist: Entferne v .

I Wenn v genau ein Kind w hat: Entferne v und mache den Vatervon v zum Vater von w .

I Wenn v zwei Kinder hat: Ersetze v durch den kleinsten Schlussel sim rechten Teilbaum von v .

I Der Knoten u speichere den Schlussel s.I u ist als linkester Knoten im rechten Teilbaum leicht zu finden.I u hat kein linkes Kind und kann damit sofort entfernt werden.


Beispiel Remove

42

23 57

12 37 53 62

7 28 41 49 61

10 35 44 52 59

remove(56)




Beispiel Remove

42

23 57

12 37 53 62

7 28 41 49 61

10 35 44 52 59

remove(56)




Beispiel Remove

42

23 57

12 37 62

7 28 41 49 61

10 35 44 52 59

remove(53)




Beispiel Remove

42

23 57

12 37 49 62

7 28 41 44 52 61

10 35 59

remove(53)




Beispiel Remove

42

57

12 37 49 62

7 28 41 44 52 61

10 35 59

remove(23)




Beispiel Remove

42

28 57

12 37 49 62

7 41 44 52 61

10 35 59

remove(23)




Beispiel Remove

42

28 57

12 37 49 62

7 35 41 44 52 61

10 59

remove(23)




Documents

Datenstrukturen - uni-frankfurt.de · 2012. 6. 19. · Priorit atswarteschlangen: Zusammenfassung (a)Ein Heap mit n Priorit aten unterst utzt jede der Operationen insert, delete max,