Post on 21-Sep-2020
transcript
Algorithmen und DatenstrukturenB3. Verkettete Listen und Baume
Marcel Luthi and Gabriele Roger
Universitat Basel
22. Marz 2018
Einfuhrung Verkettete Liste Baume
Einfuhrung
Einfuhrung Verkettete Liste Baume
Abstrakter Datentyp / Datenstruktur
Abstrakter Datentyp
Eine Menge von Werten undOperationen, die auf dieserMenge definiert sind.
Reprasentation undImplementation bleibtabstrakt.
ADT kann mittelsverschiedenerDatenstrukturenimplementiert sein.
Datenstruktur
Beschreibt wie die Datenorganisiert sind
Implementation undReprasentation explizit
Organisation so ausgelegt,dass gewisse Operationeneffizient ausgefuhrt werdenkonnen.
Dieselbe Datenstruktur kannin verschiedenen ADTsbenutzt werden.
Derselbe Begriff (Beispiel Array) kann sowohl fur Datenstruktur alsauch Datentyp stehen.
Einfuhrung Verkettete Liste Baume
Wiederholung: Multimengen, Warteschlangen und Stapel
Multimenge
Ungeordnet
Stapel
LIFO
Warteschlange
FIFO
Einfuhrung Verkettete Liste Baume
Wissenschaftler des Tages
Herbert Simon (Okonom)
Nobelpreistrager undGewinner des Turing Awards
Pionier in kunstlicherIntelligenz
”Erfinder “der verketteten
Liste (im Rahmen der IPLSprache).
Newell, Allen, and Fred M.Tonge. An introduction toinformation processing languageV. Communications of the ACM(1960).
Einfuhrung Verkettete Liste Baume
Verkettete Liste
Einfuhrung Verkettete Liste Baume
Motivation
Arrays sind nicht flexibel genug
Brauchen immer grossen, kontinuierlichen Block an Speicher
Einfugen ist teuer (vor allem am Anfang)
Enqueue oder Dequeue in Warteschlange hat KomplexitatO(n)
Losung muss uns erlauben Elemente im Speicher zu verteilen.
Einfuhrung Verkettete Liste Baume
Listen
Eine Liste ist eine geordnete Kollektion von n Elementen(n ∈ N0)
Array: Ordnung kommt von Anordnung in Speicher
Einfuhrung Verkettete Liste Baume
Listen
Wie kann man Elemente ordnen die verteilt im Speicher sind?
Einfuhrung Verkettete Liste Baume
Listen
Wie kann man Elemente ordnen die verteilt im Speicher sind?
Einfuhrung Verkettete Liste Baume
Verkettete Listen
Wichtige, flexible Datenstruktur
Jeder Knoten speichert sein Datum, sowie eine Referenz(Zeiger) auf Nachfolger
Ende muss speziell gekennzeichnet werden (haufig null/None).
... oder wir brauchen Referenz auf letztes Element
Einfuhrung Verkettete Liste Baume
Quiz: Komplexitat Array / Verkettete Liste
Operation Array Verkettete Liste
Zugriff auf beliebiges ElementEinfugen, Loschen am AnfangEinfugen am EndeLoschen am EndeEinfugen, Loschen in MitteVerschwendeter Speicher
Take-home Message
Verschiedene Datenstrukturen machen verschiedene Trade-offs
Einfuhrung Verkettete Liste Baume
Verkettete Listen: Datenstruktur
class Node[Item]:
# Das gespeicherte Datum
item : Item
# Referenz auf den Nachfolger
next : Node
# Konstruktur : Erzeugen eines neuen Nodes
Node(item : Item , next : Node[Item])
}
Beispiele:
Node(“first“, None)
Node(“first“, Node(“second“, None))
Node(“first“, Node(“second“, Node(“third“, None))
Einfuhrung Verkettete Liste Baume
Einfugen am Anfang
Einfuhrung Verkettete Liste Baume
Einfugen am Anfang
Einfuhrung Verkettete Liste Baume
Einfugen am Anfang
Einfuhrung Verkettete Liste Baume
Einfugen am Ende
Einfuhrung Verkettete Liste Baume
Einfugen am Ende
Einfuhrung Verkettete Liste Baume
Einfugen am Ende
Einfuhrung Verkettete Liste Baume
Weitere Operationen
Einfach:
Vom Anfang entfernen
Traversieren
Schwierig:
Vom Ende entfernen
An beliebiger Positioneinfugen
An beliebiger Positionentfernen
Element an beliebigerPosition lesen/schreiben
Einfach/Schwierig bezieht sich auf Aufwand und nichtImplementation.
Einfuhrung Verkettete Liste Baume
Doppelt verkettete Liste
Referenz nicht nur auf Nachfolger, sondern auchvorhergehendes Element
Macht Entfernen vom Ende gunstig.
Einfuhrung Verkettete Liste Baume
Beispiele und Implementation
IPython Notebooks: LinkedList.ipnb
Einfuhrung Verkettete Liste Baume
Rekursive Definition
Eine Liste L ist
die leere Liste
oder ein Element H (Head) gefolgt von einer Liste: H, L
Einfuhrung Verkettete Liste Baume
Verkettete Listen: Datenstruktur (rekursiv)
class List[Item]:
head : Item
tail : List[Item]
List(head : Item , tail : List[Item])
emptyList = List(None , None)
Gleich wie Definition mit Node - nur neue Namen:(Node → List, item → head , next → tail)
Einfuhrung Verkettete Liste Baume
Verkettete Listen: Datenstruktur (rekursiv)
class List[Item]:
head : Item
tail : List[Item]
List(head : Item , tail : List[Item])
emptyList = List(None , None)
Gleich wie Definition mit Node - nur neue Namen:(Node → List, item → head , next → tail)
Einfuhrung Verkettete Liste Baume
Verkettete Listen (rekursiv)
Naturliche, rekursive Implementation vieler Operationen
Implementation folgt Datenstruktur
def printList(list):
if (list == emptyList ):
return ""
else:
return str(list.head) + printList(list.tail)
Einfuhrung Verkettete Liste Baume
Beispiele und Implementation
IPython Notebooks: LinkedList.ipnb
Einfuhrung Verkettete Liste Baume
Liste : ADT
Liste ist nicht nur Datenstruktur, sondern auch ADT
class List[Item]:
def getFirst : Item
def getLast : Item
def size() : int
def isEmpty () : boolean
def append(item : Item)
def addFirst(item : Item)
def insert(item : Item , pos : int)
def exists(item : Item) : boolean
def iterate () -> Iterator
Viele weitere Operationen moglich. Design Entscheidung!
Beispiel aus Java: https://docs.oracle.com/javase/7/docs/api/java/util/List.html
Einfuhrung Verkettete Liste Baume
Liste : ADT
ADT erlaubt verschiedene Implementationen derselbenSchnittstelle
Beispiel aus Java
LinkedListIn Java: java.util.LinkedList sowiejava.util.ArrayList
Achtung
Verschiedene Listen haben dieselbe Schnittstelle, aber Operationenhaben nicht dieselbe Komplexitat.
Einfuhrung Verkettete Liste Baume
Baume
Einfuhrung Verkettete Liste Baume
Was ist ein Baum
Struktur um Daten hierarchisch anzuordnen.
Abbildung:http://www.ub.unibas.ch/bernoulli/index.php/Stammbaum
Einfuhrung Verkettete Liste Baume
Was ist ein Baum
Rekursive Definition: Baum
Ein Baum T der Ordnung n ist entweder der leere Baum, oderbesteht aus einem Knoten (genannt Wurzel) sowie maximal nBaumen (den Unterbaumen von T ).
Nicht rekursive Definition in Teil uber Graphen
Einfuhrung Verkettete Liste Baume
Beispiele
Eine Liste ist ein Spezialfall eines Baumes (Baum der Ordnung 1)
Einfuhrung Verkettete Liste Baume
Beispiele
Eine Liste ist ein Spezialfall eines Baumes (Baum der Ordnung 1)
Einfuhrung Verkettete Liste Baume
Terminologie
Einfuhrung Verkettete Liste Baume
Wichtigster Spezialfall: Binarbaum
Binarbaum (Binary Tree)
Ein Binarbaum T ist entweder der leere Baum, oder besteht auseinem Knoten (genannt Wurzel) sowie maximal 2 Baumen (denUnterbaumen von T ).
Binarbaume haben jedeMenge Anwendungen
Unser aktueller Fokus
Einfuhrung Verkettete Liste Baume
Wichtigster Spezialfall: Binarbaum
Binarbaum (Binary Tree)
Ein Binarbaum T ist entweder der leere Baum, oder besteht auseinem Knoten (genannt Wurzel) sowie maximal 2 Baumen (denUnterbaumen von T ).
Binarbaume haben jedeMenge Anwendungen
Unser aktueller Fokus
Einfuhrung Verkettete Liste Baume
Terminologie (2)
Voller Binarbaum: Jeder Knoten hat 0 oder 2 Kinder
Vollstandiger (oder kompletter) Binarbaum: Alle Ebenen sindvollstandig gefullt ausser evtl. die letzte Ebene wobei nurBlatter rechts fehlen durfen.
Perfekter Binarbaum: Alle internen Knoten haben genau 2Kinder und alle Blatter sind auf der gleichen Ebene
Einfuhrung Verkettete Liste Baume
Quiz
Welche der folgenden Baume sind voll, vollstandig oderperfekt?
Wie ist es mit dem leeren Baum?
Einfuhrung Verkettete Liste Baume
Hohe eines perfekten Binarbaums
Theorem
Die Hohe eines perfekten Binarbaums der Grosse N (also mit NKnoten) ist log2(N + 1)− 1.
Beweis.
Die Anzahl Knoten N eines perfekten Baumes der Hohe hsind N = 20 + 21 + . . . ,+2h = 2h+1 − 1
Auflosen nach h ergibtlog2(N + 1) = h + 1⇔ h = log2(N + 1)− 1
Einfuhrung Verkettete Liste Baume
Hohe eines vollstandigen Binarbaums
Theorem
Die Hohe eines vollstandigen Binarbaums der Grosse N isblog2(N)c
Es stimmt fur Hohe 0 (Fur N = 1 ist log2(1) = 0)
Die Hohe nimmt nur um 1 zu, wenn N so vergrossert wird,dass es eine Zweierpotenz wird.
D.h ein Knoten ist alleine auf der letzten Ebene.
Einfuhrung Verkettete Liste Baume
Datenstruktur fur Binarbaum
class BinaryTree[Item]:
item Item
left: BinaryTree[Item]
right: BinaryTree[Item]
BinaryTree(item : Item ,
left : BinaryTree[Item],
right: BinaryTree[Item]
)
emptyTree = BinaryTree(None , None , None)
Einfuhrung Verkettete Liste Baume
Traversierung
Breitenansatz (breadth-first-search). Eine Ebene nach demanderen.
Tiefenansatz (depth-first-search). Zuerst in die Tiefe, dann linksnach rechts.
Quelle:http://www.cse.unsw.edu.au/ billw/Justsearch.html
Einfuhrung Verkettete Liste Baume
Depth-first-search Traversierung
Wir unterscheiden drei Hauptarten der DFS Traversierung:
Preorder Aktueller Knoten zuerst, danach weiter traversieren
Inorder Aktueller Knoten zwischen Traversierung vonUnterbaumen
Postorder Aktueller Knoten nach Traversierung vonUnterbaumen
Einfuhrung Verkettete Liste Baume
Implementation
IPython Notebooks: Trees.ipynb
Einfuhrung Verkettete Liste Baume
ADT fur Binarbaum?
Genau wie Listen, konnten wir einen Binarbaum alsAbstrakten Datentyp definieren.
Kein naturliches API um Einfugen der Elemente zu definieren
Wo soll eingefugt werdenEinfacher Datenstruktur abhangig zu definieren.
Spater: Kompletter ADT fur Binarsuchbaum
Einfugeposition wird anhand Ordnung der Elemente bestimmt
Einfuhrung Verkettete Liste Baume
Teil ADT fur Binarbau (nicht mutierend)
Nicht mutierende Operationen konnen einfach definiertwerden.
class BinaryTree[Item]:
def item() -> Item
def left() -> BinaryTree
def right() -> BinaryTree
def depth() -> int
def isLeaf () -> bool
def iterate(order : Order) -> Iterator
Einfuhrung Verkettete Liste Baume
Implementation mittels Array (1)
Der ADT Binarbaum kann auch mittels Array implementiertwerden.
Linker Teilbaum: Index Wurzel * 2Rechter Teilbaum: Index Wurzel * 2 + 1
Quelle: Abbildung 2.26, Algorithms, Sedgewick & Wayne
Einfuhrung Verkettete Liste Baume
Implementation mittels Array (2)
Wechseln zwischen Ebenen ohne explizite Links (Kind /Elternknoten) moglich.
Speichereffizient fur vollstandigen Binarbaum
Sehr ineffizient wenn Baum zur Liste degenieriert (nur linkeoder rechte Teilbaume)
Wird beim Heap zur effizienten Implementation einerVorrangswarteschlange (priority queue) ausgenutzt! Mehr dazunachste Woche.
Einfuhrung Verkettete Liste Baume
Quiz
Ist die verkettete Liste eine Datenstruktur oder ein ADT?
Weshalb ist das Loschen des letzten Elements in einerverketteten Liste schwierig?
Konnen wir beliebige Binarbaume mittels einem Arrayimplementieren oder nur vollstandige?
Wie ist es mit Baumen beliebiger Ordnung?
Wie unterscheidet sich die Komplexitat der Operation left
des Binarbaum ADT in den verschiedenen Implementationen(Baum Datenstruktur / Array)?