1 Strutture gerarchiche di ogni tipo Cosa sono gli alberi? Alberi

(1)

Ugo de'Liguoro - Informatica 2 Alberi

Alberi

Corso di Informatica 2

Cosa sono gli alberi?

Strutture gerarchiche di ogni tipo

Generale

Colonnello1

Maggiore1,1 Maggiore1,m

Colonnellok

Maggiorek,1 Maggiorek,n

Capitano

(2)

Strutture gerarchiche di ogni tipo

Strutture dati

1.

Tipi di dato e strutture dati

1. Specifica e realizzazione 2. Rappresentazione in memoria 2.

Liste

1. L’ADT delle liste 2. Realizzazione con vettori 3. Realizzazione con puntatori 3.

Pile e code

1. L’ADT delle pile …

Definizioni

Un albero èun grafo connesso aciclico; nel caso finito può essere definito induttivamente come un insieme tale che:

• ∅ è un albero;

• se k≥ 0, T₁, …, T_ksono alberi, v un vertice, allora {v, T₁, …, T_k} è un albero

Un insieme di alberi è una foresta.

albero foresta grafo ciclico

Struttura induttiva degli alberi

albero radice

albero

(3)

Alberi con radice e foglie

•

La radice è un nodo privilegiato di un albero;

•

se l’albero è un grafo non orientato qualunque nodo può considerarsi radice;

•

se l’albero è orientato allora due casi:

1.

la radice ha solo archi in uscita (albero

sorgente)

2.

la radice ha solo archi in entrata (albero

pozzo)

•

Una foglia è un nodo da cui non esce alcun arco

Alberi sorgente, alberi pozzo

sorgente

pozzo

Parentele

d e

b c

a

f a è padre

di b e c b è figlio

di a

d è fratello di e

f è un discendente di a;

a è un avo di f

(4)

Cammini

Cammino: sequenza di archi ciascuno incidente sul vertice di quello successivo Cammino: sequenza di archi ciascuno incidente sul vertice di quello successivo

Un cammino dalla radice ad una foglia si dice

ramo

Livelli

Livello 0

Livello 1

Livello 2

Livello: insieme di vertici equidistanti dalla radice

L’altezza è la massima distanza dalla

radice di un livello non

vuoto

Alberi ordinati

Un albero è ordinato quando lo sono (linearmente) i suoi livelli Un albero è ordinato quando lo sono

(linearmente) i suoi livelli

a

b c

d

a

c b

=

d

≠

Come alberi ordinati

siamo diversi

Conta solo l’ordine, non sinistra e destra

(5)

Alberi k-ari

Io sono un albero ternario Arietà = massimo num. dei figli di

qualche nodo Arietà = massimo num. dei figli di

qualche nodo

Alberi posizionali

Un albero ordinato è posizionale quando nell’ordine dei livelli si tiene conto di ∅ (si deve quindi fissare l’arietà) Un albero ordinato è posizionale quando nell’ordine dei livelli si tiene conto di ∅ (si deve quindi fissare l’arietà)

a

b c

d

a

b c

d

≠

Una specifica

Sintassi

• Tipi: Tree, Node

• Operatori:

NewTree: void → Tree IsEmptyTree: Tree → boolean InsAsRoot: Node, Tree → Tree Root: Tree → Node

Parent: Node, Tree → Node

Leaf: Node, Tree → boolean …

(6)

Una specifica

Sintassi

• Tipi: Tree, Node

• Operatori:

…

Child: Node, Tree → Node HasSibling: Node, Tree → Boolean Sibling: Node, Tree → Node

InsTree: Node, Node, Tree, Tree → Tree DelTree: Node, Tree → Tree

Semantica degli operatori

InsAsRoot(n, T ) = T′

Pre: T = ∅

Post: T′ è l’albero il cui unico nodo è n r

InsAsRoot(r, ∅ )

A cosa servono queste

banalità?

Con qualcosa si deve pur cominciare

Semantica degli operatori

DelTree(n, T ) = T′

Pre: n è un nodo di T

Post: T′ risulta da T eliminando il sottoalbero con radice in n r

a b

c d

T

r b

DelTree(a, T )

(7)

Semantica degli operatori

InsTree(n, m, T, U ) = T′

Pre: m, n sono nodi di T, U≠ ∅

Post: T′ risulta da T inserendo U come figlio di m e 1. fratello successivo di n se n≠ m

2. primo figlio di m se n = m r

a b

c d

T

z

x v

U

r

a b

c z d

x v

InsTree(c, a, T, U )

Semantica degli operatori

InsTree(n, m, T, U ) = T′

Pre: m, n sono nodi di T, U≠ ∅

Post: T′ risulta da T inserendo U come figlio di m e 1. fratello successivo di n se n≠ m

2. primo figlio di m se n = m r

a b

c d

T

z

x v

U

r

a b

c d

z

x v

InsTree(a, a, T, U )

Semantica degli operatori

Semantica

NewTree () = ∅ (albero vuoto) Root(T) = la radice di T

Parent (n, T) = m Pre: n∈ T Post: m padre di n Child (n, T) = m Pre: n∈ T, Leaf(n, T) = false

Post: m è il primo figlio di n Sibling (n, T) = m Pre: n∈ T , HasSibling (n, T) = true

Post: m è il fratello successivo di n IsEmptyTree(T) = true se T = ∅ , false altr.

Leaf(n, T) = b Pre: n∈ T , b = true sse n è una foglia HasSibling(n, T) = b Pre: n∈ T

Post: b = true sse n ha un fratello

(8)

Realizzazioni: vettore dei padri

d e

b c

a

f

a 0 1

b 1 2

c 1 3

d 2 4

e 2 5

f 3 6 etichetta del

nodo

indice del nodo

indice del padre

Efficiente per rappresentare alberi pozzo di cardinalità (numero dei nodi)

fissata

Alberi binari: definizione induttiva

L’insieme degli alberi binari etichettati in A, BT(A), è definito induttivamente:

a)

∅ ∈ BT(A) (albero vuoto)

b) a

∈ A, l ∈ BT(A), r ∈ BT(A) ⇒

ConsTree(a, l, r) ∈ BT(A)

l r

a Si introduce la

nozione di sottoalbero sinistro e destro

Alberi binari realizzati con puntatori

info left right

r

a b

c d

T

r

a b

c d

T

(9)

Codifica binaria di alberi k-ari

a

b c d

e f g

a b

c d e

f g Nel caso di alberi non ordinati

la codifica non è univoca!

Realizzazioni: con puntatori

info child sibling

parent

a

b c d

e f g

a

b c d

e f g

La cardinalità di un albero binario

Cardinalità (B) if B = ∅ then return 0

else return 1 + Cardinalità (Left(B)) + Cardinalità (Right(B))

l r

a

Left(B) = l B

Right(B) = r

(10)

L’altezza di un albero binario

Altezza (B) // Pre: B≠ ∅

// Post: ritorna l’altezza di B return Altezza_aux (B) Altezza_aux (B)

// Post: ritorna l’altezza di B, 0 se B = ∅ if B = ∅ then return 0

else return max{Altezza_aux(Left(B), Altezza_aux(Right(B)) + 1 Si usa una funzione

ausiliaria perché il caso di base B = ∅ è essenziale alla

ricorsione

La ricorsione sugli alberi

ContaFoglie (T)

// Post: ritorna il numero delle foglie di T if T = ∅ then return 0

else if T ha un solo nodo then return 1 due casi di base else siano T₁, …, T_ki sottoalberi con radici nei

nodi figli di della radice di T return

∑

=

k

i₁ContaFoglie(Ti) Questo pseudocodice è lontano

dalla realizzazione

La ricorsione sugli alberi

ContaFoglie (T)

// Post: ritorna il numero delle foglie di T if IsEmptyTree(T) then return 0 else return Cf_aux(Root(T), T) Cf_aux (n, T)

// Pre: n∈ T ≠ ∅

// Post: ritorna il numero delle foglie del sottoalbero di T con radice in n

(11)

La ricorsione sugli alberi

Cf_aux (n, T) // Pre: n∈ T ≠ ∅

// Post: ritorna il numero delle foglie del sottoalbero di T con radice in n if Leaf(n, T) then return 1

else // n ha almeno un figlio in T m← Child(n, T) foglie← Cf_aux (m, T) while HasSibling (m, T) do

m← Sibling (m, T) foglie← foglie + Cf_aux (m, T) return foglie

Se m aveva un fratello, allora l’attuale valore di

m è un nodo di T

Visite: Depth First Search

DFS (T)

// Post: visita i nodi di T in profondità if T≠ ∅ then

visita Root(T)

siano T1, …, Tki sottoalberi con radici nei nodi figli di della radice di T for i← 1 to k do

DFS (Ti)

Visite: Depth First Search

DFS (T)

// Post: visita i nodi di T in profondità if not IsEmtyTree(T ) then

DFS_aux (Root(T), T) DFS_aux (n, T)

// Post: visita in profondità il sottoalbero di T con radice in n

(12)

Visite: Depth First Search

DFS_aux (n, T)

// Post: visita in profondità il sottoalbero di T con radice in n cominciando dalla radice

visita n

if not Leaf (n, T) then m← Child (n, T) DFS_aux (m, T) while HasSibling (m, T) do

m← Sibling(m, T) DFS_aux (m, T)

Il tipo BinTree

typedef struct tnode { T info; // etichetta struct tnode *left, *right;

// puntatori ai figli sinistro e destro } tNode;

typedef struct bintreeframe {

int card; // numero dei nodi dell’albero tNode* root; // radice dell’albero } BinTreeFrame

typedef BinTreeFrame* BinTree;

Costruttori

tNode* NewtNode (T etc, tNode* l, tNode* r) { tNode* n = new tNode;

n->info = etc;

n->left = l; n->right = r;

return n;

}

BinTree NewBinTree (void)

{ BinTree bt = new BinTreeFrame;

bt->card = 0; bt->root = NULL;

return bt;

}

(13)

Un esempio: la funzione Altezza

int Altezza (tNode* n) // Pre: n != NULL

// Post: ritorna l’altezza dell’albero con radice in n { return Altezza_aux(n); }

int Altezza_aux (tNode*)

// Post: ritorna l’altezza di tNode se != NULL, 0 altr.

{ int hl = 0, hr = 0;

if (n->left == NULL && n->right == NULL) return 0;

if (n->left != NULL) hl = Altezza_aux (n->left);

if (n->right != NULL) hr = Altezza_aux (n->right);

if (hl > hr) return hl + 1;

return hr + 1;

}

Visite in profondità

void preorder (tNode* n) { if (n != NULL) { visit(n);

preorder(n->left);

preorder(n->right);

} }

void inorder (tNode* n) { if (n != NULL) { inorder(n->left);

visit(n);

inorder(n->right);

} }

La lista dei vertici in preordine (1)

l r

a

l r

a

(14)

La lista dei vertici in preordine (2)

Node* Preorder_List (tNode* n) { if (n == NULL) return NULL;

return NewNode(n->info,

concat (Preorder_List(n->left), Preorder_List(n->right));

}

La soluzione ovvia è O(n²):

La complessità quadratica deriva dall’uso di concat nel caso in cui l’albero sia degenere sinistro.

La lista dei vertici in preordine (3)

Node* Preorder_List2 (tNode* n, Node* l) { if (n == NULL) return l;

return NewNode(n->info,

Preorder_List2(n->left, Preorder_List2(n->right,l));

}

Esiste una soluzione ottima O(n):