Post on 04-Jun-2018
transcript
Informatik 2Datenstrukturen
Prof. Dr.-Ing. Holger Vogelsang holger.vogelsang@hs-karlsruhe.de
Holger Vogelsang
Inhaltsverzeichnis
Abstrakte Datentypen (3) Datenstrukturen in Java (11) Elementare Datenstrukturen (14) Iteratoren (42) Streams (58) Hashtabellen (67) Bäume (113) Graphen (202)
Informatik 2 - Datenstrukturen 2
Holger Vogelsang
Abstrakte DatentypenÜbersicht
Informatik 2 - Datenstrukturen 3
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 4
Abstrakte DatentypenÜbersicht
Bisher: Einführung in objektorientierte Programmierung Einfache Datenstrukturen wie Array, Vektor und Liste
Jetzt: Festlegung von Schnittstelle und Funktionalität einer Datenstruktur, ohne eine konkrete
Implementierung zu verwenden
Definition: Abstrakter DatentypEin abstrakter Datentyp (ADT) ist ein Datentyp (eine Menge von Werten und eine Sammlung von Operationen auf diesen Werten), der nur über eine Schnittstelle zugänglich ist. Ein ADT kann bei identischer Funktionalität unterschiedliche mögliche Implementierungen besitzen.
Holger Vogelsang Informatik 2 - Datenstrukturen 5
Abstrakte DatentypenÜbersicht
Eine ADT-Spezifikation besteht aus einer Signatur und Axiomen (hier stark vereinfacht dargestellt, die mathematischen Begriffe wurden teilweise nicht verwendet). Signatur ∑ = (S, Ω) mit
- S = Die Menge von Datentypen, die der ADT verwendet. Einer der Datentypen wird in der Regel durch den ADT neu definiert. Die anderen existieren bereits.
- Ω = Die Menge von Methoden und Konstanten des ADT. Axiome legen die Semantik und damit das Verhalten des ADT unabhängig von einer
konkreten Implementierung fest. In diesen Unterlagen werden teilweise Beispiele aus dem Buch „Algorithmen und
Datenstrukturen“ von Saake und Sattler übernommen. Die Darstellung der ADTs entspricht auch der Syntax aus dem Buch.
Holger Vogelsang Informatik 2 - Datenstrukturen 6
Abstrakte DatentypenBeispiel: Liste
Unvollständiger ADT für eine Liste List von Elementen des Datentyps T.type List(T)import Natoperators
[] List_:_ : T × List ListaddFirst : List × T ListgetFirst : List TgetTail : List Listsize : List Nat
axioms ∀l : List, ∀x : TgetTail(addFirst(l, x)) = lgetFirst(addFirst(l, x)) = xgetFirst(x : l) = xgetTail(x : l) = lsize([]) = 0size(x : l) = succ(size(l))
x : l Element xund weitereListenelemente in l
[] erzeugt eineneue, leere Liste
succ entstammt ADTfür natürliche Zahlen
_:_ Konstruktions-vorschrift (neuer Operator)
Holger Vogelsang Informatik 2 - Datenstrukturen 7
Abstrakte DatentypenBeispiel: Liste
Mögliche Listen: [] leere Liste 1 : [] Liste mit dem Element 1 1 : 2 : 3 : 4 : [] Liste mit den Elementen 1 bis 4
Deutlich erkennbar: Das Wissen über die konkrete Implementierung der Liste ist für die Anwendung nicht erforderlich. In einer Programmiersprache: Schnittstelle der Klasse (öffentliche Methoden und
Datentypen) sowie die Dokumentation des Verhalten sind erforderlich. Die Art der Implementierung ist unwichtig (sofern sie das Laufzeitverhalten nicht
beeinflusst). Wozu dient das Wissen über ADTs?
ADT könnte in Java eine Schnittstelle (ein interface) sein. Die konkrete Implementierung implementiert die Schnittstelle. Es lässt sich prima „auf der Schnittstelle“ arbeiten.
Holger Vogelsang Informatik 2 - Datenstrukturen 8
Abstrakte DatentypenAnwendung eines ADT
Beispiel ADT List und konkrete Java-Umsetzung der Operatorentype List(T)import Natoperators
[] List_:_ : T × List ListaddFirst : List × T ListgetFirst : List TgetTail : List Listsize : List Nat
axioms ∀l : List, ∀x : TgetTail(addFirst(l, x)) = lgetFirst(addFirst(l, x)) = xgetFirst(x : l) = xgetTail(x : l) = lsize([]) = 0size(x : l) = succ(size(l))
<<interface>>List
+add(int i, e: T): boolean+get(index: int): T+remove(index: int): T+size(): int
LinkedList
+add(int i, e: T): boolean+get(index: int): T+remove(index: int): T+size(): int
ArrayList
+add(int i, e: T): boolean+get(index: int): T+remove(index: int): T+size(): int
VerketteteListe
Vektor
T: class
T: class T: class
Holger Vogelsang Informatik 2 - Datenstrukturen 9
Abstrakte DatentypenAnwendung eines ADT
Beispiel ADT List und konkrete Java-Umsetzung der Axiometype List(T)import Natoperators
[] List_:_ : T × List ListaddFirst : List × T ListgetFirst : List TgetTail : List Listsize : List Nat
axioms ∀l : List, ∀x : TgetTail(addFirst(l, x)) = lgetFirst(addFirst(l, x)) = xgetFirst(x : l) = xgetTail(x : l) = lsize([]) = 0size(x : l) = succ(size(l))
z.B. als Dokumentation oderzur Validierung einer Implementierung
Holger Vogelsang Informatik 2 - Datenstrukturen 10
Abstrakte DatentypenADT: Beschreibung der Axiome
Die Axiome können durch nahezu beliebige „Sprachen“ beschrieben werden. Komplexere Aussagen sind z.B. mit OCaml (funktionale Programmiersprache, siehe
http://caml.inria.fr/) möglich soll hier nicht näher vertieft werden.
Holger Vogelsang
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
Datenstrukturen in JavaÜbersicht
Informatik 2 - Datenstrukturen 11
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 12
Datenstrukturen in JavaÜbersicht
Vereinfachte Übersicht über die Collections-Klassen in Java
Holger Vogelsang
Datenstrukturen in JavaSchnittstellen
Iterable<E>: Über die Datenstruktur kann direkt iteriert werden siehe Iteratoren. Collection<E>: Gruppe von Elementen, Duplikate können erlaubt sein List<E>: Collection mit einer Ordnung, Indexzugriff ist erlaubt (möglicherweise
ineffizient) RandomAccess: Leere Schnittstelle, der Indexzugriff ist mit konstanter Zeit möglich. Queue<E>: spezielle Queue-Operationen vorhanden Deque<E>: Queue mit Einfüge- und Löschoperationen an Anfang und Ende Set<E>: Menge von Elementen ohne Duplikate SortedSet<E>: Menge mit einer Totalordnung der Elemente (anhand ihrer natürlichen
Ordnung oder anhand eines Vergleichs-Objektes) NavigableSet<E>: SortedSet mit Methoden, um kleinere oder größere Elemente zu
finden Map<K,V>: Bildet Schlüssel-Objekte (K) auf Werte (V) ab. SortedMap<K,V>: Eine Map mit einer Totalordnung der Elemente NavigableMap<K,V>: SortedMap mit Methoden, um kleinere oder größere Schlüssel zu
finden.Informatik 2 - Datenstrukturen 13
Holger Vogelsang
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
Elementare DatenstrukturenÜbersicht
Informatik 2 - Datenstrukturen 14
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 15
Elementare DatenstrukturenÜbersicht in Java
Elementare Datenstrukturen
Holger Vogelsang Informatik 2 - Datenstrukturen 16
Elementare DatenstrukturenVektor – Prinzip
Die Klassen ArrayList<E> und Vector<E> verwalten dynamisch beliebig viele Objekte. Die Anordnung der Objekte erfolgt sequentiell. Die interne Implementierung erfolgt durch ein Array. Der Vektor besitzt eine Referenz auf den Speicherbereich. Ein Vektor eignet sich besonders für einen schnellen freien Zugriff über Indizes auf die
Elemente. Der Indexzugriff erfolgt immer geprüft. Vector ist im Gegensatz zu ArrayList thread-sicher und damit langsamer.
Extra Platz0 1 2 3 4 5 6 7
ArrayList
-values[*]: E-size: int
E: classArrayList
size
Holger Vogelsang Informatik 2 - Datenstrukturen 17
Elementare DatenstrukturenBeispiel zu ArrayList
Beispiel:import java.util.ArrayList;
public class ArrayListTest public static void main(String[] args)
ArrayList<Integer> contents = new ArrayList<>(10);
for (int i = 0; i < 10; i++) contents.add(i * i);
int v = contents.get(12); // Geprüfter Zugriff -->// Abfangen der Fehler
System.out.println(contents.size());System.out.println(contents.contains(2));
Holger Vogelsang Informatik 2 - Datenstrukturen 18
Elementare DatenstrukturenArrayList und Vektor in Java
Beide implementieren RandomAccess: Indexzugriff in konstanter Zeit
Holger Vogelsang Informatik 2 - Datenstrukturen 19
Elementare DatenstrukturenVektor – Aufwandsabschätzungen
Aufwandsabschätzungen für die Vektor-Klassen
Operation Aufwand
Einfügen O(N)
Löschen O(N)
Indexzugriff O(1)
Suche, sortierte Daten O(ln N) Binärsuche
Suche, unsortierte Daten O(N) sequentielles Durchlaufen
Holger Vogelsang Informatik 2 - Datenstrukturen 20
Elementare DatenstrukturenListe: Prinzip
Prinzip einer einfach verketteten Liste:
Die Liste besitzt einen Kopf und ein Ende. Jeder Listeneintrag verweist auf seinen Nachfolger. Jeder Listeneintrag beinhaltet die Nutzdaten.
LinkedList
LinkedListE: class
Listelementvalue
Listelementvalue
Listelementvalue
ListelementE: class
-value: E
last
first
first
last
0, 1
0, 10, 1
next
Holger Vogelsang Informatik 2 - Datenstrukturen 21
Elementare DatenstrukturenListe: Prinzip
Prinzip einer doppelt verketteten Liste:
Die Liste besitzt einen Kopf und ein Ende. Jeder Listeneintrag verweist auf seinen Nachfolger und Vorgänger Jeder Listeneintrag beinhaltet die Nutzdaten.
LinkedList
Listelementvalue
Listelementvalue
Listelementvalue
last
first
LinkedListE: class
ListelementE: class
-value: E
first
last
0, 1
0, 10, 1
next
0, 1 prev
Holger Vogelsang Informatik 2 - Datenstrukturen 22
Elementare DatenstrukturenListe in Java
LinkedList implementiert nicht RandomAccess: Indexzugriff nicht in konstanter Zeit!
Holger Vogelsang Informatik 2 - Datenstrukturen 23
Elementare DatenstrukturenListe – Aufwandsabschätzung
Operation Aufwand
Einfügen (an Index x) O(N) sequentielles Durchlaufen
Einfügen (Anfang, Ende) O(1)
Löschen (an Index x) O(N) sequentielles Durchlaufen
Löschen (Anfang, Ende) O(1)
Indexzugriff O(N) sequentielles Durchlaufen
Suche, sortierte Daten O(N) sequentielles Durchlaufen
Suche, unsortierte Daten O(N) sequentielles Durchlaufen
Holger Vogelsang
Elementare DatenstrukturenBeste Eigenschaften von Vektor und Liste kombinieren
Lassen sich die guten Eigenschaften von Vektor und Liste kombinieren? Schnelles Einfügen und Löschen an Anfang und Ende Indexzugriff Wiederholtes schnelles Einfügen und Löschen an benachbarten Positionen
(Lokalitätseigenschaft) Ja: GapList (CircularArrayList, …) Zur Erinnerung: ArrayList (ist ein Vektor)
Die GapList ist ähnlich aufgebaut, kann aber den „Extra Platz“ an einer beliebigen Position, also auch zwischen belegten Einträgen, haben.
Informatik 2 - Datenstrukturen 24
Extra Platz0 1 2 3 4 5 6 7
ArrayList
-values[*]: E-size: int
E: classArrayList
size
Holger Vogelsang
Elementare DatenstrukturenBeste Eigenschaften von Vektor und Liste kombinieren
Ausgangssituation:
Einfügen am Ende (wie bei ArrayList):
Informatik 2 - Datenstrukturen 25
0 1 2 3 4 5 6 7
GapList
E1 E2 E3
Extra Platz
8 9 10 11
0 1 2 3 4 5 6 7
GapList
E1 E2 E3
Extra Platz
8 9 10 11
E4
Holger Vogelsang
Elementare DatenstrukturenBeste Eigenschaften von Vektor und Liste kombinieren
Ausgangssituation:
Einfügen am Anfang (wie bei einem Ring-Puffer):
Informatik 2 - Datenstrukturen 26
0 1 2 3 4 5 6 7
GapList
E1 E2 E3
Extra Platz
8 9 10 11
0 1 2 3 4 5 6 7
GapList
E1 E2 E3
Extra Platz
8 9 10 11
E4
Holger Vogelsang
Elementare DatenstrukturenBeste Eigenschaften von Vektor und Liste kombinieren
Ausgangssituation:
Einfügen in der Mitte zwischen 1 und 2 (die Elemente an der Einfügestelle werden so verschoben, dass dort die Lücke entsteht):
Informatik 2 - Datenstrukturen 27
0 1 2 3 4 5 6 7
GapList
E1 E2 E3
Extra Platz
8 9 10 11
0 1 2 3 4 5 6 7
GapList
E1 E4
Extra Platz
8 9 10 11
E3E2
Holger Vogelsang
Elementare DatenstrukturenBeste Eigenschaften von Vektor und Liste kombinieren
Das Einfügen in eine GapList ist immer dann sehr schnell, wenn an benachbarten Positionen eingefügt wird (Lokalitätseigenschaft).
Das Löschen funktioniert ähnlich wie das Einfügen, ist ebenfalls sehr schnell. Ist die GapList voll, dann wird wir bei einer ArrayList ein neues Array angelegt und alle
Elemente kopiert. Dummerweise gibt es im SDK keine GapList… Ausweg:
Brownies Collections von http://www.magicwerk.org/page-collections-overview.html Bieten weitere schnelle und speichersparendere Array-artige Datenstrukturen sollen
hier nicht betrachtet werden GapList implementiert List und Collection aus dem SDK.
Auch Nachteil: Bei sehr vielen Elementen wird der Aufwand trotzdem recht hoch.
Informatik 2 - Datenstrukturen 28
Holger Vogelsang
Elementare DatenstrukturenUnveränderliche Listen
Bereits bekannt: „Value Objects“ für unveränderliche Objekte Gibt es dasselbe auch bei Datenstrukturen?
Mit Collections.unmodifiableList(List<? extends T list> lässt sich eine unveränderliche Sicht auf eine vorhandene List (und damit z.B. eine ArrayList oder LinkedList) erzeugen. Diese Methode existiert auch für andere Datenstrukturen.
Diese List kann an Methoden übergeben werden, ohne dass der Aufrufer die Listverändern kann.
Der Versuch, die unveränderbare List zu verändern, führt zu einer Exception. Dummerweise ist das den Methoden nicht anzusehen gut testen.
Enthält die List lediglich „Value Objects“, dann kann der Aufrufer sicher sein, dass die aufgerufene Methode keine Änderungen vorgenommen hat.
Unterschied zu den vorgestellten „Value Objects“: Es ist nicht vorgesehen, eine Änderung in Form einer veränderten Kopie zu erstellen und diese Kopie zurückzugeben.
Informatik 2 - Datenstrukturen 29
Holger Vogelsang
Elementare DatenstrukturenUnveränderliche Listen
Beispiel:public void doSomething(List<String> names) // Ist names veränderbar oder nicht??names.add("Vogelsang");
public static void main(String[] args) // Veränderbare ArrayListList<String> names = new ArrayList<>();doSomething(names);// Unveränderbare Sicht auf die ArrayListList<String> unmodNames = Collections.unmodifiableList(names);doDomething(unmodNames);
Die Lösung ist etwas unbefriedigend, zumal keine veränderte Kopie erzeugt werden kann. Leider bietet das JDK auch keine bessere Lösung Ausweg: Fremdbibliotheken.
Informatik 2 - Datenstrukturen 30
KeinFehler
Unsupported-OperationException
Holger Vogelsang
Elementare DatenstrukturenUnveränderliche Listen
Beispiel: Open-Source-Bibliothek „a-foundation“ (https://github.com/arnohaase/a-foundation), angelehnt an Datenstrukturen aus der Sprache Scala.
Anderer Aufbau der Listen: Eine Liste kennt ihr erstes Element sowie den Rest der Liste, der wiederum eine Liste ist. Das letzte Element ist die leere Liste nil. Idee: siehe ADT-Einführung!
Beispiel:// Leere Liste erzeugenAList<String> noNames = Alist.<String>nil();// Neue Liste erzeugen, dabei jeweils Elemente vorne in "Kopien" von noNames einfügen// (noNames bleibt unverändert).AList<String> names = noNames.cons("Vogelsang").cons("Pape");AList<String> names2 = names.cons("Körner");AList<String> names3 = names.cons("Hoffmann");System.out.println(noNames); // Leere Liste []System.out.println(names); // Liste [Pape, Vogelsang]System.out.println(names2); // Liste [Körner, Pape, Vogelsang]System.out.println(names3); // Liste [Hoffmann, Pape, Vogelsang]
Informatik 2 - Datenstrukturen 31
Holger Vogelsang
Elementare DatenstrukturenUnveränderliche Listen
Interne Repräsentation:
Informatik 2 - Datenstrukturen 32
nil
"Pape"
"Vogelsang"
"Körner"
"Hoffmann"
names2
names3names
Holger Vogelsang
Elementare DatenstrukturenUnveränderliche Listen
Da sich die Listen nie ändern, können neue Listen auf die Daten aller Listen verweisen. Das klappt nur, wenn die Listen lediglich „Value Objects“ enthalten.
Fazit: Unveränderliche Objekte und Datenstrukturen vereinfachen manchmal die
Programmierung und erlauben besser lesbaren Code. Sie können, müssen aber nicht, effizienter als veränderbare Objekte und
Datenstrukturen sein. Im Zusammenhang mit Multithreading (siehe drittes Semester) sind solche
unveränderlichen Daten manchmal ganz hilfreich.
Informatik 2 - Datenstrukturen 33
Holger Vogelsang Informatik 2 - Datenstrukturen 34
Elementare DatenstrukturenQueue – Prinzip
Prinzip einer Queue (Warteschlange):
Daten werden in einer Queue am Ende mit offer eingetragen und am Anfang der Queue mit poll entfernt Warteschlange (häufig auch push/pop).
Es gibt einige Container-Klassen, die Queue-Funktionalität einsetzen. Beispiel: LinkedList. Einsatzgebiete
einfaches Nachrichtensystem (Nachricht ablegen = offer, Nachricht abholen = poll). allgemeine asynchrone Kommunikation zwischen Auftragnehmer und Auftraggeber
Queue
0 1 2 3
Holger Vogelsang Informatik 2 - Datenstrukturen 35
Elementare DatenstrukturenQueue in Java
LinkedList implementiert Queue
Holger Vogelsang
Elementare DatenstrukturenQueue in Java
Die Methoden gibt es doppelt (aus Queue und Deque):
Informatik 2 - Datenstrukturen 36
Funktion Methoden mit Ausnahmen Methoden ohne Ausnahmen(Fehlercode)
Einfügen (push) add(E), push(E) offer(E), addLast(E)
Entfernen (pop) remove(), removeFirst() poll(), pollFirst()
Auslesen (top) element(), getFirst() peek(), peekFirst()
Holger Vogelsang Informatik 2 - Datenstrukturen 37
Elementare DatenstrukturenQueue – Prinzip
Arbeitsweise einer Queue an einem Beispiel. Initialzustand:
offer(E4):
poll():
Queue
Queue
Queue
offer
poll
0 1 2
0 1 2 3
E1 E2 E3
E1 E2 E3 E4
0 1 2
E2 E3 E4
Holger Vogelsang Informatik 2 - Datenstrukturen 38
Elementare DatenstrukturenStack – Prinzip
Prinzip eines Stacks (Stapel):
Daten werden in einem Stack am Ende mit offer eingetragen und ebenfalls am Ende mit poll entfernt Stapel (häufig auch push/pop).
Einsatzgebiete u.a.: Zwischenspeicherung von Objekten, wenn eine Rekursion zu einer Iteration aufgelöst
wird. Text-Parser.
Stack
0 1 2 3
Holger Vogelsang Informatik 2 - Datenstrukturen 39
Elementare DatenstrukturenStack in Java
Es gibt eine Stack-Klasse, die aber nicht optimal ist. Besser: Klasse, die Deque implementiert.
Holger Vogelsang
Elementare DatenstrukturenStack in Java
Die Methoden gibt es doppelt (aus Queue und Deque):
Informatik 2 - Datenstrukturen 40
Funktion Methoden mit Ausnahmen Methoden ohne Ausnahmen(Fehlercode)
Einfügen (push) add(E), push(E) offer(E), addLast(E)
Entfernen (pop) removeLast() pollLast()
Auslesen (top) getLast() peekLast()
Holger Vogelsang Informatik 2 - Datenstrukturen 41
Elementare DatenstrukturenStack – Prinzip
Arbeitsweise eines Stacks an einem Beispiel. Initialzustand:
offer(E4):
pollLast():
Stack
Stack
Stack
0 1 2
E1 E2 E3
offer
0 1 2 3
E1 E2 E3 E4
E1 E2 E3
pollLast
0 1 2
Holger Vogelsang
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
IteratorenÜbersicht
Informatik 2 - Datenstrukturen 42
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 43
IteratorenMotivation
Wie lässt sich ein Algorithmus schreiben, der unabhängig von einer konkreten Datenstruktur arbeiten kann?
Wie können beliebig viele Algorithmen quasi parallel eine unbekannte Datenstruktur bearbeiten?
Holger Vogelsang Informatik 2 - Datenstrukturen 44
IteratorenKonzept
Problem: Bisher werden Listen oder Vektoren durch eine Schleife, die direkt auf die Elemente des Containers zugreift, durchlaufen. Wie kann aber ein Algorithmus unabhängig von der Klasse (dem Container) geschrieben werden?
Ziel: Konstruktion eines Algorithmus unabhängig von der konkreten Klasse (dem Container). Lösung: Iteratoren dienen als Bindeglied zwischen den Containern und Algorithmen auf
Containern Prinzip „Umkehr der Abhängigkeiten“! Iteratoren sind abstrakte Datentypen, mit deren Hilfe auf eine Folge von Objekten
zugegriffen werden kann. Ein Iterator verweist immer auf ein Objekt innerhalb einer Folge von Objekten. Die Vorlesung behandelt Iteratoren nicht vollständig.
Holger Vogelsang Informatik 2 - Datenstrukturen 45
IteratorenKonzept
Mögliche Vektor- und Listenimplementierungen mit Sortierung der Elemente.
Mit einem Iterator können alle Elemente in ihrer Sortierreihenfolge besucht werden.
ArrayList
Extra Platz
LinkedListlast
first
sequentielles Durchlaufen
sequentielles Durchlaufen
Holger Vogelsang Informatik 2 - Datenstrukturen 46
IteratorenKonzept
Iterator als Bindeglied zwischen Algorithmus und Datenstruktur:
ArrayList
Algorithmus
last
first
Zugriff auf die Datenstrukturüber eine einheitliche
Schnittstelle
LinkedList
erzeugtZugriff
erzeugtZugriff
Holger Vogelsang Informatik 2 - Datenstrukturen 47
IteratorenFunktionsweise
Jede Datenstruktur bietet eigene Iteratoren, die eine der beiden folgenden Schnittstellen implementieren:
normaler Iterator, um eine Collectionvom Anfang bis zum Ende zudurchlaufen
Iterator, um eine List vorwärts und rückwärts zudurchlaufen• erlaubt das Ersetzen von Elementen• ermöglicht das Auslesen des aktuellen Indexes
Holger Vogelsang Informatik 2 - Datenstrukturen 48
IteratorenFunktionsweise
Jede Datenstruktur hat Methoden, die die Iteratorobjekte erzeugen:
Datenstruktor Erzeugung des Iterators
Collection<E> Iterator<E> iterator()
List<E> ListIterator<E> listIterator()undIterator<E> iterator()(weil List auch eine Collection ist)
Holger Vogelsang Informatik 2 - Datenstrukturen 49
IteratorenBeispiel
import java.util.ArrayList;import java.util.Iterator;import java.util.ListIterator;
public class IteratorTest
public static void print(Iterator<?> iter)
while (iter.hasNext()) System.out.println(iter.next());
public static <E> void modify(ListIterator<? super E> iter,E value)
while (iter.hasNext()) iter.next();iter.set(value);
public static void main(String[] args)
ArrayList<String> source =new ArrayList<>();
source.add("Hallo 1");source.add("Hallo 2");source.add("Hallo 3");source.add("Hallo 4");
print(source.iterator());
modify(source.listIterator(),"----");
Holger Vogelsang Informatik 2 - Datenstrukturen 50
IteratorenWeiteres Beispiel
import java.util.ArrayList;import java.util.Iterator;import java.util.ListIterator;
public class IteratorTest
public static <E> void copy(ListIterator<? super E> dest,ListIterator<? extends E> source) while (source.hasNext()) // Im Ziel überschreiben?if (dest.hasNext())
dest.next();dest.set(source.next());
// Anhängen, da Ziel kürzerelse
dest.add(source.next());
public static void main(String[] args)
ArrayList<String> source =new ArrayList<>();
source.add("Hallo 1");source.add("Hallo 2");source.add("Hallo 3");source.add("Hallo 4");
ArrayList<String> dest =new ArrayList<>();
copy(dest.listIterator(),source.listIterator());
kopiert von ArrayList in ArrayList
Holger Vogelsang Informatik 2 - Datenstrukturen 51
IteratorenWeiteres Beispiel – Variante 2
copy arbeitet auch mit LinkedList, Vector, und anderen Datentypen.public static void main(
String[] args) LinkedList<String> source =
new LinkedList<>();
source.add("Hallo 1");source.add("Hallo 2");source.add("Hallo 3");source.add("Hallo 4");
LinkedList<String> dest =new LinkedList<>();
copy(dest.listIterator(),source.listIterator());
copy kann auch zwischen unterschiedlichen Containern kopieren.
public static void main(String[] args)
ArrayList<String> source =new ArrayList<>();
source.add("Hallo 1");source.add("Hallo 2");source.add("Hallo 3");source.add("Hallo 4");
LinkedList<String> dest =new LinkedList<>();
copy(dest.listIterator(),source.listIterator());
Im SDK wird aber eher mit Collection und List statt mit Iteratoren gearbeitet.
Holger Vogelsang Informatik 2 - Datenstrukturen 52
IteratorenBedeutung von Iteratoren: Beispiel
Die folgenden Klassen verwalten ein einfaches Dateisystem direkt im Hauptspeicher des Computers.
File
-name: String-access: int-contents: byte[*]
Directory
-name: String-access: intfiles
0..* subdirectories
0..*
0, 1parent
// Eine Datei im Dateisystempublic class File
private String name; // Nameprivate int access; // Rechteprivate byte[] contents; // Inhalt
public File(String name,int access, byte[] contents)
public boolean equals(Object other)
//
// Verzeichnis im Dateisystempublic class Directory private String name;private Directory parent; // Vater
private LinkedList<Directory>subdirectories;
private LinkedList<File> files;private int access;
//
Holger Vogelsang Informatik 2 - Datenstrukturen 53
IteratorenBedeutung von Iteratoren: Beispiel
Es ergibt sich ein Baum aus Verzeichnissen, in denen jeweils eine Anzahl von Dateien liegen kann.
Ziel: Schreiben einiger Methoden der Directory-Klasse, die über Iteratoren auf den Baum zugreifen.
Zählen aller Dateien Methode der Klasse Directory, die die Anzahl der Dateien in dem Verzeichnis sowie seinen
Unterverzeichnissen ermittelt.public int countFiles() int size = files.size();for (Iterator<Directory> iter = subdirectories.iterator(); iter.hasNext();)
Directory currentDirectory = iter.next();size += currentDirectory.countFiles();
return size;
Holger Vogelsang Informatik 2 - Datenstrukturen 54
IteratorenBedeutung von Iteratoren: Beispiel
Suchen einer Datei Methode der Klasse Directory, die nur in diesem Verzeichnis (nicht in seinen
Unterverzeichnissen) eine Datei sucht. Doppelte Dateinamen kommen nicht vor. public boolean containsFile(File file) for (Iterator<File> iter = files.iterator(); iter.hasNext(); )
if (iter.next().equals(file)) return true;
return false;
Holger Vogelsang Informatik 2 - Datenstrukturen 55
IteratorenBedeutung von Iteratoren
Abstrakte Zugriffe auf Datenstrukturen (nicht auf konkrete Collection-Klassen): Iteratoren Methoden der Schnittstellen List und Collection
- Viele Algorithmen sind auch als statische Methoden in der Klasse Collectionsvorhanden (sortieren usw.).
- Diese arbeiten fast immer auf den Schnittstellen List und Collection.
Holger Vogelsang Informatik 2 - Datenstrukturen 56
IteratorenEine Auswahl an Algorithmen der Klasse Collections
Algorithmus (Funktion) Bedeutung
static <T> void copy(List<? super T> dest,List<? extends T> src)
Kopiert Elemente eines Containers in einen anderen. Dabei werden die vorhandenen Elemente des Ziels überschrieben. Das Ziel muss genügend Platz für alle Elemente haben. Beispiel:LinkedList<String> src =
new LinkedList<>();LinkedList<String> dest =
new LinkedList<>();src.add("Test");Collections.copy(dest, src);
static <T> void fill(List<? super T> list, T obj)
Überschreibt alle Elemente eines Ziel-Containers mit einem festen Wert. Beispiel:ArrayList<String> a = new ArrayList<>();a.add("42");a.add("66");Collections.fill(a, "9");
Holger Vogelsang Informatik 2 - Datenstrukturen 57
IteratorenEine Auswahl an Algorithmen der Klasse Collections
Algorithmus (Funktion) Bedeutung
static<T extends Comparable<? super T>> void sort(List<T> list)
Mit sort kann der Inhalt eines Containers sortiert werden. Diese Methode verwendet den Standardtest equals, um zwei Objekte zu vergleichen. Beispiel:Vector<String> v = new Vector<>();v.add("66");v.add("42");Collections.sort(v);
static void sort(List<T> list,Comparator<? super T> c)
Diese Sortier-Methode verwendet den übergebenen Vergleicher, um zwei Objekte zu vergleichen.
static void reverse(List<?> list) Dreht die Reihenfolge der Elemente um. Beispiel:Vector<String> v = new Vector<>();v.add("66");v.add("42");Collections.reverse(v);
Holger Vogelsang Informatik 2 - Datenstrukturen 58
StreamsMotivation
Mit Iteratoren lassen sich Datenstrukturen durchlaufen. Geht das auch eleganter? Wie kann das Durchlaufen von den Aktionen auf den einzelnen Elementen
entkoppelt werden? Wie lassen sich Datenstrukturen parallel effizienter bearbeiten nicht Bestandteil
dieser Vorlesung.
Holger Vogelsang Informatik 2 - Datenstrukturen 59
StreamsMotivation
Zur Erinnerung: Durchlaufen einer Datenstruktur mit Hilfe von Iteratoren, Beispiel:for (Iterator<String> iter = names.iterator(); iter.hasNext(); ) System.out.println(iter.next());
Beispiel zur Summation aller positiven Werte:int sum = 0;for (Iterator<Integer> iter = values.iterator(); iter.hasNext(); ) int value = iter.next();if (value > 0)
sum += value;
Es zeigt sich ein immer wiederkehrendes Muster: äußere Schleife zum Durchlaufen innerhalb der Schleife mit dem eigentlichen Code
Problem: Große Datenstrukturen werden immer sequentiell abgearbeitet, obwohl im Computer vielleicht einige Prozessorkerne nichts zu tun haben.
Die Stream-API übernimmt das Durchlaufen der Collection-Klassen und Anwenden der Funktionen auf die einzelnen Elemente.
Holger Vogelsang
StreamsEinführung
Was bietet die Stream-API? Filtern von Werten (z.B. nur Strings einer bestimmten Länge auswählen) Abbilden von Daten eines Typs auf andere Typen (z.B. automatisch die Kundennummer
aus einem Kundenobjekt auslesen) Begrenzung der Anzahl der Elemente (z.B. nur die ersten 100 Elemente berücksichtigen) Sortierung der Elemente beim Auslesen Reduktions-Operationen wie z.B. Summenbildung, erstes Element mit einer bestimmten
Bedingung suchen, … Und vieles mehr, was aus Zeitgründen hier entfällt.
Die übergebenen Funktionen sind Lambda-Ausdrücke. Ablauf:
Die Collections-Klassen besitzen eine Methode stream, um einen Stream zu erzeugen. Die Funktionen dürfen sehr häufig keine Nebeneffekte haben (siehe API-Dokumentation).
Informatik 2 - Datenstrukturen 60
Datenstruktur Funktion1 Funktion2 Funktion3 Ergebnis
Holger Vogelsang
StreamsEinführung
Beispiel zur Summation aller positiven Werte:int sum = values.stream().filter(v -> v > 0).mapToInt(x -> x).sum();
Was passiert hier? stream() erzeugt den „Strom von Daten“ aus der Datenquelle values. Filter erwartet als Parameter ein Objekt der Schnittstelle Predicate<T> mit diesem
vereinfachten Aufbau:@FunctionalInterfacepublic interface Predicate<T>
boolean test(T t);
Die Methode test wertet den Übergabeparameter aus und entscheidet, ob er die Bedingung erfüllt oder nicht.
Alle Werte, die der Filter durchlässt, werden aufsummiert:
Informatik 2 - Datenstrukturen 61
values filter() mapToInt() sum
Alle Werteaus values
v > 0 Alle Werteaus values,die größerals 0 sind.
Werteals int-Zahlen
sum()SummederWerte
Holger Vogelsang
StreamsErzeugung
Weiteres Beispiel, Entfernung von Duplikaten, Sortierung der Zahlen in aufsteigender Reihenfolge und Beschränkung auf die ersten 10 Werte und Ausgabe:values.stream().distinct().sorted().limit(10).forEach(System.out::println);
Ablauf:
Weitere Möglichkeiten, Streams zu erzeugen: von primitiven Datentypen und Strings:
- Stream<String> str = Stream.of("Douglas", "Adams");- IntStream str = IntStream.of(1, 2, 3, 4, 5);- IntStream str = IntStream.range(0, 100); // Werte von 0 - 99
Informatik 2 - Datenstrukturen 62
values distinct() sorted() limit()
Alle Werteaus values
Alle Werteohne Duplicate
Alle Werte ohneDuplikate, sortiert
nur die ersten10 Werte
forEach
Ausgabeauf derKonsole
Holger Vogelsang
StreamsErzeugung
Erzeugung von Daten auf einem Stream- Erzeugt einen Stream mit einer (potentiell) endlosen Folge von Strings: Stream<String> str = Stream.generate(()->"Adams");
- Erzeugt einen Stream mit einer (potentiell) endlosen Folge von Zufallszahlen: Stream<Double> str = Stream.generate(() -> Math.random());
und noch viele weitere Möglichkeiten!
Informatik 2 - Datenstrukturen 63
Holger Vogelsang
StreamsFilterung und Reduktion
Filtern von Daten aus einem Stream: filter: Die Funktion ermittelt, ob der Wert behalten werden soll. map: Die Funktion bildet einen Wert auf einen anderen ab. Beispiel zur Umwandlung
eines Namens auf seinen Anfangsbuchstaben vor der Ausgabe:names.stream().map(n -> n.charAt(0)).forEach(System.out::println);
Reduktion des Streams auf ein Ergebnis: max: liefert den größten Wert eines Streams. Beispiel:
names.stream().max(String::compareTo); sum: liefert die Summe aller Werte. findFirst: liefert den ersten Wert des Streams. usw.
Informatik 2 - Datenstrukturen 64
Holger Vogelsang
StreamsOptionale Werte
Was passiert eigentlich beim Aufruf von findFirst oder max, wenn es keinen Wert im Stream gibt?
Diese Reduktion liefern ein Optional-Objekt zurück: Optional<String> first = names.stream().findFirst(); Die Methode isPresent dieses Objektes liefert true zurück, wenn es wirklich ein
Ergebnis gab, ansonsten false. Die Methode get() liefert das Ergebnisobjekt zurück. Verwendung:
if (first.isPresent()) System.out.println(first.get());
Warum so kompliziert? Optional kann auch innerhalb eines Stream verwendet werden,
um Werte zu erzeugen, wenn es keinen Wert gespeichert hat nicht Bestandteil der Vorlesung.
Informatik 2 - Datenstrukturen 65
Holger Vogelsang
StreamsSammlung der Ergebnisse, Streams mit primitiv
Sammlung der Ergebnisse von Stream-Operationen in einer Datenstruktur: List<String> result = stream.collect(Collectors.toList());
Es gibt viel mehr Möglichkeiten, Ergebnisse zu sammeln oder in Gruppen einzuteilen lassen wir lieber…
Gute Erklärungen auch unter java.util.stream in der API-Dokumentation.
Streams werden später in der Vorlesung beim Zugriff auf das Dateisystem wiederkommen!
Informatik 2 - Datenstrukturen 66
Holger Vogelsang
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
HashtabellenÜbersicht
Informatik 2 - Datenstrukturen 67
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 68
HashtabellenMotivation
Wie können Daten laufzeiteffizient verwaltet werden? Welche Bedingungen gelten dabei? Wie sieht der Speicherbedarf dazu aus? Idee: Daten werden in einem Array abgelegt und der Index im Array aus den Daten
berechnet.
Holger Vogelsang Informatik 2 - Datenstrukturen 69
HashtabellenIdee
Problem: Wie kann eine Menge von Werten M, die durch eine Schlüsselmenge K repräsentiert werden kann, effizient verwaltet werden? schnelles Einfügen schnelles Suchen schnelles Löschen
Gesucht ist eine Abbildung H von der Menge der Schlüssel K in den zur Verfügung stehenden Adressraum.
Bisherige Lösung: Listen-, Vektordarstellungen, Arrays,... Dabei wurde beim Suchen jeweils die Speicheradresse ermittelt. Jetzt: Neue Lösung, bei der die Werte in einem Vektor oder Array liegen und die Werte
mittels einer Schlüsseltransformation auf den Adressraum (den Vektor) abgebildet werden.
Holger Vogelsang Informatik 2 - Datenstrukturen 70
HashtabellenProblem der Schlüsselabbildung
Problem: Menge der möglichen Schlüsselwerte ist viel größer als die Menge der freien Speicheradressen. Beispiel: Die Elemente einer Menge werden mit Schlüsseln der Länge 10 Zeichen
beschrieben. Es sollen maximal 1000 Elemente und damit 1000 Adressen verwendet werden. Wie sollen 2610 mögliche Schlüssel auf 1000 Adressen verteilt werden?
Schlussfolgerung: Die Abbildungsfunktion H kann nicht eindeutig sein. Die Funktion H wird Hashfunktion genannt. Das Array, das die Werte aufnimmt, wird Hashtabelle genannt.
Holger Vogelsang Informatik 2 - Datenstrukturen 71
HashtabellenPerfekte Hashfunktion
Eine (perfekte) Hashfunktion kann über einen Schlüsselwert direkt die Position des Objekts im Feld berechnen.
Beispiel: Es existieren 26 Objekte, die Personen beschreiben:public class Person ....
Diese Personen werden durch Ihren Nachnamen als Schlüssel identifiziert. Zufällig sind die Namen über das Alphabet verteilt. Es gibt also zu jedem Großbuchstaben genau eine Person, deren Namen mit diesem Schlüssel anfängt. Damit ergibt sich eine perfekte Hashfunktion:Person[] hashtable = new Person[26];int hash(String key)
return key.charAt(0) – 'A';
Dann kann die Person zu einem Schlüssel einfach so gefunden werden:Person dozent = hashtable[ hash("Vogelsang") ];
Holger Vogelsang Informatik 2 - Datenstrukturen 72
HashtabellenPerfekte Hashfunktion
Dieser Fall ist ziemlich unwahrscheinlich. Zumeist werden mehrere Personen den gleichen Anfangsbuchstaben haben und sich dann
die Positionen im Feld teilen müssen. Man spricht dann auch von Kollision. Bis zu einem gewissen Grad kann man Kollisionen dadurch begegnen, dass man die
Hashtabelle größer macht und die Hashfunktion so erweitert, dass zum Beispiel der zweite Buchstabe berücksichtigt wird. Damit das Ergebnis der Berechnung wieder in die Tabelle passt, wird es später modulo der Tabellengröße gerechnet.final int SHIFT = 257;int hash(String key) return key.charAt(0) + key.charAt(1) * SHIFT;
Holger Vogelsang Informatik 2 - Datenstrukturen 73
HashtabellenStrategien zur Kollisionserkennung
Ab jetzt soll der Fall der nicht-perfekten Hashfunktion betrachtet werden. Frage: Wie soll verfahren werden, wenn beim Einfügen die Hashfunktion einen Index in der
Tabelle ermittelt, der bereits durch einen anderen Wert belegt ist?
Holger Vogelsang Informatik 2 - Datenstrukturen 74
HashtabellenHashtabellen mit Verkettung
Idee: Alle Objekte, die auf den selben Index abgebildet werden, werden am selben Index der Hashtabelle am Ende einer linearen Liste angehängt.
HashMapK, V: class
listK, V: class
listelementK, V: class
-data: pair<K, V>
first
last
0, 1
0, 10, 1
nextlists
*
0 1 2 3 4 5 6 7
Holger Vogelsang Informatik 2 - Datenstrukturen 75
HashtabellenHashtabellen mit Verkettung
Vorteil: Die Hashtabelle kann nicht überlaufen. Solange überhaupt noch Speicher vorhanden ist, lassen sich auch Elemente in der
Tabelle eintragen. Bezeichnung:
mit Verkettung: Beim Suchen müssen nur Objekte mit gleichem Schlüsselwert in einer verketteten Liste verglichen werden.
Problem: Der Zugriff wird mit zunehmender Anzahl der Kollisionen langsamer. Die Suche kann sogar zur linearen Suche entarten. Ist die zu erwartende Anzahl von
Objekten bekannt, kann auch die Lösung mit einer Liste gut sein. Eine mögliche Lösung:
Einsatz von Bäumen statt Listen.
Holger Vogelsang Informatik 2 - Datenstrukturen 76
HashtabellenHashtabellen mit Verkettung
Nachteile von Hashtabellen mit Verkettung: Es muss dynamisch Speicher belegt werden, was das Eintragen in die Hashtabelle zu
einer relativ aufwändigen Operation macht. Dynamische Container brauchen mehr Platz als ein statisches Feld mit gleich vielen
Elementen. Bei zunehmender Anzahl der Kollisionen ist Listensuche erforderlich.
Holger Vogelsang Informatik 2 - Datenstrukturen 77
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
Implementierung einer sehr einfachen und nicht optimalen Hashtabelle für Schlüssel und Werte eines beliebigen Typs mit Kollisionslisten (Projekt HashMap, Pair überschreibt equals für die Duplikatprüfung beim Einfügen):public class SimpleHashMap<K,V> implements Iterable<SimpleHashMap<K,V>.Pair>
// Paar für Schlüssel (K) und Wert (V), normalerweise impl. Interfaceclass Pair
private K key; // + Getterprivate V value; // + Getter und Setterpublic Pair(K key, V value)
this.key = key;this.value = value;
@SuppressWarnings("unchecked")@Overridepublic boolean equals(Object otherPair)
if (otherPair != null && otherPair.getClass() == getClass()) return ((Pair) otherPair).key.equals(key);
return false;
Holger Vogelsang Informatik 2 - Datenstrukturen 78
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
// Vektor mit den Listen, die ihrerseits die Paare aufnehmenprivate ArrayList<LinkedList<Pair>> entries;
// Größe des Vektors übergebenpublic SimpleHashMap(int size)
entries = new ArrayList<>();// Im Vektor alle Listen anlegenfor (int i = 0; i < size; ++i) entries.add(new LinkedList<Pair>());
// Schlüssel "key" und Wert "value" in der Hash-Tabelle ablegenpublic void put(K key, V value)
int index = indexFor(key.hashCode());Pair pair = new Pair(key, value);// Eventuell vorhandenes Paar mit id. Schlüssel löschenLinkedList<Pair> list = entries.get(index);list.remove(pair);list.add(pair);
Holger Vogelsang Informatik 2 - Datenstrukturen 79
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
// Wert zu einem Schlüssel auslesenpublic V get(K key)
int index = indexFor(key.hashCode());// Die Listen sequentiell durchsuchenfor (Pair pair: entries.get(index)) if (pair.key.equals(key))
return pair.value;
return null;
Holger Vogelsang Informatik 2 - Datenstrukturen 80
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
/*** Berechnet den Index aus einem Hashwert. Die Modulo-Berechnung* <code>abs(hashCode % laenge)</code> ist nicht ausreichend, da* der <code>hashCode</code> den Wert <code>Integer.MIN_VALUE</code>* besitzen kann. Der Absolutwert von <code>Integer.MIN_VALUE</code>* ist wiederum <code>Integer.MIN_VALUE</code>, also negativ!* @param hashCode Berechneter Hashwert.* @return Index innerhalb der Tabelle.*/
private int indexFor(int hashCode) int absHashCode = abs(hashCode);if (absHashCode < 0)
absHashCode = 0;return absHashCode % entries.size();
Holger Vogelsang Informatik 2 - Datenstrukturen 81
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
// Die Hash-Tabelle benötigt einen Iterator. Der wird// hier etwas anders als in der HashMap des JDK implementiert.
// Innere Klasse von SimpleHashMapclass HashMapIterator implements Iterator<Pair>
private int index;private Iterator<Pair> listIterator;
public HashMapIterator() // Erste nicht-leere Liste findenfor (LinkedList<Pair> list: entries)
if (list.size() > 0) listIterator = list.iterator();break;
++index;
Holger Vogelsang Informatik 2 - Datenstrukturen 82
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
@Overridepublic boolean hasNext()
// Gibt es überhaupt ein Element?if (index >= 0 && index < entries.size() && listIterator != null)
// Hat die aktuelle Liste ein weiteres Element?if (listIterator.hasNext()) return true;
// Nächste Liste mit Eintrag suchenint nextIndex = index;while (++nextIndex < entries.size()) // Hat sie einen Eintrag?if (entries.get(nextIndex).size() > 0)
return true;
return false;
Holger Vogelsang Informatik 2 - Datenstrukturen 83
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
@Overridepublic Pair next() // Gibt es überhaupt ein Element?if (index >= 0 && index < entries.size() && listIterator != null)
// Hat die aktuelle Liste ein weiteres Element?if (listIterator.hasNext()) return listIterator.next();
// Nächste Liste mit Eintrag suchenwhile (++index < entries.size()) // Hat sie einen Eintrag?if (entries.get(index).size() > 0)
listIterator = entries.get(index).iterator();return listIterator.next();
throw new NoSuchElementException();
Holger Vogelsang Informatik 2 - Datenstrukturen 84
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
// Ein Löschen des aktuellen Elementes ist hier nicht implementiert// --> ist etwas länglich.@Overridepublic void remove() throw new UnsupportedOperationException();
// Methode, um den Iterator der Hash-Tabelle auszulesen. Auch dieses// ist hier anders als in der HashMap des JDK umgesetzt.@Overridepublic Iterator<Pair> iterator()
return new HashMapIterator();
Holger Vogelsang Informatik 2 - Datenstrukturen 85
HashtabellenHashtabellen mit Verkettung: Eine einfache Implementierung
public class SimpleHashMapTest
public static void main(String[] args) SimpleHashMap<String, Integer> simpleHashMap = new SimpleHashMap<>(31);simpleHashMap.put("Answer", 42);simpleHashMap.put("What?", 66);
for (Iterator<SimpleHashMap<String, Integer>.Pair> iter = simpleHashMap.iterator(); iter.hasNext();)
SimpleHashMap<String, Integer>.Pair pair = iter.next();System.out.println(pair.getKey() + ": " + pair.getValue());
for (SimpleHashMap<String, Integer>.Pair pair: simpleHashMap) System.out.println(pair.getKey() + ": " + pair.getValue());
Holger Vogelsang Informatik 2 - Datenstrukturen 86
HashtabellenHashtabellen mit Verkettung: Aufwandsabschätzung
Annahmen: Die Auslastung der Tabelle ist α = N / M. N = Anzahl der Schlüssel, M = Anzahl der
Speicherplätze in der Tabelle. Der Schlüsselbereich S ist uniform, d.h., die Schlüssel werden gleichmäßig auf die Tabelle
verteilt. Die Berechnung der Hashfunktion hat Aufwand O(1).
Operation Aufwand
Einfügen (inkl. Duplikatsuche) O(N), im Mittel θ(α+1)
Löschen O(N), im Mittel θ(α+1)
Suche, erfolgreich O(N), im Mittel θ(α+1)
Suche, erfolglos O(N), im Mittel θ(α+1)
Holger Vogelsang Informatik 2 - Datenstrukturen 87
HashtabellenOffene Hashtabellen/Geschlossene Hashtabellen
Ein anderer Ansatz zur Kollisionsbehandlung sind offene Hashtabellen (manchmal auch geschlossene Hashtabellen): offen: offene Adressierung im Array geschlossen: Begrenzung der maximalen Schlüssel im Array
Ansatz: Verzicht auf dynamische Verknüpfungen wie Listen etc. Statt dessen: Ist beim Einfügen der gesuchte Index belegt, so wird ein freier Nachbarindex
gesucht und der Wert dort eingetragen. Zu Bestimmung eines Nachbarindexes existieren verschiedene Ansätze. Die Suche erfolgt analog:
Zunächst wird durch den Schlüssel ein Index ermittelt. Steht dort nicht der gesuchte Wert, so werden die Nachbarindizes durchsucht.
0 1 2 3 4 5 6 7
Holger Vogelsang Informatik 2 - Datenstrukturen 88
HashtabellenOffene Hashtabellen: Einfügen
// Fiktive Beispielimplementierung einer Hash-Map ohne Duplikatsprüfungpublic class SimpleHashMap<K,V>
// Schlüssel- und Wertepaarclass Pair
public K key;public V value;public Pair(K key, V value)
this.key = key;this.value = value;
@SuppressWarnings("unchecked")@Overridepublic boolean equals(Object otherPair)
if (otherPair != null && otherPair.getClass() == getClass()) return ((Pair) otherPair).key.equals(key);
return false;
Holger Vogelsang Informatik 2 - Datenstrukturen 89
HashtabellenOffene Hashtabellen: Einfügen
// ArrayList mit den Paarenprivate ArrayList<Pair> entries;
// Hash-Map in einer vorgegebenen Größe erzeugenpublic SimpleHashMap(int size)
entries = new ArrayList<Pair>(size);for (int i = 0; i < size; ++i)
entries.add(null); // jeder Eintrag ist leer
// Schon bekannt aus dem vorherigen Beispielprivate int indexFor(int hashCode)
int absHashCode = abs(hashCode);if (absHashCode < 0)
absHashCode = 0;return absHashCode % entries.size();
Holger Vogelsang Informatik 2 - Datenstrukturen 90
HashtabellenOffene Hashtabellen: Einfügen
// Einfügen ohne Prüfung auf Duplikate (nicht sehr praxisnah).public void put(K key, V value)
int startIndex = indexFor(key.hashCode());int count = 0;int currentIndex = startIndex;boolean finished = false;
do if (entries.get(currentIndex) == null)
// freien Platz gefunden, Paar erzeugen und eintragenentries.set(currentIndex, new Pair(key, value));finished = true;
else
// berechne nächsten Indexcount++;currentIndex = (startIndex + nextStep(count)) % entries.size();
while (!finished && (count < entries.size()));
Holger Vogelsang Informatik 2 - Datenstrukturen 91
HashtabellenOffene Hashtabellen: Einfügen
// Suche nach einem Wert anhand seines Schlüsselspublic V get(K key)
int startIndex = indexFor(key.hashCode());int count = 0;int currentIndex = startIndex;
// Solange suchen, bis ein leerer Eintrag gefunden wurdedo
if (entries.get(currentIndex) == null) return null;
else // gefunden!
if (entries.get(currentIndex).key.equals(key)) return entries.get(currentIndex).value;
// Berechne nächsten Indexcount++;currentIndex = (startIndex + nextStep(count)) % entries.size();
while (count < entries.size());return null;
Holger Vogelsang Informatik 2 - Datenstrukturen 92
HashtabellenOffene Hashtabellen: Lineares Sondieren
Die Methode int nextStep(int attempt) ermittelt den nächsten zu testenden Eintrag. Im einfachsten Fall ist nextStep:
private int nextStep(int attempt) return attempt;
In diesem Fall nennt man die Vorgehensweise auch lineares Sondieren, und für die Testindizes gilt:h0 = hash(key);hi = (h0 + i);
Nachteil: Die Schlüssel ballen sich um primäre Schlüssel (Schlüssel, die beim Einfügen nicht kollidieren).
Ziel: nextStep sollte so gewählt werden, dass die Schlüssel wiederum gleichmäßig auf die freien Plätze verteilt werden.
Holger Vogelsang Informatik 2 - Datenstrukturen 93
HashtabellenOffene Hashtabellen: Quadratisches Sondieren
Die Methode nextStep ermittelt den nächsten Eintrag durch eine quadratische Funktion.h0 = hash(key);hi = (h0 + i2);
Vorteil: Die Verteilung ist einfach zu berechnen und verhindert im Wesentlichen primäre Ballungen.
Nachteil: Es werden nicht alle Indizes der Hashtabelle berücksichtigt, damit wird u.U. ein freier Eintrag nicht gefunden.
Es wird aber mindestens die halbe Tabelle durchsucht, wenn deren Größe eine Primzahl ist. Der Nachteil trägt nur dann, wenn die Tabelle relativ voll ist. In der Praxis sollte man eine Auslastung von max. 50% vorsehen.
Holger Vogelsang Informatik 2 - Datenstrukturen 94
HashtabellenOffene Hashtabellen: Doppelte Hashfunktion
Die Methode nextStep ermittelt den nächsten Eintrag durch einen Aufruf einer anderen Hashfunktion g.h0 = hash(key);hi = (h0 + i * g(key));
Doppelte Hashfunktionen zeigen das beste Verhalten, wenn die beiden Hashfunktionen hinreichend unabhängig voneinander sind.
Die Wahrscheinlichkeit, dass beide Hashfunktionen den gleichen Wert liefern, sollte also gering sein.
Holger Vogelsang Informatik 2 - Datenstrukturen 95
HashtabellenOffene Hashtabellen: Pseudozufallszahlen
Nach der Initialisierung durch den Konstruktor liefern sukzessive Aufrufe von nextStep der Reihe nach die Pseudozufallszahlen.
Die Überlaufstrategie mit einem Pseudozufallszahlengenerator leidet auch unter sekundärer Clusterbildung, es sei denn, der Startwert wird vom Schlüssel abhängig gemacht.
Holger Vogelsang Informatik 2 - Datenstrukturen 96
HashtabellenDynamische Hashtabellen
Dynamische Hashtabellen sind in der Lage, sich bei Bedarf automatisch zu vergrößern oder zu verkleinern, ohne dass ein komplettes Neuberechnen der Hashwerte erforderlich ist.
soll hier nicht betrachtet werden (zu kompliziert…)
Holger Vogelsang Informatik 2 - Datenstrukturen 97
HashtabellenVergleich der Verfahren – einige Zahlen
Vorteile der Hashtabelle mit Verkettung: Sie erlaubt Auslastungen α > 100%. Sie unterstützt sehr einfach das Löschen. Ein gegebener Schlüssel wird immer abgespeichert.
Vorteile der offenen Hashtabellen: Die Zugriffsoperationen sind wesentlich effizienter. Die Algorithmen sind einfacher zu implementieren.
Konkrete Werte der durchschnittlichen Anzahl von Einfüge-Versuchen für Füllgrade zwischen 60% und 95% (ohne Test auf Duplikate):
Name Anzahl Versuche bei Füllgrad α
60% 70% 80% 90% 95%
Kollisionsliste 1,00 1,00 1,00 1,00 1,00
Lineares Sondieren 1,75 2,17 3,00 5,50 10,50
Pseudozufallszahlen 2,29 4,01 8,05 23,02 59,91
Holger Vogelsang Informatik 2 - Datenstrukturen 98
HashtabellenVergleich der Verfahren – einige Zahlen
Verlauf beim Einfügen
0
10
20
30
40
50
60
70
60% 70% 80% 90% 95%
mit Verkettung
offen, lineares Sondieren
offen, Pseudozufallszahlen
Holger Vogelsang Informatik 2 - Datenstrukturen 99
HashtabellenImplementierungen in Java
Es gibt noch weitere Klassen (siehe Folgeseiten)
Holger Vogelsang
HashtabellenImplementierungen in Java
Hashtabellenimplementierungen in Java: HashMap<K,V>:
- Ablage von Schlüssel-/Wertepaaren- Schlüsselduplikate sind nicht erlaubt.- Mehrere Iterierungsmöglichkeiten kommen gleich
Hashtable<K,V>:- Ablage von Schlüssel- Wertepaaren- Schlüsselduplikate sind nicht erlaubt.- im Gegensatz zu HashMap thread-sicher- Iterieren wie bei HashMap
HashSet<E>:- Ablage von Schlüsseln- Duplikate sind nicht erlaubt.- Iteratorzugriff mit der Methode public Iterator<E> iterator()
Informatik 2 - Datenstrukturen 100
Holger Vogelsang
HashtabellenImplementierungen in Java
LinkedHashMap<K,V>:- Ablage von Schlüssel- Wertepaaren- Schlüsselduplikate sind nicht erlaubt.- Alle Paare sind untereinander durch eine doppelt-verkettete Liste verbunden.
Entweder:• in Einfügereihenfolge, um diese zu erhalten• oder in jeweils aktualisierter Zugriffsreihenfolge beim Lesen, damit die
Elemente mit den häufigsten Zugriffen vorne in der Liste stehen Cache!- Iterieren wie bei HashMap
LinkedHashSet<E>:- siehe LinkedHashMap und HashSet (nur Schlüssel, verbunden über eine Liste)
Informatik 2 - Datenstrukturen 101
Holger Vogelsang
HashtabellenImplementierungen in Java
Beispiel zum Einsatz einer Hash-Tabelle in einer Server-Anwendung: Wenn der Browser mit GZIP komprimierte Dateien verarbeiten kann und wenn der Dateityp nicht ohnehin schon komprimierte Daten enthält dann komprimiere die Daten vor dem Versand mit GZIP.
Die Hash-Tabelle enthält die Dateiendungen der nicht zu komprimierenden Dateien. Ausschnitt:
private HashSet<String> compressedFileTypes = new HashSet<String>();//public void doFilter(...) if (!isGzipSupportedByBrowser(request) ||
compressedFileTypes.contains(fileType)) chain.doFilter(request, response);return;
// vor dem Versand komprimierenGzipResponse gzipRespone = new GzipResponse(response);chain.doFilter(request, gzipRespone);gzipResponse.close();
Informatik 2 - Datenstrukturen 102
Holger Vogelsang
HashtabellenImplementierungen in Java
Maps und Zugriff auf Iteratoren
Informatik 2 - Datenstrukturen 103
Holger Vogelsang
HashtabellenImplementierungen in Java
Es existieren drei Varianten zum Iterieren: Set<K> keySet(): Liefert die Menge aller Schlüssel, über die iteriert werden kann. Die
Werte sind nicht direkt zugreifbar. Collection<V> values(): Liefert alle Schlüssel, über die iteriert werden kann. Deren
Zuordnung zu den Schlüsseln ist nicht mehr erkennbar. Set<Map.Entry<K,V>> entrySet(): Liefert die Menge aller Schlüssel-/Werte-Paare,
über die iteriert werden kann. Beispiel mit direkter Iterator-Verwendung:
HashMap<String, Integer> map = new HashMap<>();// füllenfor (Iterator<Map.Entry<String, Integer>> entryIter = map.entrySet().iterator();
entryIter.hasNext(); ) Map.Entry<String, Integer> entry = entryIter.next();String key = entry.getKey();Integer value = entry.getValue();// …
Informatik 2 - Datenstrukturen 104
Holger Vogelsang
HashtabellenImplementierungen in Java
Es existieren dementsprechend auch drei Varianten, um einen Stream zu erhalten: Stream<K> keySet().stream(): Liefert einen Stream, der alle Schlüssel beinhaltet. Stream<V> values().stream(): Liefert einen Stream, der alle Werte beinhaltet. Stream<Map.Entry<K,V>> entrySet().stream(): Liefert Stream, der die Menge
aller Schlüssel-/Werte-Paare beinhaltet. Beispiel:
HashMap<String, Integer> map = new HashMap<>();// füllenStream<String> keyStream = map.keySet().stream();
Stream<Integer> valueStream = map.values().stream();
Stream<Map.Entry<String, Integer>> keyValueStream = map.entrySet().stream();
Informatik 2 - Datenstrukturen 105
Holger Vogelsang 106
HashtabellenWeiterer Einsatz von Hashfunktionen
Wozu kann eine Hashfunktion noch dienen? Berechnung von Prüfsummen, um zu testen, ob eine Nachricht oder Datei verfälscht
wurde. Beispiel: siehe http://tomcat.apache.org/download-80.cgi
Informatik 2 - Datenstrukturen
Datei Hashwert
Holger Vogelsang Informatik 2 - Datenstrukturen 107
HashtabellenWeiterer Einsatz von Hashfunktionen
SHA1 ist eine 64-Bit Prüfsumme (hier über den Inhalt der Datei):
Algorithmus: siehe https://de.wikipedia.org/wiki/Secure_Hash_Algorithm
Holger Vogelsang Informatik 2 - Datenstrukturen 108
HashtabellenWahl einer Hashfunktion
Ziel: Gleichmäßige Verteilung der Werte in der Tabelle. Beispiel für eine schlechte Hashfunktion:
Studenten-Objekte sollen in einer Hashtabelle gespeichert werden. Jeder Student hat eine 6-stellige Matrikelnummer, die fortlaufend vergeben wird. Größe der Hashtabelle: 10001. Hashfunktion 1:
- Die ersten vier Stellen der Matrikelnummer bilden den Hash-Wert.- Problem: Alle Datensätze eines Jahrganges werden auf sehr wenige Positionen
abgebildet. Hashfunktion 2:
- Die letzten vier Stellen der Matrikelnummer bilden den Hash-Wert.- Besser: Die Datensätze verteilen sich gleichmäßiger auf die Tabelle.
Holger Vogelsang Informatik 2 - Datenstrukturen 109
HashtabellenWahl einer Hashfunktion
Einige Hinweise zur Wahl der Hashfunktion: Integer-Zahlen i: die Zahl i selbst oder i mod 2n (n ist eine große Primzahl) Fließkommazahlen: Addition oder andere Verknüpfung von Mantisse und Exponent Strings: Addition der ASCII/Unicode-Werte einiger/aller Zeichen, eventuell mit einem
Faktor gewichtet Komplexere Objekte: Reduktion auf primitive Datentypen, die Attribute des Objektes
sind. Beispiel:public class Rectangle
private int x;private int y;private int w;private int h;
Hashwert aus Verknüpfung derKoordinaten + Größe
Holger Vogelsang Informatik 2 - Datenstrukturen 110
HashtabellenWahl einer Hashfunktion: Beispiele von Java
Die Ermittlung einer guten Hashfunktion wird hier nicht besprochen. Hashfunktionen in Java (Ergebnis ist immer int):
für einen String s der Länge n:- s[0]*31(n-1) + s[1]*31(n-2) + ... + s[n-1] - 0 für leere Strings
für Byte-, Short- und Integer-Zahlen:- Die Zahl ist der Hashwert.
für Long-Zahlen:- Exklusiv-Oder-Verknüpfung der unteren und oberen 32 Bit- Rückgabe der unteren 32 Bit
für Double-Zahlen:- Umwandlung der Bit-Repräsentation der Zahl in long- Exklusiv-Oder-Verknüpfung der unteren und oberen 32 Bit (um Mantisse und
Exponent zu berücksichtigen)- Rückgabe der unteren 32 Bit
Holger Vogelsang Informatik 2 - Datenstrukturen 111
HashtabellenWahl einer Hashfunktion: Beispiele von Java
für Boole‘sche Werte:- true: 1231- false: 1237
für einen Vector bzw. eine List der Länge n:- v[0].hashCode()*31(n-1) + v[1].hashCode()*31(n-2) + ... +
v[n-1] .hashCode()- 0 für leere Vektoren
Wichtig in Java: Objekte liefern durch Überschreiben der Methode int hashCode() ihren eigenen
Hashwert zurück. Der Wert darf sich bei mehreren Aufrufen der Methode nicht ändern, solange sich das
Objekt nicht ändert. Wenn zwei Objekte beim Vergleich mit der equals-Methode gleich sind, so müssen
auch ihre Hashwerte identisch sein.
Holger Vogelsang Informatik 2 - Datenstrukturen 112
HashtabellenWahl einer Hashfunktion: Beispiele von Java
Beispiel für Klasse java.awt.geom.Rectangle2D (stark vereinfacht!):public abstract class Rectangle2D private double x;private double y;private double w;private double h;
@Overridepublic int hashCode()
long bits = Double.doubleToLongBits(x);bits += Double.doubleToLongBits(y) * 37;bits += Double.doubleToLongBits(w) * 43;bits += Double.doubleToLongBits(h) * 47;return (((int) bits) ^ ((int) (bits >> 32)));
// Die equals-Methode liefert dann true, wenn// alle x, y, w, h bei beiden Objekten gleich sind.
Holger Vogelsang
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
BäumeÜbersicht
Informatik 2 - Datenstrukturen 113
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 114
BäumeMotivation
Was sind Bäume? Wozu dienen Bäume? Wie sind die Daten in einem Baum sortiert? Wie kann ein Baum effizient implementiert werden? Verschiedene Baumarten für unterschiedliche Einsatzgebiete
Holger Vogelsang Informatik 2 - Datenstrukturen 115
BäumeÜbersicht
Beispiel: Teilebaum eines „Autos“ (der Fahrer ist eher kein Teil des Autos…)
Es ergibt sich ein Aufbau der Teile wie bei einem Stammbaum. Jeder Strich von oben nach unten bedeutet dabei, dass sich das Ausgangsobjekt aus den
tiefer liegenden Objekten zusammensetzt. Zusammengesetzte Objekte können durch einen solchen Baum eindeutig beschrieben
werden.
Holger Vogelsang
BäumeÜbersicht
Stammbaum wichtiger Programmiersprachen (bis 2003)
[P. Henning, H. Vogelsang (Hrsg.), „Handbuch Programmiersprachen“]
Informatik 2 - Datenstrukturen 116
Holger Vogelsang
BäumeÜbersicht
Darstellung von (X)HTML-Seiten im Browser
Informatik 2 - Datenstrukturen 117
wird im Browser intern durcheinen Baum (DOM) repräsentiert
Holger Vogelsang
BäumeÜbersicht
Quelltext-Verwaltung in Eclipse
Informatik 2 - Datenstrukturen 118
Quelltext wirdintern als Baumdargestellt
Holger Vogelsang
BäumeÜbersicht
Dokumentenstruktur
Informatik 2 - Datenstrukturen 119
Holger Vogelsang
BäumeÜbersicht
Scene Graph von JavaFX:
Informatik 2 - Datenstrukturen 120
Scene
FlowPane
Button ButtonButton Group
Ellipse Rectangle
Holger Vogelsang
BäumeÜbersicht
Entscheidungsbäume:
Informatik 2 - Datenstrukturen 121
Person
< 20 >= 20Temperatur
Regenwahr-scheinlichkeit
< 50% >= 50%
Norddeutscher?
< 30% >= 30%
neinja neinja neinja
im Meerbaden?
Holger Vogelsang Informatik 2 - Datenstrukturen 122
BäumeBegriffe
Nicht nur für zusammengesetzte Objekte können Bäume verwendet werden. In der Informatik werden Bäume häufig verwendet, um effizient Objekte einzufügen, zu suchen und zu löschen. Begriffsübersicht
42
27 68
6 39 51 75
12 34 41 64 72 Blätter (keineNachfolger)
Knoten
Wurzel
linkerTeilbaum
rechterTeilbaum
rechter Sohn(der Wurzel)
linker Sohn(der Wurzel)
Kante
Holger Vogelsang Informatik 2 - Datenstrukturen 123
BäumeBinärer Suchbaum
In dieser Vorlesung werden Bäume mit den folgenden Eigenschaften behandelt: Die Knoten enthalten Werte, die sich vergleichen lassen. In der Praxis wird man für die
Schlüssel die equals-Methode überschreiben und Comparable implementieren bzw. einen Comparator übergeben.
Für jeden Knoten gilt, dass er einen eindeutigen rechten Sohn und einen eindeutigen linken Sohn hat (sofern es diesen jeweils gibt).
Der linke Sohn (sofern es ihn gibt) hat immer einen niedrigeren Wert als der rechte Sohn (sofern es ihn gibt).
Der linke Sohn (sofern es ihn gibt) eines Knotens hat immer einen kleineren Wert als der Knoten.
Der rechte Sohn (sofern es ihn gibt) eines Knotens hat immer einen größeren Wert als der Knoten.
Holger Vogelsang Informatik 2 - Datenstrukturen 124
BäumeBinärer Suchbaum – eine einfache Implementierung
Beispielklasse für einen Baum mit Schlüsseln und Werten (siehe Projekt TreeMap):public class SimpleTreeMap<K extends Comparable<K>,V>
// Gleiche Paar-Klasse wie in der SimpleHashMapclass Pair
public K key;public V value;public Pair(K key, V value) /* ... */
// Knoten des Binärbaumesclass Node
private Pair data;private Node left;private Node right;
public Node(Pair data, Node left, Node right) /* ... */
// Getter und Setter// Wurzel des Baumsprivate Node root;
Holger Vogelsang Informatik 2 - Datenstrukturen 125
BäumeBinärer Suchbaum – Komplettes Durchlaufen
Es gibt mehrere Arten, einen Baum zu durchlaufen: Preorder: Zuerst wird der Knoten selbst ausgegeben, dann seine Söhne. Inorder: Zuerst werden der linke Sohn, dann der Knoten selbst, dann der rechte Sohn
ausgegeben. Postorder: Zuerst werden die Söhne des Knotens ausgegeben, dann der Knoten selbst.
Holger Vogelsang Informatik 2 - Datenstrukturen 126
BäumeBinärer Suchbaum – Traversierung
Preorder:public void dump(Node node)
if (node != null) System.out.println(node.data.key);dump(node.left);dump(node.right);
Inorder:public void dump(Node node)
if (node != null) dump(node.left);System.out.println(node.data.key);dump(node.right);
Postorder: Analog
Holger Vogelsang Informatik 2 - Datenstrukturen 127
BäumeBinärer Suchbaum – Traversierung
Preorder, nicht-rekursiv:void dump(Node node) stack.offer(node);while (stack.size() > 0)
node = stack.pollLast();System.out.println(node.data.key);if (node.right != null) stack.offer(node.right);
if (node.left != null)
stack.offer(node.left);
Holger Vogelsang Informatik 2 - Datenstrukturen 128
BäumeBinärer Suchbaum – Traversierung und Ausgabe
Levelorder (Queue anstatt Stack):void dump(Node node) queue.offer(node);while (queue.size() > 0)
node = queue.poll();System.out.println(node.data.key);if (node.left != null)
queue.offer(node.left);if (node.right != null) queue.offer(node.right);
Holger Vogelsang Informatik 2 - Datenstrukturen 129
BäumeBinärer Suchbaum – Suche anhand eines Beispiels
Suche nach dem Schlüssel 34: Enthält der aktuelle Knoten den gesuchten Schlüssel: fertig. Ist der gesuchte Schlüssel kleiner als der Schlüssel im Knoten: linker Sohn Ist der gesuchte Schlüssel größer als der Schlüssel im Knoten: rechter Sohn
42
27 68
6 39 51 75
12 34 41 64 72
34
Holger Vogelsang Informatik 2 - Datenstrukturen 130
BäumeBinärer Suchbaum – Implementierung der Suche
Suchmethode:public V get(K key)
// Start am WurzelknotenNode searchNode = root;
// Solange es noch Knoten gibt und der aktuelle Knoten nicht// den gesuchten Schlüssel enthält, suche weiter.while ((searchNode != null) &&
(!searchNode.data.key.equals(key))) // Wenn der gesuchte Schlüssel größer als der Schlüssel des// Knotens ist, nimm den rechten Zweig, ansonsten den linken.searchNode = (key.compareTo(searchNode.data.key) > 0) ?
searchNode.right:searchNode.left;
return searchNode != null ? searchNode.data.value : null;
Holger Vogelsang Informatik 2 - Datenstrukturen 131
BäumeBinärer Suchbaum – Algorithmus zum Einfügen
Vorgehensweise beim Einfügen: Zunächst wird die Stelle gesucht, an der sich der Schlüssel im Baum befinden sollte. Ist der Schlüssel schon vorhanden, so wird einfach die Adresse dieses Schlüssels
zurückgegeben. Ist er nicht vorhanden, so wird ein neuer Knoten erzeugt und dort eingehängt.
Holger Vogelsang Informatik 2 - Datenstrukturen 132
BäumeBinärer Suchbaum – Einfügen anhand eines Beispiels
Beispiel: Einfügen des Schlüssels 36
42
27 68
6 39 51 75
12 34 41 64 72
36
36
Holger Vogelsang Informatik 2 - Datenstrukturen 133
BäumeBinärer Suchbaum – Algorithmus zum Löschen
Die komplizierteste Funktion ist das Löschen aus einem binären Teilbaum. Dazu müssen drei Fälle unterschieden werden:
1. Der zu löschende Knoten hat gar keinen Sohn. Damit kann er direkt gelöscht werden.2. Der zu löschende Knoten hat genau einen Sohn. Dann wird der Sohn in den aktuellen
Knoten „kopiert“ und der Sohn gelöscht.3. Der zu löschende Knoten hat zwei Söhne. Dann wird im linken Teilbaum der Sohn mit
dem größten Schlüssel gesucht und als neuer zentraler Knoten eingefügt (oder im rechten Teilbaum der Knoten mit dem kleinsten Schlüssel).
Holger Vogelsang Informatik 2 - Datenstrukturen 134
BäumeBinärer Suchbaum – Löschen anhand eines Beispiels
Beispiel: Löschen des Schlüssels 36 (Fall 1, der Knoten hat keinen Nachfolger)
42
27 68
6 39 51 75
12 34 41 64 72
36
kann direkt gelöscht werden
Holger Vogelsang Informatik 2 - Datenstrukturen 135
BäumeBinärer Suchbaum – Löschen anhand eines Beispiels
Beispiel: Löschen des Schlüssels 34 (Fall 2, der Knoten hat einen direkten Nachfolger)
42
27 68
6 39 51 75
12 34 41 64 72
36
36 ersetzt 34, die alte 36 wird gelöscht
36
Holger Vogelsang Informatik 2 - Datenstrukturen 136
BäumeBinärer Suchbaum – Löschen anhand eines Beispiels
Beispiel: Löschen des Schlüssels 42 (Fall 3, der Knoten wird durch den Knoten mit dem größten Schlüssel des linken oder dem kleinste des rechten Teilbaums ersetzt der hat immer nur einen direkten Nachfolger)
42
27 68
6 39 51 75
12 34 41 64 72
36
41 ersetzt 42, die alte 41 wird gelöscht
41
Holger Vogelsang Informatik 2 - Datenstrukturen 137
BäumeBinärer Suchbaum – Beispielanwendung
public class SimpleTreeMapTest public static void main(String[] args)
SimpleTreeMap<String, Integer> simpleTreeMap = new SimpleTreeMap<>();simpleTreeMap.add("Question", 66);simpleTreeMap.add("Answer", 42);System.out.println(simpleTreeMap.get("Question"));System.out.println(simpleTreeMap.get("Answer??"));
Holger Vogelsang Informatik 2 - Datenstrukturen 138
BäumeBinärer Suchbaum – Aufwandsabschätzung
Annahme: Der Baum ist nicht balanciert.
Operation Aufwand
Einfügen, sortierte Reihenfolge O(N)
Einfügen, zufällige Reihenfolge O(N), im Mittel θ(ln N)
Löschen O(N), falls degeneriert
Indexzugriff O(N)
Suche, degeneriert O(N)
Suche, optimal eingefügt O(ln N)
Holger Vogelsang Informatik 2 - Datenstrukturen 139
BäumeBeispiel zum binären Suchbaum
Darstellung eines arithmetischen Ausdrucks als Baum:f = (a - b) * c - (d / b + sin(e))
Tipp: Klammerungen werden durch die Höhen der Operatorknoten untereinander wiedergegeben.
Holger Vogelsang Informatik 2 - Datenstrukturen 140
BäumeBalancierter Baum (AVL) – Idee
Ein Baum heißt vollständig, wenn jeder Knoten entweder zwei Söhne hat oder gar keine. Bei einem solchen Baum wächst die Höhe des Baumes, also der längste Weg beim Suchen,
logarithmisch mit der Anzahl der Objekte. Die Komplexität des Suchens wächst logarithmisch mit der Anzahl der Elemente. Gegenteil: Auch die lineare, geordnete Liste ist ein Suchbaum, wenn auch ein vollständig
entarteter. Die Komplexität des Suchens in einem derart degenerierten Baum wächst linear mit der Anzahl der Schlüssel.
Zu den gleichen Schlüssel kann man unterschiedliche binäre Suchbäume konstruieren.
Holger Vogelsang Informatik 2 - Datenstrukturen 141
BäumeBalancierter Baum (AVL) – Idee
Beispiel, in dem der Baumaufbau von der Reihenfolge des Einfügens der Schlüssel abhängt.
45
41 68
34 42 51
6439
68
64
51
45
42
41
39
34
Holger Vogelsang Informatik 2 - Datenstrukturen 142
BäumeBalancierter Baum (AVL) – Idee
Ein Baum kann also zur Liste degenerieren. Problem: In der Praxis sind Suchbäume praktisch nie vollständig ausgeglichen, denn das
würde einen sehr großen Aufwand bedeuten. Lösung: Näherungsweises Ausgleichen eines Baums (Begriff: ausgeglichener Baum). Die erste Klasse von ausgeglichenen Bäumen waren die AVL-Bäume (nach den Erfindern G.
M. Adelson-Velski/E. M. Landis). Ziel: Je zwei Teilbäume an einem Knoten dürfen sich in der Höhe um nicht mehr als 1
unterscheiden. Dieses gilt für alle Teilbäume an allen Knoten. Ein Baum ist genau dann ausgeglichen, wenn dieses Ziel erreicht ist.
Holger Vogelsang Informatik 2 - Datenstrukturen 143
Nach jeder Einfüge- oder Löschoperation muss überprüft werden, ob ein Ausgleichen des Baums erforderlich ist
Das Ausgleichen erfolgt durch „Rotation“ der Knoten. Beispiel: Linksrotation um die Knoten B/D.
Eine Linksrotation reduziert die Höhe des rechten Teilbaums um 1 und erhöht die Höhe des linken um 1.
BäumeBalancierter Baum (AVL) – Ausgleichen
B
D
Rotationspunkt
ec
a
D
B
e
ca
Holger Vogelsang Informatik 2 - Datenstrukturen 144
ec
BäumeBalancierter Baum (AVL) – Ausgleichen durch Doppelrotation
Um die Höhe eines inneren Baums zu verändern, muss eine Doppelrotation LR oder RL angewendet werden.
Beispiel: Doppelrotation
B
F
aD
g ec
D
F
a
B
g
Holger Vogelsang Informatik 2 - Datenstrukturen 145
BäumeBalancierter Baum (AVL) – Algorithmus zum Ausgleichen
Gegeben sei ein Baum mit einer Wurzel W sowie deren linken Teilbaum L und rechten Teilbaum R.
Der neue Knoten soll in L eingefügt werden (wie bisher auch). Höhe(L) = Höhe(R): Nach dem Einfügen unterscheiden sich die Höhen um 1 ->
Ausgeglichenheit nicht verletzt. Höhe(L) < Höhe(R): Die Höhen werden gleich. Die Ausgeglichenheit ist nicht verletzt. Höhe(L) > Höhe(R): Die Ausgeglichenheit wird zerstört. Der Baum muss restrukturiert
werden. Lösung: Jeder Knoten enthält zusätzlich Balance-Informationen.
Höhe(L) = Höhe(R): balance = 0 Höhe(L) < Höhe(R): balance = 1; Höhe(L) > Höhe(R): balance = -1;
Holger Vogelsang Informatik 2 - Datenstrukturen 146
BäumeBalancierter Baum (AVL) – Beispiel
Aufwandsabschätzung
Operation Aufwand
Einfügen O(ln N)
Löschen O(ln N)
Indexzugriff O(N)
Suche O(ln N)
Holger Vogelsang Informatik 2 - Datenstrukturen 147
BäumeBalancierter Baum (Top-Down 2-3-4) – Idee
AVL-Bäume sind kompliziert auszugleichen. Normale binäre Bäume können im schlimmsten Fall zu einer linearen Liste entarten. Idee: Bäume können an einem Knoten mehr als einen Schlüssel haben.
2-Knoten (1 Schlüssel) 3-Knoten (2 Schlüssel)
4-Knoten (3 Schlüssel)
n
< n > n
n0
< n0 > n1
n1
> n0< n1
n0
< n0 > n2
n1
> n0< n1
n2
> n1< n2
Holger Vogelsang Informatik 2 - Datenstrukturen 148
BäumeBalancierter Baum (Top-Down 2-3-4) – Suchoperation anhand eines Beispiels
Suche nach dem Schlüssel 15: Enthält der aktuelle Knoten den gesuchten Schlüssel: fertig. Wähle das Intervall, in dem der Schlüssel liegen müsste und folge der Kante zum
nächsten Knoten.
10 20
13 14 157 8 22 24
15
Holger Vogelsang Informatik 2 - Datenstrukturen 149
BäumeBalancierter Baum (Top-Down 2-3-4) – Einfügeoperation (naiv)
Grundidee (ineffizient) Suche nach dem Blatt-Knoten, in dem der Schlüssel liegen müsste. Der Knoten ist ein 2-Knoten: Schlüssel einfügen, es entsteht ein 3-Knoten. Der Knoten ist ein 3-Knoten: Schlüssel einfügen, es entsteht ein 4-Knoten. Der Knoten ist ein 4-Knoten:
Möglichkeit 1: Den Schlüssel als neues Blatt an den 4-Knoten anhängen Problem: Wie soll ausbalanciert werden?
Möglichkeit 2: Durchführen der folgenden Schritte: 1. Den mittleren Schlüssel des 4-Knotens entnehmen.2. Den 4-Knoten in zwei 2-Knoten aufspalten.3. Den neuen Schlüssel in einen der 2-Knoten einfügen.4. Den mittleren Knoten des ehemaligen 4-Knotens in den Vaterknoten einfügen.5. Wenn der Vater vorher ein 4-Knoten war auch aufspalten.6. Im schlimmsten Fall bis zur Wurzel aufspalten.
Holger Vogelsang Informatik 2 - Datenstrukturen 150
BäumeBalancierter Baum (Top-Down 2-3-4) – Einfügeoperation (effizient)
Grundidee (effizient) Suche nach dem Knoten/Blatt, in dem der Schlüssel liegen müsste. Teile jeden auf dem Pfad liegenden 4-Knoten in 2 2-Knoten auf (der 2. Durchlauf entfällt
dadurch).
Holger Vogelsang Informatik 2 - Datenstrukturen 151
BäumeBalancierter Baum (Top-Down 2-3-4) – Einfügeoperation (effizient)
Die Wurzel des Baums wird grundsätzlich in 3 2-Knoten aufgeteilt, wenn sie ein 4-Knoten war.
Da die 4-Knoten auf dem Weg von der Wurzel zu den Blättern gespalten werden, spricht man von einem Top-Down-Baum.
Der Baum wächst immer in Richtung Wurzel, daher ist er stets ausbalanciert. Alle Äste wachsen gleichmäßig.
In der Praxis sind relativ wenige Aufspaltungen eines 4-Knotens erforderlich.
Holger Vogelsang Informatik 2 - Datenstrukturen 152
BäumeBalancierter Baum (Top-Down 2-3-4) – Einfügeoperation anhand eines Beispiels
Einfügen des Schlüssels 16:
10 20
13 14 157 8 22 24
Ausgangssituation
10 14
137 8 15
Einfügen von 16(vor Teilen der Wurzel)
20
22 2416
Holger Vogelsang Informatik 2 - Datenstrukturen 153
BäumeBalancierter Baum (Top-Down 2-3-4) – Einfügeoperation anhand eines Beispiels
10
137 8 15
Einfügen von 16(nach Teilen der Wurzel)
22 24
14
20
16
Holger Vogelsang Informatik 2 - Datenstrukturen 154
BäumeBalancierter Baum (Top-Down 2-3-4) – Aufwandsabschätzung
Der Baum ist immer balanciert.
Operation Aufwand
Einfügen, sortierte Reihenfolge O(ln N)
Einfügen, zufällige Reihenfolge O(ln N), im Mittel θ(ln N)
Löschen O(ln N)
Indexzugriff O(N)
Suche O(ln N)
Holger Vogelsang Informatik 2 - Datenstrukturen 155
BäumeBalancierter Baum (Red-Black) – Idee
Die Implementierung des Einfügens in einen 2-3-4-Baum ist leicht ineffizient, da in jedem Schritt geprüft werden muss, ob eine Aufspaltung notwendig ist.
Neue Idee 3-Knoten und 4-Knoten werden als spezielle kleine binäre Bäume dargestellt, die durch
„rote“ Verbindungen verkettet sind. Die „schwarzen“ Verkettungen halten den kompletten Baum selbst zusammen.
Ein zusätzliches Bit im Knoten zeigt an, ob er über eine rote oder eine schwarze Verbindung mit seinen Vater verkettet ist.
Ein Rot-Schwarz-Baum kann als eine spezielle Implementierung des 2-3-4-Baums gesehen werden.
Holger Vogelsang Informatik 2 - Datenstrukturen 156
BäumeBalancierter Baum (Red-Black) – Idee
Umwandlung eines 4-Knotens in einen kleinen Binärbaum:
Umwandlung eines 3-Knotens in einen kleinen Binärbaum:
Holger Vogelsang
BäumeBalancierter Baum (Red-Black) – Idee
Bedingungen für die Farben: Jeder Knoten im Baum ist entweder rot oder schwarz eingefärbt. Die Wurzel des Baums ist immer schwarz. Alle Blätter sind schwarz. Ist ein Vaterknoten rot, so sind beide Nachfolger schwarz. Jeder Pfad von einem beliebigen Knoten zu seinen Blättern enthält die gleiche Anzahl
schwarzer Knoten. Konsequenz: Die Pfadlängen von der Wurzel zu den Blättern kann sich maximal um den
Faktor 2 unterscheiden. Warum? Im kürzesten Pfad sind alle Knoten schwarz. Im längsten Pfad wechseln sich rote und schwarze Knoten ab.
Informatik 2 - Datenstrukturen 157
Holger Vogelsang Informatik 2 - Datenstrukturen 158
BäumeBalancierter Baum (Red-Black) – Aufwandsabschätzung
Der Red-Black-Tree soll hier nicht näher betrachtet werden.Der Baum ist immer balanciert.
Operation Aufwand
Einfügen, sortierte Reihenfolge O(ln N)
Einfügen, zufällige Reihenfolge O(ln N), im Mittel θ(ln N)
Löschen O(ln N)
Indexzugriff O(N)
Suche O(ln N)
Holger Vogelsang Informatik 2 - Datenstrukturen 159
BäumeImplementierungen in Java
Baum-Klassen
Holger Vogelsang
BäumeImplementierungen in Java
Baumimplementierungen in Java (Rot-Schwarz-Baum): TreeMap<K,V>:
- Ablage von Schlüssel-/Wertepaaren- Schlüsselduplikate sind nicht erlaubt.- Mehrere Iterierungsmöglichkeiten (wie bei HashMap):
• public Set<Map.Entry<K,V>> entrySet() liefert die Menge aller Schlüssel/Werte-Paare, über die iteriert werden kann
• public Set<K> keySet() liefert die Menge aller Schlüssel, über die iteriert werden kann
• public Collection<V> values() ermittelt alle Werte, über die iteriert werden kann
TreeSet<E>:- Ablage von Schlüsseln- Schlüsselduplikate sind nicht erlaubt.- Iteratorzugriff mit der Methode public Iterator<E> iterator()
Informatik 2 - Datenstrukturen 160
Holger Vogelsang Informatik 2 - Datenstrukturen 161
BäumeDie Klasse TreeMap: Beispiel Wörterzählen
public class TreeMapWordCountStreamTest
// Wörter einlesen. Trennzeichen sind Leerzeichen,// Tabulatoren und Zeilenumbrüche usw.public static TreeMap<String,Integer> getWords(String text)
// TreeMap zum sammeln aller Wörter als Schlüssel // sowie deren Anzahl als Wert.TreeMap<String, Integer> words = new TreeMap<>();// Der StringTokenizer zerlegt einen String in einzelne Tokens (Wörter).// Die Worttrennzeichen sind die einzelnen Zeichen im 2. Parameter.StringTokenizer tokenizer = new StringTokenizer(text, " \t\r\n.,;-");while (tokenizer.hasMoreTokens()) String input = tokenizer.nextToken();Integer count = words.get(input);words.put(input, count == null ? 1 : count.intValue() + 1);
return words;
Holger Vogelsang Informatik 2 - Datenstrukturen 162
BäumeDie Klasse TreeMap: Beispiel Wörterzählen
public static void main(String[] args)
String text = "C++ ist meine absolute Lieblingssprache und" + " ich freue mich auf die Klausur. Eigentlich"+ " ist Java meine Lieblingssprache.";
TreeMap<String, Integer> words = getWords(text);words.entrySet().stream().forEach(System.out::println);
Holger Vogelsang Informatik 2 - Datenstrukturen 163
BäumeDie Klasse TreeMap: Beispiel Wörterzählen
Eingabe C++ ist meine absolute Lieblingssprache undich freue mich auf die Klausur. Eigentlichist Java meine Lieblingssprache.
Alphabetische Ausgabe der WörterC++=1Eigentlich=1Java=1Klausur=1Lieblingssprache=2absolute=1auf=1die=1freue=1ich=1ist=2meine=2mich=1und=1
Holger Vogelsang Informatik 2 - Datenstrukturen 164
BäumeDie Klasse TreeMap: Beispiel Wörterzählen über Streams
Er geht auch kürzer über Streams:Pattern pattern = Pattern.compile("[ \t\r\n.,;-]+");pattern.splitAsStream(text) // erzeugt Stream von Wörtern.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
// Map: Key=Wort, Wert=Häufigkeit.entrySet() // Menge aller Schlüssel-/Werte-Paare.stream() // erzeugt Stream der Schlüssel-/Werte-Paare.sorted(Comparator.comparing(e -> e.getKey()))
// sortiert Daten im Stream anhand der Wörter.forEach(System.out::println);
Benötigt mehr als die doppelte Zeit! Problem: pattern.splitAsStream (also das Zerlegen des Textes in Wörter) ist sehr
langsam spezielle Eigenimplementierung könnte stark beschleunigen Die Stream-Variante selbst ist ungefähr genauso schnell wie die manuelle Verwendung des
Baums. Prinzipiell ist hier aber die Baum-Variante sinnvoller.
Holger Vogelsang Informatik 2 - Datenstrukturen 165
BäumeBalancierter Baum (B) – Idee eines Mehrwegbaums
B-Bäume sind eine Verallgemeinerung balancierter 2-3-4-Bäume. B-Bäume sind Mehrwegbäume. Die Ordnung des Baums ist o, o >= 2.
Jeder Knoten enthält maximal 2 * o Schlüssel. Jeder Knoten hat minimal o Schlüssel. Speicherausnutzung beträgt min. 50%
(Ausnahme: Wurzel, die zu weniger als 50% gefüllt sein darf). Die Schlüssel innerhalb eines Knotens sind aufsteigend sortiert. Wenn m die Anzahl der Schlüssel in einem Knoten ist, so hat der Knoten genau m + 1
Nachfolger, wenn er kein Blatt ist. Die Schlüssel des linken Teilbaums sind kleiner als der Schlüssel der Wurzel dieses
Teilbaums. Die Schlüssel des rechten Teilbaums sind größer als der Schlüssel der Wurzel dieses
Teilbaums. Alle Blattseiten liegen auf einer Ebene.
Optional: Neben einem Schlüssel können auch Werte abgelegt sein.
Holger Vogelsang Informatik 2 - Datenstrukturen 166
BäumeBalancierter Baum (B) – Idee eines Mehrwegbaums
Ein B-Baum der Ordnung 2:
Aufbau eines Knotens ohne Werte (pi = Verweis auf Nachfolger, ki = Schlüssel):
Aufbau eines Knotens mit Werten (pi = Verweis auf Nachfolger, ki = Schlüssel, vi ist Datenwert von Schlüssel ki):
25
2010
181514138752 2422 282726 383532 46454241
4030
p0 … km-1k1 p1 k2 pm-1 km pm
p0 … km-1k1 p1 k2 pm-1 km pmv1 v2 vm-1 vm
Holger Vogelsang Informatik 2 - Datenstrukturen 167
BäumeBalancierter Baum (B) – Einsatzgebiet
B-Bäume werden häufig zur Verwaltung von Daten auf externen Massenspeichern eingesetzt: Der Baum enthält Schlüssel und Indizes für die eigentlichen Nutzdaten. Die Nutzdaten liegen sequentiell in einer eigenständigen Datei vor. Vorteile dieser Organisation:
- Wenn auf die Daten nicht sequentiell zugegriffen werden muss, muss nur der Baum abgesucht werden. Dieser enthält dann die Position der Nutzdaten in der zweiten Datei.
- Zum Einfügen und Löschen muss die Reihenfolge der Nutzdaten nicht verändert werden.
- Es sind nur sehr wenige Zugriffe notwendig Zugriffe auf den Massenspeicher sind sehr langsam.
- Nur der Wurzelknoten des Baums wird im Speicher gehalten. Ein ähnlicher Aufbau wird für Datenbanken gewählt.
Holger Vogelsang Informatik 2 - Datenstrukturen 168
BäumeBalancierter Baum (B) – Aufbau bei externem Massenspeicher
Zusammenhang zwischen Index (Baum) und Nutzdatendatei:
Anmerkungen: Im Beispiel: Schlüssel = Position in der Datei In der Realität: zusätzlich Nutzdaten mit der Position als Wert
10
181514138752
Satz 2
…
Satz 7
Satz 27
Satz 1
…
Satz 42
Satz 3
…
usw.
Holger Vogelsang Informatik 2 - Datenstrukturen 169
BäumeBalancierter Baum (B) – Suchoperation
Funktionsweise der Suchoperation:1. Startknoten: Wurzel des Baums2. Suche mittels Binärsuche nach dem Schlüssel.3. Ist der Schlüssel vorhanden, so ist die Suche beendet.4. Ermittlung des Nachfolgeknotens: Auswahl des Verweises zwischen den zwei Werten,
zwischen denen der Suchschlüssel liegen muss.5. Wenn ein Nachfolgeknoten existiert (Knoten ist kein Blatt), dann lade den Knoten vom
Massenspeicher weiter an Punkt 2.6. Wenn kein Nachfolgeknoten existiert, so ist der Schlüssel nicht im Baum vorhanden.
Holger Vogelsang Informatik 2 - Datenstrukturen 170
BäumeBalancierter Baum (B) – Suchoperation am Beispiel
Suche nach dem Schlüssel 35:
25
2010
181514138752 2422 282726 3832 46454241
4030
35
Holger Vogelsang Informatik 2 - Datenstrukturen 171
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
Es soll ein Baum durch das Einfügen der folgenden Schlüssel entstehen: 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25.
Der Baum hat die Ordnung 2. Einfügen:
Analog zum Top-Down 2-3-4 Baum Das mittlere Element wird nach dem (gedachten) Einfügen ermittelt.
20
Eingefügt: 20
20
Eingefügt: 40
40 402010
Eingefügt: 10
402010
Eingefügt: 30
30
10 30
20
4015
Eingefügt: 15
10 30
20
15
Eingefügt: 35
4035
Holger Vogelsang Informatik 2 - Datenstrukturen 172
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
30
20
3510
Eingefügt: 7
157
20
3010
Eingefügt: 26
157 3526
20
3010
Eingefügt: 18
157 352618
20
4010
Eingefügt: 22
157 3518
40 40
40
30
2622
Holger Vogelsang Informatik 2 - Datenstrukturen 173
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
2010
26 40351815 22
Eingefügt: 5
30
75
2010
26 40351815 22
Eingefügt: 42
30
75 42
Holger Vogelsang Informatik 2 - Datenstrukturen 174
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
2010
26 403515 22
Eingefügt: 13
30
75 421813
2010
26 403515 22
Eingefügt: 46
30
75 421813 46
Holger Vogelsang Informatik 2 - Datenstrukturen 175
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
2010
26 403515 22
Eingefügt: 27
30
75 421813 4627
2010
26 403515 22
Eingefügt: 8
30
75 421813 46278
Holger Vogelsang Informatik 2 - Datenstrukturen 176
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
2010
26 3515 22
Eingefügt: 32
30
75 1813 278 4642
40
32
2010
26 3515 22
Eingefügt: 38
30
75 1813 278 4642
40
32 38
Holger Vogelsang Informatik 2 - Datenstrukturen 177
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
2010
3515 22
Eingefügt: 24
30
75 1813 268 4642
40
32 382724
2010
3515 22
Eingefügt: 45
30
75 1813 268 42
40
32 382724 4645
Holger Vogelsang Informatik 2 - Datenstrukturen 178
BäumeBalancierter Baum (B) – Einfügeoperation am Beispiel
4030
3515 22
Eingefügt: 25
75 18138 4232 3824 4645
25
2010
26 27
Holger Vogelsang Informatik 2 - Datenstrukturen 179
BäumeBalancierter Baum (B) – Löschoperation
Löschoperation in einem B-Baum:1. Unterscheidung zweier Fälle:
- Das zu löschende Objekt liegt in einem Blatt. Es wird gelöscht Schritt 2.- Das zu löschende Objekt liegt nicht in einem Blatt: Aus dessen linkem Teilbaum
wird der Knoten mit dem größten Schlüssel geholt (oder aus dem rechten Teilbaumder mit dem kleinsten). Dieses ersetzt das zu löschende Objekt Schritt 2.
2. Ausgleichen: Durch das Löschen der Schlüssel kann ein Unterlauf auftreten (der Knoten ist nicht mehr zu min. 50% gefüllt). Es werden eine benachbarte Seite geladen und die Schlüssel auf beide Seiten gleichmäßig verteilt.
3. Tritt dabei ein Unterlauf auf, werden beide Seiten zusammengelegt und der mittlere Schlüssel des Vaterknoten in die gemeinsame Seite eingefügt.
4. Jetzt kann im Vaterknoten ein Unterlauf auftreten Schritt 2.
Holger Vogelsang Informatik 2 - Datenstrukturen 180
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
Es sollen aus dem Baum die folgenden Schlüssel entfernt werden: 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 5, 22, 18, 26, 7, 35, 15.
Der Baum hat die Ordnung 2.
4030
3515 2275 18138 4232 3824 4645
25
2010
26 27
Holger Vogelsang Informatik 2 - Datenstrukturen 181
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
4030
3515 20
Gelöscht: 25
75 138 4232 3822 4645
24
1810
26 27
4030
3515 20
Gelöscht: 45
75 138 4232 3822 46
24
1810
26 27
Holger Vogelsang Informatik 2 - Datenstrukturen 182
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
2210
3515 26
Gelöscht: 24
30
75 18138 42
40
32 3827 4620
2210
3515 26
Gelöscht: 38
30
75 18138 42
40
3227 4620
Holger Vogelsang Informatik 2 - Datenstrukturen 183
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
2210
4015 26
Gelöscht: 32
30
75 18138 423527 4620
2210
4015 26
Gelöscht: 8
30
75 1813 423527 4620
Holger Vogelsang Informatik 2 - Datenstrukturen 184
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
2210
4215 26
Gelöscht: 27
35
75 1813 46403020
2210
4215 26
Gelöscht: 46
35
75 1813 403020
Holger Vogelsang Informatik 2 - Datenstrukturen 185
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
2210
4218 26
Gelöscht: 13
35
75 2015 4030
2210
4018 26
Gelöscht: 42
75 2015 3530
Holger Vogelsang Informatik 2 - Datenstrukturen 186
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
2215
4020 26
Gelöscht: 5
107 18 3530
2615
20 30
Gelöscht: 22
107 18 4035
Holger Vogelsang Informatik 2 - Datenstrukturen 187
BäumeBalancierter Baum (B) – Löschoperation am Beispiel
3015
26 35
Gelöscht: 18
107 20 40
15
30 35
Gelöscht: 26
107 20 40
20
35 40
Gelöscht: 7
1510 30
20
40
Gelöscht: 35
1510 30 10 20 30 40
Gelöscht: 15
Holger Vogelsang Informatik 2 - Datenstrukturen 188
BäumeBalancierter Baum (B) – Sequentieller Datenzugriff
Inorder-Durchlauf aller Knoten: Nachteil: Auf Knoten muss mehrfach zugegriffen werden (Laden vom Massenspeicher!).
Holger Vogelsang Informatik 2 - Datenstrukturen 189
BäumeBalancierter Baum (B) – Aufwandsabschätzungen
Bedeutung der Ordnung o des Baums: Je größer o ist, desto flacher wird der Baum Je kleiner o ist, desto geringer ist der Aufwand zum Suchen innerhalb des Knotens.
Seien n = Anzahl Knoten im Baum mit n >= 2 o = Ordnung des Baums mit o >= 1 Dann gilt für die Höhe h des Baum: h <= log2*o ((n+1) / 2)
Damit gilt für die Suche eines Schlüssels Ermittlung und Laden der Seiten entlang des Pfads: O(log2*o( (n+1)/2 )) Suche innerhalb einer Seite mittels Binärsuche: O(ld( 2*o ))
Damit gilt für die komplette Suche: O(log2*o((n+1)/2 ))* O(ld( 2*o )), wobei der Aufwand für das Laden einer Seite wegen der Plattenzugriffe deutlich höher als die Suche innerhalb der Seite ist.
Holger Vogelsang Informatik 2 - Datenstrukturen 190
BäumeBalancierter Baum (B) – Aufwandsabschätzungen
Erste Idee: Ein Knoten soll möglichst viele Schlüssel enthalten. Konsequenzen:
Beim rekursiven Abstieg zum Einfügen werden alle gefundenen Knoten im Speicher gehalten, um die Anzahl der Plattenzugriffe klein zu halten. Dadurch wächst bei sehr vielen Knoten der Speicherbedarf an.
Werden die Knoten nicht mehr im Speicher gehalten, so wächst die Zeit für die Plattenzugriffe (Verdopplung).
Bessere Idee: Häufig wird die Knotengröße so gewählt, dass ein Knoten sehr gut beispielsweise in einen Sektor auf dem externen Speicher passt und so effizient gelesen werden kann.
Holger Vogelsang Informatik 2 - Datenstrukturen 191
BäumeBalancierter Baum (B+/B*)
Der B+-Baum (je nach Literatur auch B*-Baum) ist eine Abwandlung des B-Baums mit Daten: Innere Knoten enthalten nur Schlüssel (so genannte Separatorschlüssel) und Nachfolger
als Paare (ki, pi):
- p0 verweist auf einen Knoten mit Schlüsseln kleiner oder gleich k1.- pi (1 ≤ i < m) verweist auf einen Knoten mit Schlüsseln größer als ki und kleiner oder
gleich ki+1.- pm verweist auf einen Knoten mit Schlüsseln größer als km.
Die Werte befinden sich zusammen mit den Schlüsseln nur in den Blättern als Paare (ki, vi):
Die Daten werden in der Sortierreihenfolge der Schlüssel abgelegt. Alle Blätter werden zu einer doppelt verketteten Liste verbunden (Verweis p, n oben)
sehr schnelles sequentielles Durchlaufen aller Daten.
p0 … km-1k1 p1 k2 pm-1 km pm
p … km-1k0 k1 km nv0 v1 vm-1 vm
Holger Vogelsang Informatik 2 - Datenstrukturen 192
BäumeBalancierter Baum (B+/B*)
Jeder innere Knoten hat min. k und max. 2k Einträge (=Ordnung beim B-Baum). Jeder Blattknoten hat min. k* und max. 2k* Einträge (außer Wurzel).
Wozu? In den inneren Knoten ist „mehr Platz“ für Schlüssel und Verweise auf Nachfolger
Baumhöhe sinkt bei identischer Knotengröße. Einfaches Sequentielles Durchlaufen der Datenelemente. B* ist die wichtigste Variante des B-Baums.
Holger Vogelsang Informatik 2 - Datenstrukturen 193
BäumeBalancierter Baum (B+/B*) – Einfügeoperation
Einfügen: Ähnlich wie beim B-Baum.
1. Suche den Schlüssel des neuen Datensatzes im Baum führt immer zu einem Blatt, da Daten nur in Blättern gespeichert werden.
2. Füge den neuen Datensatz im Blatt ein. 3. Falls der Knoten überläuft, wird er gespalten („in der Mitte“).4. Beim Spalten wird ein „mittlerer“ Schlüssel (Separatorschlüssel) erzeugt und in den
Vaterknoten eingefügt. 5. Der Separatorschlüssel kann im Blatt vorkommen, muss es aber nicht.6. Beim Überlauf des Vaterknotens: weiter in Schritt 3
Holger Vogelsang Informatik 2 - Datenstrukturen 194
BäumeBalancierter Baum (B+/B*) – Einfügeoperation am Beispiel
Beispiel: k = 4, k* = 2 Startsituation (Knoten bestehen aus Schlüssel und zugehörigem Wert):
Schrittweises Einfügen von [30, „Hoffmann“]:
Aufspalten des Knotens und Erzeugung eines Separatorschlüssels (23) in einem neuen gemeinsamen Vaterknoten.Neue Knoten als Liste verketten.
Überlauf im Vaterknoten: Rekursiv zur Wurzel hin fortsetzen.
10 Vogelsang 15 Pape 20 Gmeiner 25 Nestler
10 Vogelsang 15 Pape 20 Gmeiner 25 Nestler
10 Vogelsang 15 Pape 20 Gmeiner 25 Nestler 30 Hoffmann
23
30 Hoffmann
Überlauf
Holger Vogelsang Informatik 2 - Datenstrukturen 195
BäumeBalancierter Baum (B+/B*) – Löschoperation, sequentieller Datenzugriff
Löschen Daten werden immer nur in den Blättern gelöscht. Unterlauf ähnlich wie beim B-Baum soll hier nicht näher betrachtet werden.
Sequentieller Datenzugriff Verzeigerung in den Blattseiten folgen Vorteil: Auf jeden Blattknoten muss nur einmal zugegriffen werden.
Die Nutzdaten befinden sich nur in den Blättern!
Holger Vogelsang Informatik 2 - Datenstrukturen 196
BäumeVergleich von B- und B+/B*-Baum
B-Baum:
B+/B*-Baum:
Index(mit Schlüsselnund Werten)
Index(mit Separator-schlüsseln)
Schlüssel mit Werten
Holger Vogelsang Informatik 2 - Datenstrukturen 197
BäumeTries (digitale Bäume)
Trie (gesprochen „try“): Baum zur Speicherung von Zeichenketten eines Dokumentes, um später leicht das Vorhandensein der Texte im Dokument feststellen zu können (retrieval).
Aufbau: Knoten ist ein Array mit der Größe = Kardinalität des Alphabetes. Jeder Eintrag enthält einen Verweis auf einen anderen Knoten. Die Buchstaben werden nicht um Baum gespeichert (Index ergibt Buchstaben).
Aufbau: Alphabet mit 26 Zeichen als Großbuchstaben.
A B C D X Y Z…
A B C D X Y Z…
A B C D X Y Z…
A B C D X Y Z…
Holger Vogelsang Informatik 2 - Datenstrukturen 198
BäumeTries (digitale Bäume)
Beispiel (unvollständig):
Probleme: Ungleichmäßige Verteilung der Daten (viele leere Verweise z.B. für Kombinationen wie
XX, XY, YY, YYYZ, …). Entartung zur Liste möglich.
A B C D Z… F …
E … R ……
Y
E … R ……
N … T …… E … I …… E … I ……
J … N …… G … T ……
Benjamin Bennet Bettina Brigitte Britta Fred Frieda
Holger Vogelsang Informatik 2 - Datenstrukturen 199
BäumeBinäre Tries
Ausweg aus dem Problem der ungleichmäßigen Auslastung: Repräsentation der Zeichenketten als Binärfolge. Knoten enthält nur noch Nachfolger für 0 und 1.
Weiterhin problematisch: Entartung zu Listen.
Holger Vogelsang Informatik 2 - Datenstrukturen 200
BäumePatricia Bäume
Ziel: Vermeidung des Entartens zu einer Liste. Lösung: Practical Algorithm to Retrieve Information Coded in Alphanumeric (Patricia). Idee:
Irrelevante Teile der Zeichenkette werden übersprungen. Jeder Knoten enthält die Anzahl zu überspringender Zeichen (Trie) oder Bits (bin. Trie).
Beispiel (kompakte Darstellung eines Trie):
2
4
2
Oberkante
Objektiv
Objektmenge Objektmethode
e j
i m
n t
Holger Vogelsang Informatik 2 - Datenstrukturen 201
BäumePatricia Bäume
Suchen: Die im Knoten angegebenen Stellen überspringen. Zum richtigen Nachfolger laufen.
Vorteil: Kompakte Struktur, schnelleres Durchlaufen (besonders bei langen Wörtern).
Holger Vogelsang
Typinfo.,I/O
Annota-tionen
Laufzeit-typinfo.
Ein-,Ausgabe
GraphenÜbersicht
Informatik 2 - Datenstrukturen 202
GrafischeOberflä-
chenÜbersicht Layouts Widgets Grafik-
operationenGrafik-widgets
Effekte,Animationen
OffenePunkteEreignisse
Daten-strukturen ADTs Elementare
DatenstrukturenHash-
tabellen Bäume GraphenIteratoren,Streams
Datenstrukturenin Java
JavaScript Prinzipien Einstieg VererbungObjekte DOM-Zugriffe
Module
Holger Vogelsang Informatik 2 - Datenstrukturen 203
GraphenMotivation
Wozu dienen Graphen? Welche Arten von Informationen können damit modelliert werden? Wie können Graphen im Speicher abgebildet werden? Einige wichtige Algorithmen für Graphen.
Holger Vogelsang Informatik 2 - Datenstrukturen 204
GraphenIdee
Viele Probleme lassen sich allgemein unter Verwendung von Objekten und Verbindungen formulieren: Darstellung eines Straßennetzes:
[https://maps.google.com/]
Holger Vogelsang
GraphenIdee
Schienennetzplan (KVV):
[http://www.kvv.de/fileadmin/user_upload/kvv/dokumente/netz/liniennetz/2013/L0SCHI_DEZ12_Betreiber.pdf]
Informatik 2 - Datenstrukturen 205
Holger Vogelsang
GraphenIdee
Oder etwas berühmter (London Tube):
[http://www.tfl.gov.uk/assets/downloads/standard-tube-map.gif]
Informatik 2 - Datenstrukturen 206
Holger Vogelsang
GraphenIdee
Beziehungen in einem sozialen Netzwerk:
[http://blog.iconsultants.eu/2012/10/was-ist-der-facebook-open-graph-und-warum-gibt-es-ihn/]
Netz aller Flugverbindungen Elektronische Schaltungen aus Komponenten und Verbindungen Scheduling: Welche Aufgaben hängen von anderen Aufgaben ab?
Informatik 2 - Datenstrukturen 207
Holger Vogelsang Informatik 2 - Datenstrukturen 208
Begriffe Ein Graph ist eine Menge von Knoten und Kanten. Knoten sind einfache Objekte, die Namen und andere Eigenschaften haben können. Kanten sind Verbindungen zwischen Knoten.
GraphenBegriffe
6 39
Knoten
27 41
42 68
51
16
Kante
Holger Vogelsang Informatik 2 - Datenstrukturen 209
GraphenBegriffe
Ein Graph ist unabhängig von seiner Darstellung:
Ein Pfad von einem Knoten x zu einem Knoten y ist eine Liste von aufeinander folgenden Knoten, die durch Kanten verbunden sind.
Ein Graph ist zusammenhängend, wenn von jedem Knoten zu jedem anderen Knoten ein Pfad existiert.
Ein Zyklus ist ein Pfad, in dem Anfangs- und Endknoten identisch sind. Ein Baum ist ein Graph ohne Zyklen. Ein Gruppe nicht zusammenhängender Bäume wird Wald genannt.
6 39
27 41
42 68
51
16
41 39
27 6
42 68
5116
Holger Vogelsang Informatik 2 - Datenstrukturen 210
GraphenBegriffe
Ein Spannbaum ist ein Teilgraph, der alle Knoten enthält sowie die Kanten, die notwendig sind, um einen Baum zu bilden.
Graphen mit wenigen Kanten (E < V log V) werden licht genannt. Graphen, in denen nur wenige Kanten fehlen, werden dicht genannt. Gewichtete Graphen: Die Kanten haben Gewichte (Kosten, Entfernungen, ...). Gerichtete Graphen: Die Kanten können nur in einer vorgegebenen Richtung durchlaufen
werden („Einbahnstraßen“).
6 39
27 41
42 68
51
16
Graph
6 39
27 41
42 68
51
16
Spannbaum
Holger Vogelsang Informatik 2 - Datenstrukturen 211
GraphenDarstellung im Programm
Knoten werden auf ganze Zahlen (Indizes) abgebildet, um sehr effizient darauf zugreifen zu können: Knoten werden nummeriert. Der Hashwert des Namens eines Knotens wird als Index verwendet perfekte
Hashfunktion. Einfachste Darstellung eines Graphen: Adjazenzmatrix („Nachbarschaftsmatrix“):
Annahme: Der Graph hat V Knoten. Es wird ein Feld (zweidimensionales Array) graph der Größe V*V mit Boole‘schen
Werten gefüllt:- Der Wert graph[ x ][ y ] = true, wenn eine Kante von Knoten x zu Knoten y
führt.- Der Wert graph[ x ][ y ] = false, wenn es diese Kante nicht gibt.- Die Matrix ist symmetrisch für ungerichtete Graphen: graph[ x ][ y ] = graph[ y ][ x ] Speicherplatzverschwendung, aber einfachere Algorithmen
Holger Vogelsang Informatik 2 - Datenstrukturen 212
GraphenDarstellung im Programm
- In der Regel ist es praktisch zu definieren, dass ein Knoten immer zu sich selbst führt: graph[ x ][ x ] = true abhängig vom Einsatz des Graphen
Beispiel:
Löschen eines Knotens x: An den Positionen [ 0...V-1 ][ x ] und[ x ][ 0...V-1 ] muss false eingetragen werden (Löschen der Kanten).
0 1 2 3 4 5 6 7
0 t f f f f t t f
1 f t t f f f t f
2 f t t f t f f f
3 f f f t t t f t
4 f f t t t t t f
5 t f f t t t f f
6 t t f f t f t f
7 f f f t f f f t
0 5
6 4
1 2
3
7
Holger Vogelsang Informatik 2 - Datenstrukturen 213
GraphenDarstellung im Programm
Beispielgraph:
1 2
3
46
5 70
Holger Vogelsang Informatik 2 - Datenstrukturen 214
GraphenDarstellung im Programm
Aufwand Adjazenzmatrix: O(V2) Speicherplätze sowie O(V2) Schritte zur Initialisierung. Nachteil der Adjazenzmatrix: Bei lichten Graphen ist die Speicherplatzverschwendung sehr
hoch. Für lichte Graphen existiert daher eine Adjazenzliste („Nachbarschaftsliste“, auch
Adjazentstruktur): Für jeden Knoten werden alle mit ihm verbundenen Knoten in einer Liste gehalten. Die Listen liegen in einem eindimensionalen Array.
Beispiel:
0 5
6 4
1 2
3
7
0 1 2 3 4 5 6 7
5
6
2
6
1
4
4
5
7
2
3
0
3
4
0
1
4
3
5
6
Holger Vogelsang Informatik 2 - Datenstrukturen 215
GraphenDarstellung im Programm
Ein Kante, die Knoten x mit Knoten y verbindet, wird in der Liste von Knoten x und in der Liste von Knoten y aufgeführt effiziente Suche: Mit welchen Knoten ist Knoten xverbunden?
Vorteil Speicherbedarf: O(V+E), Initialisierung: O(V) Nachteile:
Einige Algorithmen sind aufwändiger und ineffizienter zu implementieren. Das Löschen eines Knotens x ist aufwändig: In allen Listeneinträgen von x den Knoten x
löschen, dann alle Listeneinträge von x löschen. Konsequenz: Keine „direkte“ Darstellung eines Graphen im Speicher, da der Aufwand für
Algorithmen sonst sehr hoch wird.
Holger Vogelsang Informatik 2 - Datenstrukturen 216
GraphenDarstellung gerichteter und gewichteter Graphen im Programm
Gerichtete Graphen Jede Kante wird nur einmal dargestellt. Darstellung einer Kante von Knoten x zu Knoten y:
Adjazenzmatrix: graph[ x ][ y ] = true. Adjazenzliste/Adjazenzstruktur: y erscheint in der Liste von x.
Gewichtete Graphen Die Darstellung erfolgt wie bei ungerichteten Graphen mit den folgenden Erweiterungen:
Adjazenzmatrix: Anstelle von true steht in graph[ x ][ y ] der numerische Wert (die Gewichtung) der Kante. Anstelle von false wird eine nicht benutzte Gewichtung eingetragen (z.B. -1).
Adjazenzliste/Adjazenzstruktur: Die Liste enthält für jeden Eintrag ein weiteres Feld mit der Gewichtung.
Holger Vogelsang Informatik 2 - Datenstrukturen 217
GraphenTiefensuche
Tiefensuche: systematisches Besuchen aller Knoten und Kanten im Graphen Der Algorithmus ist Basis vieler anderer Lösungen im Zusammenhang mit Graphen. Ablauf:
Ein Feld visitedNodes nimmt für alle Knoten den Index in der Besuchsreihenfolge auf. Wurde der Knoten noch nicht besucht, so enthält es die Konstante UNSEEN (z.B. -1). Solange es noch unbesuchte Knoten ki gibt, wird der nächste unbesuchte aus
visitedNodes genommen:- In visitedNodes erhält der Knoten ki den nächsten Index.- Es werden alle von ki aus erreichbaren Knoten besucht, die bisher noch nicht
besucht wurden.
Holger Vogelsang Informatik 2 - Datenstrukturen 218
GraphenTiefensuche
V ist die Anzahl der Knotenprivate int[] visitedNodes = new int[ V ];private int visitId;private static final int UNSEEN = -1;
public void visitNodes()
visitId = 0;
// Reihenfolgearray löschenfor (int i = 0; i < V; ++i)
visitedNodes[ i ] = UNSEEN;
// Knoten besuchenfor (int i = 0; i < V; ++i)
if (visitedNodes[ i ] == UNSEEN) visitNode(i);
Holger Vogelsang Informatik 2 - Datenstrukturen 219
GraphenTiefensuche
Tiefensuche bei Darstellung mit Adjazenzmatrix Der Graph liegt im zweidimensionalen Array graph. Rekursives Besuchen aller Knoten, die mit dem übergebenen Knoten verbunden sind:
public void visitNode(int nodeIndex) visitedNodes[ nodeIndex ] = ++visitId;
// Alle Zellen der Zeile des Knotens absuchenfor (int i = 0; i < V; ++i)
if (graph[ nodeIndex ][ i ] && (visitedNodes[ i ] == UNSEEN)) visitNode(i);
Zeitaufwand für die Tiefensuche: O(V2), da jedes Bit in der Matrix geprüft wird.
Holger Vogelsang Informatik 2 - Datenstrukturen 220
GraphenTiefensuche
Beispiel (siehe Tafelanschrieb):
0 5
6 4
1 2
3
7
Holger Vogelsang Informatik 2 - Datenstrukturen 221
GraphenTiefen- und Breitensuche
Hinweise Die Rekursion kann genau wie bei Bäumen durch eine Iteration unter Verwendung einer
Stack-Klasse implementiert werden. Wird der Stack durch eine Schlange (Queue) ersetzt, so ergibt sich automatisch Breitensuche. Unterschiede zwischen Breiten- und Tiefensuche:
Tiefensuche: Es werden erst die Pfade zu den am weitesten entfernt liegenden Knoten gesucht. Erst im Fall einer Sackgasse werden näher liegende Knoten besucht.
Breitensuche: Erst werden alle Knoten in der Nähe und danach immer weiter weg liegende Knoten betrachtet.
Holger Vogelsang Informatik 2 - Datenstrukturen 222
GraphenBreitensuche iterativ
Der folgende Ausschnitt zeigt eine iterative Lösung zur Breitensuche im Graphen.private int[] visitedNodes = new int[ V ];private static final int UNSEEN = -1;
public void breadthFirstSearch(int startNode)
int visitId = 0;// Breitensuche mit Queue// Tiefensuche mit Deque (als Stack)Queue<Integer> queue = new LinkedList<>();
// Reihenfolgearray löschenfor (int i = 0; i < V; ++i)
visitedNodes[ i ] = UNSEEN;
queue.offer(startNode);
while (!queue.isEmpty()) // Vordersten Knoten der Queue besuchenint node = queue.poll(); // Tiefensuche: queue.pollLast();
Holger Vogelsang Informatik 2 - Datenstrukturen 223
GraphenBreitensuche iterativ
if (visitedNodes[ node ] == UNSEEN)
visitedNodes[ node ] = ++visitId;
// Alle Zellen der Zeile des Knotens absuchenfor (int i = V - 1; i >= 0; --i)
if (graph[ node ][ i ] && (visitedNodes[ i ] == UNSEEN)) queue.offer(i);
Holger Vogelsang Informatik 2 - Datenstrukturen 224
GraphenSuche des kürzesten Pfades iterativ
Der Breitensuchalgorithmus kann sehr leicht zur Suche des kürzesten Pfades zwischen zwei Knoten verwendet werden: Statt der Reihenfolge der Besuche wird in predNodes der Vorgänger jedes Knotens
abgelegt. Der Algorithmus bricht ab, wenn das Ziel erreicht ist.
Algorithmus:private boolean[] visitedNodes = new boolean[ V ];private int[] predNodes = new int[ V ];private final static int UNSEEN = -1;
public boolean pathfinder(int startNode, int endNode)
LinkedList<Integer> queue = new LinkedList<>();
// Reihenfolgearray löschenfor (int i = 0; i < V; i++)
visitedNodes[ i ] = false;predNodes[ i ] = UNSEEN;
queue.offer(startNode);
Holger Vogelsang Informatik 2 - Datenstrukturen 225
GraphenSuche des kürzesten Pfades iterativ
while (!queue.isEmpty()) // Vordersten Knoten der Queue besuchenint node = queue.pollFirst();
if (!visitedNodes[ node ]) visitedNodes[ node ] = true;
// Fertig ?if (node == endNode)
return true;// Alle Zellen der Zeile des Knotens absuchenfor (int i = V - 1; i >= 0; i--)
if (graph[ node ][ i ] && !visitedNodes[ i ]&& predNodes[ i ] == UNSEEN)
predNodes[ i ] = node; // jetzigen als Vorgänger eintragenqueue.offer(i);
return false;
Holger Vogelsang
GraphenSuche des kürzesten Pfades in einem gewichteten Graphen
Suche des kürzesten Pfades in einem gerichteten (nicht so wichtig) und gewichteten Graphen mit nicht-negativen Gewichten mittels Dijkstra-Algorithmus (gehört zu den Greedy-Alghorithmen wählen schrittweise in jedem Zustand den aussichtsreichsten Folgezustand aus)
Zeitaufwand (abhängig von der Darstellung des Graphen im Speicher): min. O(V2 + E)
Informatik 2 - Datenstrukturen 226
0 5
6 4
1 2
3
7
3
11
1
11
2
3 810
1 3
11
2 22
Holger Vogelsang
GraphenSuche des kürzesten Pfades in einem gewichteten Graphen
Ablauf:1. Alle Knoten erhalten die Attribute „aktuelle Distanz zum Startknoten“ (Distanz) und
„Vorgängerknoten im Pfad“ (Vorgänger). 2. Die Distanzen werden mit ∞ (unendlich) initialisiert. Nur der Startknoten erhält zu sich
selbst die Distanz 0.3. Solange es noch unbesuchte Knoten ki gibt, wird derjenige mit dem geringsten Abstand
zum Startknoten gewählt (verspricht am ehesten Erfolg):1. Markiere diesen Knoten ki als schon besucht2. Berechne für alle Knoten kx, die von ki aus erreichbar sind, die Abstände zum
Startknoten als: Abstand kx = Abstand ki + Gewichtung von ki zu kx
3. Ist der berechnete Abstand kx kleiner als der bisherige Abstand zu kx, dann wurde ein kürzerer Pfad zu kx gefunden:
a. Trage den neuen Abstand kx am Knoten kx ein und merke als Vorgänger von kxden Knoten ki.
b. Trage ki als Vorgänger von kx ein. Java-Code: siehe Eclipse-Projekt „GraphAlgos“.
Informatik 2 - Datenstrukturen 227
Holger Vogelsang Informatik 2 - Datenstrukturen 228
GraphenWeitere Algorithmen
Es existieren viele weitere Algorithmen für Graphen, die in der Praxis sehr wichtig sind: Kürzeste Pfade zwischen allen Knoten, kürzester Pfad von einem Knoten zu allen
anderen, … Kürzeste Menge der Linien, die alle Punkte innerhalb einer Ebene verbinden. Topologisches Sortieren eines azyklischen, gerichteten Graphen: Erst werden die Knoten
ermittelt, auf die kein anderer Knoten verweist. Dann die Knoten, auf die nur bereits im ersten Schritt ermittelte Knoten verweisen... Abhängigkeitsgraph.
Diese Algorithmen sollen nicht mehr Bestandteil der Vorlesung sein.
Holger Vogelsang
GraphenBibliotheken
Für die Verwendung von Graphen in Java existieren eine ganze Anzahl unterschiedlicher Bibliotheken. Interessant sind: JGraphT (http://www.jgrapht.org/): Frei verfügbare Bibliothek mit Graphenalgorithmen JGraph (http://www.jgraph.com/jgraph.html): Frei verfügbare Bibliothek zur Darstellung
von Graphen (z.B. denen von JGraphT) Beispiel zur Suche des kürzesten Pfades in einem Graphen (Projekt GraphDemo):
// Gerichteter GraphListenableGraph g = new ListenableDirectedGraph(DefaultEdge.class);// Knoten ergänzeng.addVertex("v1");g.addVertex("v2");g.addVertex("v3");g.addVertex("v4");// Knotenverbindeng.addEdge("v1", "v2");g.addEdge("v2", "v3");g.addEdge("v3", "v1");g.addEdge("v4", "v3");List<DefaultEdge> result = DijkstraShortestPath.findPathBetween(g, "v1", "v4");
Informatik 2 - Datenstrukturen 229