Alberi binari
description
Transcript of Alberi binari
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi binari
Corso di Informatica 2a.a. 2003/04Lezione 6
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Strutture gerarchiche di ogni tipo
Generale
Colonnello1
Maggiore1,1 Maggiore1,m
Colonnellok
Maggiorek,1 Maggiorek,n
Capitano
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Strutture gerarchiche di ogni tipo
Strutture dati1. Tipi di dato e strutture dati
1. Specifica e realizzazione2. Rappresentazione in memoria
2. Liste1. L’ADT delle liste2. Realizzazione con vettori3. Realizzazione con puntatori
3. Pile e code1. L’ADT delle pile …
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Definizioni
Un albero èun grafo connesso aciclico; nel caso finito può essere definito induttivamente come un insieme tale che:• è un albero;• se k 0, T1, …, Tk sono alberi, v un vertice, allora
{v, T1, …, Tk } è un albero
Un insieme di alberi è una foresta.
albero foresta grafo ciclico
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Cammini
Cammino: sequenza di archi ciascuno incidente sul vertice di quello successivo
Un cammino dalla radice ad
una foglia si dice ramo
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi ordinati
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi k-ari
Io sono un albero
ternario
Arietà = massimo num. dei figli di qualche nodo
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi posizionali
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Una specifica
Sintassi• Tipi: Tree, Node• Operatori:
NewTree: void TreeIsEmptyTree: Tree booleanInsAsRoot: Node, Tree TreeRoot: Tree NodeParent: Node, Tree NodeLeaf: Node, Tree boolean …
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Una specifica
Sintassi• Tipi: Tree, Node• Operatori:
…Child: Node, Tree NodeHasSibling: Node, Tree BooleanSibling: Node, Tree NodeInsTree: Node, Node, Tree, Tree TreeDelTree: Node, Tree Tree
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
DelTree(n, T ) = T
Pre: n è un nodo di TPost: T risulta da T eliminando il sottoalbero con radice in n
r
a b
c d
T
r
b
DelTree(a, T )
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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 m2. primo figlio di m se n = m
r
a b
c dT
z
x v
U
r
a b
c dz
x v
InsTree(c, a, T, U )
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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 m2. primo figlio di m se n = m
r
a b
c dT
z
x v
U
r
a b
c dz
x v
InsTree(a, a, T, U )
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
SemanticaNewTree () = (albero vuoto)Root(T) = la radice di TParent (n, T) = m Pre: n T Post: m padre di nChild (n, T) = m Pre: n T, Leaf(n, T) = false
Post: m è il primo figlio di nSibling (n, T) = m Pre: n T , HasSibling (n, T) = true
Post: m è il fratello successivo di nIsEmptyTree(T) = true se T = , false altr.Leaf(n, T) = b Pre: n T , b = true sse n è una fogliaHasSibling(n, T) = b Pre: n T
Post: b = true sse n ha un fratello
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Realizzazioni: vettore dei padri
d e
b c
a
f
a0
1
b1
2
c1
3
d2
4
e2
5
f3
6
etichetta del nodo
indice del nodo
indice del padre
Efficiente per rappresentare alberi pozzo di cardinalità (numero dei nodi)
fissata
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi binari realizzati con puntatori
info
left right
r
a b
c dT
r
a b
c d
T
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Codifica binaria di alberi k-ari
a
b c d
e f g
a
bc
de
fg
Nel caso di alberi non ordinati la codifica non è univoca!
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Realizzazioni: con puntatori
info
child sibling
parent
a
b c d
e f g
a
b c d
e f g
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La cardinalità di un albero binario
Cardinalità (B)if B = then return 0else return 1 + Cardinalità (Left(B)) +
Cardinalità (Right(B))
l r
a
Left(B) = l
B
Right(B) = r
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
L’altezza di un albero binario
Altezza (B)// Pre: B // Post: ritorna l’altezza di Breturn Altezza_aux (B)
Altezza_aux (B)// Post: ritorna l’altezza di B, 0 se B = if B = then return 0else 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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La ricorsione sugli alberi
ContaFoglie (T)// Post: ritorna il numero delle foglie di T
if T = then return 0else if T ha un solo nodo then return 1
due casi di base
else siano T1, …, Tk i sottoalberi con radici nei nodi figli di della radice di Treturn
k
i iT1
)(eContaFogli
Questo pseudocodice è lontano dalla realizzazione
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La ricorsione sugli alberi
ContaFoglie (T)// Post: ritorna il numero delle foglie di Tif IsEmptyTree(T) then return 0else 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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La ricorsione sugli alberi
Cf_aux (n, T)
// Pre: n T
// Post: ritorna il numero delle foglie del sottoalbero di T con radice in nif Leaf(n, T) then return 1else // 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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Visite: Depth First Search
DFS (T)// Post: visita i nodi di T in profonditàif T then
visita Root(T)
siano T1, …, Tk i sottoalberi con radici nei nodi figli di della radice di T
for i 1 to k doDFS (Ti)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Visite: Depth First SearchDFS_aux (n, T)// Post: visita in profondità il sottoalbero di T con radice in n
cominciando dalla radicevisita nif 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)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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;
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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);
}}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
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(n2):
La complessità quadratica deriva dall’uso di concat nel caso in cui l’albero sia degenere sinistro.