Struttura dati ad Albero

(1)

Unità Didattica

Struttura dati ad Albero

Daniele Contarino

Didattica di Algoritmi e Programmazione Laboratorio di Didattica di Programmazione

Percorso Abilitante Speciale A.A. 2013/14

(2)

SDA - Alberi 2 di 56 Daniele Contarino

Didattica: prerequisiti e finalità

Introduzione

Alberi n-ari e alberi binari

Binary Search Tree

Esercizi di laboratorio

Indice degli argomenti

(3)

Target: alunni della classe 4° A Informatica

Prerequisiti:

• Conoscenza dei fondamenti dei linguaggi di programmazione

• Conoscenza della programmazione Object-Oriented (ove è necessaria)

• Conoscenza delle strutture dati List, Stack e Queque.

• Rudimenti di complessità temporale

Unità didattica

(4)

Tempi di realizzazione Unità didattica

Argomenti Ore Metodologia Strumenti

Introduzione e ricollegamento con gli argomenti precedenti

1 Brainstorming

Discussione partecipata

Lavagna / LIM I tipi di alberi n-ari e binari 2 Lezione Frontale Lavagna / LIM Libro di testo Alberi Binari di Ricerca (BST) 3 Lezione Frontale

Esercitazioni alla lavagna e al computer

Lavagna / LIM

Laboratorio multimediale Libro di testo

Analisi di complessità 2 Lezione Frontale Lavagna / LIM

Libro di testo Tecniche di bilanciamento 2 Lezione Frontale

Esercitazioni alla lavagna e al computer

Lavagna / LIM

Laboratorio multimediale Esercitazione laboratoriale 3 Peer-Tutoring

Discussione partecipata

Laboratorio multimediale Verifica ed eventuale recupero 2 Test cartaceo

Esercizio di laboratorio

Laboratorio multimediale

TOTALE 15

(5)

Obiettivi specifici

Conoscenze Abilità / Capacità

Struttura intrinseca del albero n-ario e binario

Implementazione della SDA «Albero» e dei sui algoritmi fondamentali

Conoscenza dei algoritmi di inserimento ed eliminazione dell'Albero

Valutazione della complessità computazione dell'Albero Conoscenza dei algoritmi di visita e di

ricerca dell'Albero

Individuare l’esistenza della SDA «Albero»

nelle standard library fornite dai vari linguaggi di programmazione

Confronto con gli altri linguaggi di programmazione

Best pratices

(6)

 Interdisciplinarietà

Complementi di Matematica

 Competenze (DM 139/07)

 Risultati dell’apprendimento

 Usare al meglio la SDA ‘Albero’

 Conoscere la complessità computazionale del SDA ‘Albero’

 Progettare programmi che prevedono l’uso del BST

Ulteriori indicatori

Professionali Indirizzo informatico

Assi culturali (all. 1) scientifico/tecnologico (Competenza n. 3) chiave di cittadinanza (all. 2) Progettare

(7)

 Didattica: prerequisiti e finalità

Introduzione

Alberi n-ari e alberi binari

Binary Search Tree

Esercizi di laboratorio

Indice degli argomenti

(8)

Strutture dati fondamentali

Introduzione

(9)

L’albero è la

migliore struttura per rappresentare al meglio alcuni modelli di vita reale

Alberi – Perché usarli?

Albero

genealogico

Directory del

Filesystem

(10)

 Didattica: prerequisiti e finalità

 Introduzione

Alberi n-ari e alberi binari

Binary Search Tree

Esercizi di laboratorio

Indice degli argomenti

(11)

Foglia

La struttura dell’albero n-ario

Radice

Padre

Figlio

Zio Fratello

Dato Puntatori

Nodo

(12)

L’albero binario è un albero dove ogni nodo ammette al massimo due figli.

È la struttura dati ad Albero più comune, per i motivi che verranno illustrati in seguito

Albero binario

(13)

Albero Binario

Visita In-order

(14)

Albero Binario

Visita In-order

(15)

Albero Binario

Visita In-order

(16)

Albero Binario

Visita In-order

(17)

Albero Binario

Visita In-order

(18)

Albero Binario

Visita In-order

(19)

Albero Binario

Visita In-order

(20)

Albero Binario

Visita In-order

(21)

Albero Binario

Visita Post-order

(22)

Albero Binario

Visita Post-order

(23)

Albero Binario

Visita Post-order

(24)

Albero Binario

Visita Post-order

(25)

Albero Binario

Visita Post-order

(26)

Albero Binario

Visita Post-order

(27)

Albero Binario

Visita Post-order

(28)

Albero Binario

Visita Post-order

(29)

Albero Binario

Visita Pre-order

(30)

Albero Binario

Visita Pre-order

(31)

Albero Binario

Visita Pre-order

(32)

Albero Binario

Visita Pre-order

(33)

Albero Binario

Visita Pre-order

(34)

Albero Binario

Visita Pre-order

(35)

Albero Binario

Visita Pre-order

(36)

Albero Binario

Visita Pre-order

(37)

 Didattica: prerequisiti e finalità

 Introduzione

 Alberi n-ari e alberi binari

Binary Search Tree

Esercizi di laboratorio

Indice degli argomenti

(38)

più piccolo

Albero Binario di Ricerca

In un albero binario di ricerca - Binary Search Tree (BST) i nodi figli sono

disposti in maniera ordinata rispetto al valore del nodo

padre

più grande

(39)

Inserimento

Albero Binario di Ricerca

(40)

Inserimento

Albero Binario di Ricerca

(41)

Inserimento

Albero Binario di Ricerca

(42)

Inserimento

Albero Binario di Ricerca

(43)

Albero Binario di Ricerca

Ricerca

Cerca il nodo con

il valore 12

(44)

Albero Binario di Ricerca

Ricerca

Cerca il nodo con

il valore 12

(45)

Albero Binario di Ricerca

Ricerca

Cerca il nodo con

il valore 12

(46)

Albero Binario di Ricerca

Ricerca

Cerca il nodo con

il valore 12

(47)

Complessità computazionale

Albero Binario di Ricerca

h=4

# max di nodi= 15

# passo =1

(48)

Complessità computazionale

Albero Binario di Ricerca

h=4

# max di nodi= 15

# passo = 2

(49)

Complessità computazionale

Albero Binario di Ricerca

h=4

# max di nodi= 15

# passo = 3

(50)

Complessità computazionale

Albero Binario di Ricerca

h=4

# max di nodi= 15

# passo = 4

(51)

Complessità computazionale

Albero Binario di Ricerca

h=log

₂

n

# passi = O(log

₂

n)

# max di nodi= 2

^h

-1

(52)

Caso Peggiore – Albero sbilanciato

Albero Binario di Ricerca

h=n

# passi = O(n)

(53)

Tecniche di bilanciamento

Albero Binario di Ricerca

 Alberi Splay

 Alberi AVL

 Albero Rosso-Nero (Milanista)

(54)

 Didattica: prerequisiti e finalità

 Introduzione

 Alberi n-ari e alberi binari

 Binary Search Tree

Esercizi di laboratorio

Indice degli argomenti

(55)

 Sviluppo BST in C99 (procedurale)

 Sviluppo BST in Java (Object-Oriented)

Esercitazione di laboratorio

(56)