Algorithmen und Datenstrukturen - unibas.ch...Einf uhrung Verkettete Liste B aume Wissenschaftler des Tages Herbert Simon (Okonom) Nobelpreistr ager und Gewinner des Turing Awards

Algorithmen und DatenstrukturenB3. Verkettete Listen und Baume

Marcel Luthi and Gabriele Roger

Universitat Basel

22. Marz 2018

Einfuhrung Verkettete Liste Baume

Einfuhrung


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.


Wiederholung: Multimengen, Warteschlangen und Stapel

Multimenge

Ungeordnet

Stapel

LIFO

Warteschlange

FIFO


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).


Verkettete Liste


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.


Listen

Eine Liste ist eine geordnete Kollektion von n Elementen(n ∈ N0)

Array: Ordnung kommt von Anordnung in Speicher


Listen

Wie kann man Elemente ordnen die verteilt im Speicher sind?


Listen

Wie kann man Elemente ordnen die verteilt im Speicher sind?


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


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


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))


Einfugen am Anfang


Einfugen am Anfang


Einfugen am Anfang


Einfugen am Ende


Einfugen am Ende


Einfugen am Ende


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.


Doppelt verkettete Liste

Referenz nicht nur auf Nachfolger, sondern auchvorhergehendes Element

Macht Entfernen vom Ende gunstig.


Beispiele und Implementation

IPython Notebooks: LinkedList.ipnb


Rekursive Definition

Eine Liste L ist

die leere Liste

oder ein Element H (Head) gefolgt von einer Liste: H, L


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)


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)


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)


Beispiele und Implementation

IPython Notebooks: LinkedList.ipnb


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

https://docs.oracle.com/javase/7/docs/api/java/util/List.html

https://docs.oracle.com/javase/7/docs/api/java/util/List.html


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.


Baume


Was ist ein Baum

Struktur um Daten hierarchisch anzuordnen.

Abbildung:http://www.ub.unibas.ch/bernoulli/index.php/Stammbaum


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


Beispiele

Eine Liste ist ein Spezialfall eines Baumes (Baum der Ordnung 1)


Beispiele

Eine Liste ist ein Spezialfall eines Baumes (Baum der Ordnung 1)


Terminologie


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


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


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


Quiz

Welche der folgenden Baume sind voll, vollstandig oderperfekt?

Wie ist es mit dem leeren Baum?


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


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.


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)


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


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


Implementation

IPython Notebooks: Trees.ipynb


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


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


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


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.


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)?

Documents

Algorithmen und Datenstrukturen - unibas.ch...Einf uhrung Verkettete Liste B aume Wissenschaftler des Tages Herbert Simon (Okonom) Nobelpreistr ager und Gewinner des Turing Awards