Appunti di Dati e Algoritmi 1

ABCDEF.

- Dire quali delle seguenti sequenze pu`o rappresentare la visita in postorder dello stesso

albero (motivando la risposta): BAFECD, CDBFEA, CDAEFB.

- Disegnare l’albero compatibile con le due sequenze di preorder e postorder.

Es. Si supponga di calcolare l’altezza di un albero T di n nodi invocando l’algoritmo depth (T , v) da

ciascuna foglia v di T e restituendo come altezza la massima profondit`a ottenuta.

Dimostrare che tale strategia ha una complessit`a al caso pessimo Ω(n ).

2

Es. Sia T un albero. Dati due nodi v, w ∈ T si definisce il Lowest Common Ancestor di v e w (LCA(v,

w)) come l’antenato comune più profondo.

Progettare un algoritmo efficiente per trovare LCA(v, w), analizzandone la complessità.

Albero binario

Un albero binario T è un albero ordinato tale che:

- ogni nodo interno ha ≤ 2 figli

- ogni nodo non radice è etichettato come figlio sinistro (sx) o destro (dx) di suo padre

- il figlio sx viene prima del figlio dx nell’ordinamento

N.B.: A meno di casi particolari, se c’è un solo figlio questo si considera essere il figlio sx.

T è il sottoalbero sinistro di u, con radice u.sx; similmente T .

sx dx

Un albero binario proprio è t. c. ogni nodo interno ha esattamente 2 figli.

Interfaccia

public interface BinaryTree<E> extends Tree<E> {

/** Returns the Position of p’s left child (or null if no child exists) */

Position<E> left(Position<E> p);

/** Returns the Position of p’s right child (or null if no child exists) */

Position<E> right(Position<E> p);

/** Returns the Position of p’s sibling (or null if no sibling exists) */

Position<E> sibling(Position<E> p);

/** Returns true if p has a left child */

boolean hasLeft(Position<E> p);

/** Returns true if p has a right child */

boolean hasRight(Position<E> p);

} - 36 -

Proprietà di un albero binario proprio T non vuoto

n numero di nodi in T

m numero di foglie in T

n – m numero di nodi interni in T

h altezza di T

1. m = n – m + 1

2. h + 1 ≤ m ≤ 2

h

3. h ≤ n – m ≤ 2 – 1

h

4. 2h + 1 ≤ n ≤ 2 – 1

h+1

5. log (n + 1) – 1 ≤ h ≤ (n – 1)/2

2

Oss. 3, 4 e 5 sono corollari di 1 e 2.

Dimostrazione di 1.

m = n – m + 1.

Per induzione su h ≥ 0. Fisso k = 0, h = 0.

0

Il caso base è h = 0. Dunque, se l’altezza è 0, c’è solo un nodo (quello radice) che è anche foglia.

Questo significa m = n = 1 che soddisfa la proprietà.

Passo induttivo: fisso un h ≥ 0 e l’ipotesi è che la proprietà valga ∀ T di altezza 0 ≤ h’ ≤ h.

Considero ora un T di altezza h + 1 ≥ 1. Posto m = numero foglie in T (i = 1, 2), n = numero nodi

i i i

in T (i = 1, 2), dove T e T sono i due sottoalberi.

i 1 2

Dunque m = m + m , e n = n + n + 1 (1 = radice).

1 2 1 2

Seguendo l’ipotesi induttiva, m = m + m = n – m + 1 + n – m + 1 = n – m + 1.

1 2 1 1 2 2

Dimostrazione di 2.

h + 1 ≤ m ≤ 2 , cioè m ≤ 2 e m ≥ h + 1.

h h

Dimostro m ≤ 2 .

h

Per induzione su h ≥ 0. Fisso k = 0, h = 0.

0

Il caso base è h = 0. In questo caso necessariamente m = 1, che come nella precedente

affermazione è effettivamente dimostrata essendoci solo la radice.

Passo induttivo: fisso un h ≥ 0 e l’ipotesi è ancora che la proprietà valga ∀ T di altezza 0 ≤ h’ ≤ h.

Considero ora un T di altezza h + 1 ≥ 1, e pongo m = numero foglie in T (i = 1, 2).

i i

Osservo come prima che m = m + m .

1 2

Seguendo l’ipotesi induttiva, m = m + m ≤ 2 + 2 ≤ 2 × 2 = 2 .

h1 h2 h h+1

1 2

Es. Dimostrare m ≥ h + 1.

Oss. Un albero binario proprio ha altezza h = Ω(log m). E se non è proprio?

Se si ammettono operatori unari (-x, sqrt x…) l’albero non è più proprio.

Alberi binari propri estremi - 37 -

Inorder: visite di alberi binari

Oltre alle visite in preorder e postorder, per gli alberi binari si definisce anche la visita inorder,

basata sulla regola: prima il figlio sx, poi il padre, poi il figlio dx

Algoritmo inorder(T, v)

Input: T, v ∈ T

Output: visita inorder di T .

v

1 if T.hasLeft(v) then inorder(T,T.left(v));

2 visita v;

3 if T.hasRight(v) then inorder(T,T.right(v));

Oss. La prima chiamata è inorder(T,T.root());

La complessità è O(n + ∑ t ) dove n = # nodi, t = tempo per visitare il nodo u.

u u

Importante applicazione: negli Alberi Binari di Ricerca serve per elencare i contenuti dei nodi

in ordine crescente.

Es. Il seguente albero ha una sequenza inorder “2 3 4 5 6 7 8”:

Parse Tree

Una espressione fully parenthesized in notazione infissa è una costante o variabile a, oppure

(E Op E )

1 2

dove E , E sono espressioni fully parenthesized in notazione infissa e Op è un operatore binario.

1 2

Es. ∗

((15 + x) (7 − (9 ÷ 3)))

Il Parse Tree T associato a una espressione FPNI E è un albero binario proprio in cui i nodi foglia

contengono le costanti/variabili di E, e i nodi interni contengono gli operatori di E, tale che:

- Se E = a, allora T è costituito da un’unica foglia contenente la costante/variabile a;

- Se E = (E Op E ), la radice di T contiene Op e ha come sottoalbero sx (e rispettivamente dx) il

1 2

Parse Tree associato a E (e rispettivamente a E ).

1 2

Es. ∗

((15 + x) (7 − (9 ÷ 3)))

*

/ \

+ -

/ \ / \

15 x 7 ÷

/ \

9 3

Oss. Le parentesi sono implicitamente rappresentate dalla struttura dell’albero.

- 38 -

Valutazione dell’espressione

Algoritmo evaluateExpression(T, v)

Input: Parse Tree T di E, v ∈ T

Output: valore dell’espressione associata al sottoalbero T .

v

1 if T.isInternal(v) then

2 op ← v.getElement();

3 x ← evaluateExpression(T,T.left(v));

4 y ← evaluateExpression(T,T.right(v));

5 return x op y;

6 else return v.getElement();

Oss. La prima chiamata è evaluateExpression(T,T.root());

La complessità è O(n) dove n = # nodi.

La visita è in postorder.

Infix: espressione a partire dall’albero

Algoritmo infix(T, v)

Input: Parse Tree T, v ∈ T

Output: espressione E rappresentata da T .

v v

1 if T.isInternal(v) then return v.getElement()

2 else return ’(’+infix(T,T.left(v))+v.getElement()+infix(T,T.right(v))+’)’;

Oss. La complessità è O(n) dove n = # nodi.

Notazione postfissa

Una espressione in notazione postfissa è una costante o variabile a, oppure

E E Op

1 2

dove E , E sono espressioni in notazione postfissa e Op è un operatore binario.

1 2

Es. era l’esempio per la not. infissa; leggendo in postorder il

∗

((15 + x) (7 − (9 ÷ 3)))

parse tree associato si ottiene la corrispondente espressione in notazione postfissa

E = 15 x + 7 9 3 ÷ − ∗

CSt. Decision tree.

Machine Learning: Area dell’informatica che si occupa dello sviluppo di algoritmi e modelli per

analizzare dati allo scopo di scoprire nuova informazione e fare previsioni, a supporto di

processi decisionali.

Supervised Learning: si impara da dati storici per

fare previsioni future. I dati da trattare sono record

caratterizzati da un insieme di feature (o attributi) e

una classe. Il problema della classification consiste

nell’analizzare un training set di record classificati

per trovare un modello che predica una classe a

partire dalle feature. Il modello è poi applicato

successivamente per assegnare una classe a nuovi

record non classificati.

I Decision tree sono tra i modelli più utilizzati e

importanti nell’ambito del machine learning.

Forniscono buona accuratezza, sono semplici da

derivare, e sono descrittivi. Inoltre possono essere

utilizzati in ensemble. - 39 -

Alberi binari in Java

L’implementazione utilizza una struttura linkata: un

nodo contiene elemento, parent e 2x child.

Interfacce: Tree<E>, BinaryTree<E>

Cl. astratte: AbstractTree<E>, AbstractBinaryTree<E>

Classi: LinkedBinaryTree<E>, Node<E> (nested)

Interfaccia Tree

public interface Tree<E> {

public int size();

public int isEmpty ();

public Position<E> root();

public Position<E> parent(Position<E> p);

public Iterable <Position<E>> children(Position<E> p);

public int numChildren (Position<E> p);

boolean isExternal (Position<E> p);

boolean isInternal (Position<E> p);

boolean isRoot (Position<E> p);

public Iterator<E> iterator();

public Iterable <Position<E>> positions();

}

Interfaccia BinaryTree

public interface BinaryTree <E> extends Tree<E> {

public Position<E> left(Position<E> p);

public Position<E> right(Position<E> p);

public Position<E> sibling(Position<E> p);

}

Classe astratta AbstractBinaryTree

public abstract class AbstractBinaryTree<E> extends AbstractTree <E> implements

BinaryTree <E> {

public Position<E> sibling(Position<E> p){...}

public Position<E> numChildren(Position<E> p){...}

public Iterable<Position<E>> Children(Position<E> p){...}

/** Adds positions to snapshot based on inorder traversal */

private void inorderSubtree(Position<E> p, List<Position<E>> snapshot) {

if (left(p) != null) inorderSubtree(left(p), snapshot);

snapshot.add(p);

if (right(p) != null) inorderSubtree(right(p), snapshot);

}

/** Returns iterable collections with positions (inorder) */

public Iterable<Position<E>> inorder() {

List<Position<E>> snapshot = new ArrayList<>();

if (!isEmpty())inorderSubtree(root(), snapshot);

return snapshot;

}

public Iterable<Position<E>> positions() {return inorder();

} - 40 -

Classe LinkedBinaryTree

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

protected static class Node<E> implements Position<E> {...}

/** instance variables */

protected Node<E> root = null;

protected int size = 0;

/** methods */

public int size() {...}

public Position<E> root(){...}

public Position<E> parent(Position<E> p){...}

public Position<E> left(Position<E> p){...}

public Position<E> right(Position<E> p){...}

(...)

}

Implementazione di iterator()

Il metodo iterator() (dall’interfaccia Tree)