Algorithmen und Datenstrukturen - unibas.ch...Einf uhrung Verkettete Liste B aume Wissenschaftler...

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

Warteschlange

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

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

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.

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

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.

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

Algorithmen und Datenstrukturen - unibas.ch...Einf uhrung Verkettete Liste B aume Wissenschaftler...

Documents

Mit Themen Gäste gewinnen Die Fortsetzung der ... · Rad Aktive Best Ager Städtereise Natur Wandern Rad Boden-ständige Best Ager Wandern Erwachsene Singles Städtereise Events,

Tabor: KI & Sprachtechnologien Reise um die KI Turing-Spiel (Wer ist der Junge?) Turing-Test (Wer ist der Computer?) KI-Systeme simulieren künstl. Intelligenz

PRJ 2007/1 Stefan Dissmann Verkettete datenstruktur: Liste Problem: Liste, die eine beliebige Zahl von Elementen verwaltet Operationen: Erzeugen, Anfügen,

Das große Geschäft mit der Alterung /Vergreisung - „Best-Ager“ - „Golden-Ager“ Heidelberger Investoren Vortrag am 4.11.2015, 19.30 Uhr im NH- Hotel, Heidelberg,Bergheimerstrasse

SCHRIFTFÜHRER/IN Carmen Ager, UTV-Schriftführerin

Aktivreisen fuer Best Ager - Erlebnisreisen 50+

Tagesaktuelle Nachrichten sind auf ... · NVIDIA Turing Propels VR Toward Full Immersion NVIDIA’s new Turing GPUs are poised to take VR a big step closer to that level. Announced

W&V Best Ager Schwerpunkt 14/2013

On Sets Turing Reducible - Ulm · 2012-08-14 · On Sets Turing Reducible to P-Selective Sets Hans-JörgBurtschick TU -Berlin, Fachbereich Informatik Franklinstr. 28/29 D-10587Berlin

Zielgruppe 50+ : Best Ager Reisen und Reiseverhalten

03 - Dry Ager · Der DRY AGER Fleischreifeschrank für Privat und Gewerbe. 08 Das Produkt Unsere Mission: Einen bezahlbaren Vollreife Profischrank zu entwickeln, der genauso gut aussieht

2 Turing-Maschinen

Zukunftsmarkt Best Ager - Trends & Handlungsempfehlungen

Turing-Maschine als Akzeptor. Gliederung 1. Alan Turing 2. Nachteil Keller-Automat 3. Turing Maschine 4. Aufbau Turing-Maschine 5. Arbeitsweise Turing-Maschine

Best Ager - Angebote für Mitarbeiterinnen und Mitarbeiter mit ......Best Ager übernehmen sowohl im Berufs- als auch im Privatleben Verantwortung: Sei es im Rahmen an- spruchsvoller

Theorie der Informatik - Turing-Berechenbarkeitai.cs.unibas.ch/_files/teaching/fs14/theo/slides/theo12.pdf · Berechnungen Wiederholung: Turingmaschinen Turing-berechenbare Funktionen

Best Ager im Spielzeughandel

Dynamisches Array als "verkettete Liste". Ein Vergleich

Imc131 ager

Best Ager und die Medien