alberi

tipo astratto, implementazione, algoritmi

maggio 2003 ASD - Alberi 2

argomenti tipo astratto albero

definizione implementazione in Java algoritmi di visita

alberi binari implementazione di alberi binari in

Java

maggio 2003 ASD - Alberi 3

tipo di dato astratto albero insieme vuoto di nodi oppure costituito

da una radice R e da 0 o più alberi (detti sottoalberi)

la radice di ogni sottoalbero è collegata a R da un arco (orientato)

T1 T2 Tn

R

es.: radice R con n sottoalberi

maggio 2003 ASD - Alberi 4

terminologia genitore, figlio, fratello concetti intuitivi

nodo foglia se ha zero figli interno se ha almeno

un figlio

radice

foglia

nodo interno

maggio 2003 ASD - Alberi 5

terminologia/2 livello di un nodo

lunghezza (n.ro nodi) percorso radice-nodo

ramo percorso radice-foglia

altezza albero lunghezza (n.ro nodi)

ramo più lungo

altezza = 3

livello radice = 1

maggio 2003 ASD - Alberi 6

alberi?

maggio 2003 ASD - Alberi 7

esempi di alberi alberi genealogici gerarchie di ereditarietà

ad es., in Java classificazioni di specie animali organizzazione del territorio

continente, nazione, regione, provincia ecc (alcuni) organigrammi file system domini Internet

maggio 2003 ASD - Alberi 8

rappresentazione di alberi con liste collegate

R

A B

C

Elemento

Riferimento al primo figlio

Riferimento al prossimo fratello

Primo figliodi R

Fratello di A

livello di C = 3

maggio 2003 ASD - Alberi 9

operazioni sugli alberi operazioni più importanti

element(v): restituisce l’elemento memorizzato nel nodo v

root(): restituisce la radice dell’albero parent(v): restituisce il genitore del nodo v children(v): restituisce i figli di v isLeaf(v): restituisce true se v è una

foglia isRoot(v): restituisce true se v è la radice

maggio 2003 ASD - Alberi 10

operazioni sugli alberi Altre operazioni

livello di un nodo altezza dell’albero # nodi # foglie arità

max # di figli di un nodo dell’albero isEmpty

true se l’albero ha zero nodi

maggio 2003 ASD - Alberi 11

rappresentazionedei nodi in Java nodi

class TreeNode {Object element;TreeNode firstChild;TreeNode nextSibling;TreeNode parent;

}

maggio 2003 ASD - Alberi 12

tipo astratto albero in Java

public interface Tree {Object element(TreeNode v);TreeNode root();TreeNode parent(TreeNode v);ListIterator children(TreeNode v);boolean isLeaf(TreeNode v);boolean isRoot(TreeNode v);

}

maggio 2003 ASD - Alberi 13

algoritmi su alberi livello di un nodo

public int level(TreeNode v) {if(this.isRoot(v))

return 1;else

return 1 + level(this.parent(v));}

costo proporzionale all’altezza: O(n )

maggio 2003 ASD - Alberi 14

algoritmi su alberi/2 altezza di un

(sotto)albero costo

proporzionale al numero di nodi: (n )

viene esaminato ogni nodo

ciascun nodo viene esaminato una sola volta

Algorithm height(v) {if(v == null) return 0;if(isLeaf(v)) return 1;w = v.firstChild;hmax = height(w);while(w.nextSibling != null) {w = w.nextSibling;h = height(w);if(h > hmax) hmax = h;

}return 1 + hmax;

}

maggio 2003 ASD - Alberi 15

algoritmi su alberi/3 visita (o attraversamento) di un

albero in profondità (depth-first search, a

scandaglio): DFS vengono visitati i rami, uno dopo l’altro tre varianti

in ampiezza (breadth-first search, a ventaglio): BFS

a livelli, partendo dalla radice

maggio 2003 ASD - Alberi 16

visite in profondità/preordine in preordine (preorder, o ordine anticipato)

dato un nodo v visita v visita i sotto-alberi aventi come radice i figli di v, da sinistra

verso destravoid treePreorder(root) {if(root == null) return;<visita root>r = root.firstChildwhile (r != null) {

treePreorder(r);r = r.nextSibling;

}}

maggio 2003 ASD - Alberi 17

visite in profondità/inordine in ordine simmetrico (inorder)

dato un nodo v con k sotto-alberi visita il primo sotto-albero (radice v.firstChild) visita v visita gli altri k-1 sotto-alberi

void treeInorder(root) {if(root == null) return;r = root.firstChild;treeInorder(r);<visita root>r = r.nextSibling;

while (r != null) {treeInorder(r);r = r.nextSibling;

}}

maggio 2003 ASD - Alberi 18

visite in profondità/postordine in postordine (postorder, o ordine posticipato)

dato un nodo v visita i sotto-alberi aventi come radice i figli di v, da

sinistra verso destra visita v

void treePostorder(root) {if(root == null) return;r = root.firstChildwhile (r != null) {

treePostorder(r);r = r.nextSibling;

}<visita root>

}

maggio 2003 ASD - Alberi 19

visite in profondità

7

1 3 6

2 4 5

2

1 4 6

3 5 7

1

2 3 5

4 6 7

preordine inordine postordine

maggio 2003 ASD - Alberi 20

visita in ampiezza breadth-first search (BFS), usa una coda

dato un nodo vvoid bfs(v) {

if(v == null) return;queue.enqueue(v);while (!queue.isEmpty()) {

v = queue.dequeue();v.visit();w = v.firstChild;while(w != null) {

queue.enqueue(w);w = w.nextSibling;

}}

maggio 2003 ASD - Alberi 21

visita in ampiezza

1

2 3 4

5 6 7

BFS

maggio 2003 ASD - Alberi 22

alberi binari un albero si dice binario se ogni nodo

può avere al più 2 figli la rappresentazione si semplifica

public class BinaryNode {protected Object element;protected BinaryNode leftChild;protected BinaryNode rightChild;

}

impl

emen

tazion

e m

inim

a

maggio 2003 ASD - Alberi 23

ADT albero binario in Javapublic interface BinaryTree {Object element(BinaryNode v);BinaryNode root();BinaryNode parent(BinaryNode v);BinaryNode leftChild(BinaryNode v);BinaryNode rightChild(BinaryNode v);boolean isLeaf(BinaryNode v);boolean isRoot(BinaryNode v);

}

maggio 2003 ASD - Alberi 24

alberi binari/visita in preordine

void treePreorder(BinaryNode v) {if(v == null) return;<visita v>treePreorder(T.leftChild(v));treePreorder(T.rightChild(v));

}

maggio 2003 ASD - Alberi 25

alberi binari/visita inordine

void treeInorder(BinaryNode v) {if(v == null) return;treeInorder(T.leftChild(v));<visita v>treeInorder(T.rightChild(v));

}

maggio 2003 ASD - Alberi 26

alberi binari/visita in postordine

void treePostorder(BinaryNode v) {if(v == null) return;

treePostorder(T.leftChild(v));treePostorder(T.rightChild(v));<visita v>

}

maggio 2003 ASD - Alberi 27

alberi binari/visita in ampiezzavoid bfs(v) {queue.enqueue(v);while (!queue.isEmpty()) {p = (BSTNode) queue.dequeue();p.visit();if (p.leftChild != null)queue.enqueue(p.leftChild);

if (p.rightChild != null)queue.enqueue(p.rightChild);

}}

maggio 2003 ASD - Alberi 28

strutture dati per alberi binari vettori rappresentazioni collegate esercizi:

implementare l’interfaccia BinaryTree usando una rappresentazione collegata

scrivere un programma che legga gli elementi (stringhe) di un albero binario e li stampi effettuando una visita in preordine

maggio 2003 ASD - Alberi 29

uso di vettori ogni nodo v è memorizzato in posizione p(v)

se v è la radice allora p(v)=1 (indice 0 in Java, C, C++)

se v è il figlio sinistro di u allora p(v)=2p(u) se v è il figlio destro di u allora

p(v)=2p(u)+1

1

2

6 7

3

4

1234-67-

maggio 2003 ASD - Alberi 30

uso di vettori/2 implementazione statica: è

necessaria una stima del numero massimo di nodi dell’albero può portare a spreco di risorse nel caso peggiore, un albero con n

nodi richiede un vettore con 2n-1 elementi (se l’albero degenera in una catena "destra")

maggio 2003 ASD - Alberi 31

uso di vettori/3 in Java: si possono usare le classi Vector

(sincronizzata) o ArrayList (non sincronizzata) Vector e ArrayList gestiscono anche il

ridimensionamento quando il numero di elementi cresce oltre la capacità corrente

ciò porta a ritardi (per gestire l’allocazione di nuova memoria)

esercizio: scrivere una classe che implementi l’interfaccia BinaryTree usando ArrayList o Vector

maggio 2003 ASD - Alberi 32

rappresentazione collegata

public class LinkedBinaryTree implements BinaryTree {private BinaryNode root; /* Rif. alla radice*/private int size; public LinkedBinaryTree() {

root = new BinaryTreeNode(null, null, null);size = 0;

}/* Altri metodi */

} /* Fine della classe */