Modello dati ALBERO
Albero: insieme di punti chiamati NODI e linee
chiamate EDGES
EDGE: linea che unisce due nodi distinti
Radice (root): in una albero esiste un nodo distinto
chiamato radice (disegnato in cima)
Es. Albero con sette nodi n1, n2, n3, n4, n5, n6, n7
la radice è n1
n1
n2
n3
n4
n5
n6
n7
Modello dati ALBERO
Padre/figlio: ogni nodo c (tranne la radice) è
connesso mediante una linea ad un nodo p,
chiamato il padre di c; c è detto figlio di p.
n1
n2
n3
n4
n5
n6
n7
Es.
n1 padre di n2, n4, n5 / n2, n4, n5 figli di n1
n2 “
n3
/ n3
figlio di n2
n5
n6, n7
/ n6, n7
figli di n5
Modello dati ALBERO
Padre/figlio: ogni nodo c (tranne la radice) è
connesso mediante una linea ad un nodo p,
chiamato il padre di c; c è detto figlio di p.
n1
n2
n3
n4
n5
n6
n7
Es.
n1 padre di n2, n4, n5 / n2, n4, n5 figli di n1
n2 “
n3
/ n3
figlio di n2
n5
n6, n7
/ n6, n7
figli di n5
Albero è connesso: per ogni nodo n (tranne la radice) se
ci spostiamo da n al padre di n,
poi dal padre di n al padre del padre di n, …,
arriviamo alla radice.
Es. n3  padre di n3=n2  padre di n2=n1=radice
Definizione ricorsiva di ALBERO
Base: un singolo nodo n è un albero (con radice n)
Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia
in uno solo degli alberi. Sia r un nuovo nodo (non in
T1,…,Tk). Costruiamo un nuovo albero T come segue
1. La radice di T è r
2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (che
diventano figli di r in T)
c1
T1
r
ck
…
Tk

T=
c1
T1
…
ck
Tk
Definizione ricorsiva di ALBERO
Base: un singolo nodo n è un albero (con radice n)
Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in un solo
albero. Sia r un nuovo nodo. Costruiamo il nuovo albero T
1. La radice di T è r
2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (figli di r in T)
Es. n3
n2
albero 
n3
è albero
Definizione ricorsiva di ALBERO
Base: un singolo nodo n è un albero (con radice n)
Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in un solo
albero. Sia r un nuovo nodo. Costruiamo il nuovo albero T
1. La radice di T è r
2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (figli di r in T)
Es. n3
n2
albero 
è albero
n3
n6
n7
alberi 
n6
n5
è albero
n7
Definizione ricorsiva di ALBERO
Base: un singolo nodo n è un albero (con radice n)
Passo:Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck,rispettivamente, tali che ogni nodo compaia in un solo
albero. Sia r un nuovo nodo. Costruiamo il nuovo albero T
1. La radice di T è r
2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (figli di r in T)
Es. n3
n2
albero 
è albero
n3
n6
n7
n5
alberi 
n6
n2
n3
n4
n5
n6
è albero
n7
n1
alberi 
n7
n3
n2
n4
è albero
n5
n6
n7
Definizioni su ALBERI è
Dato T con radice r
m1,…mk: è un cammino (di lunghezza k-1) in T se
m1 è padre di m2, m2 è padre di m3,…, mk-1 padre di mk.
un solo nodo è un cammino di lunghezza 0 (k=1).
n1
n2
n3
n4
n5
n6
n7
Definizioni su ALBERI è
Dato T con radice r
m1,…mk: è un cammino (di lunghezza k-1) in T se
m1 è padre di m2, m2 è padre di m3,…, mk-1 padre di mk.
un solo nodo è un cammino di lunghezza 0 (k=1).
Predecessore: m è predecessore di m’ se esiste un cammino
da m a m’ in T
Discendente: m’ è discendente di m se m è predecessore di
m’.
Fratelli: m e m’ so dicono fratelli se hanno lo stesso padre.
n1
n2
n3
n4
n5
n6
n7
Definizioni su ALBERI è
Sottoalbero con radice n: albero formato dal nodo n con
tutti i suoi discendenti
n1
n2
n3
n4
n5
n6
n7
Definizioni su ALBERI è
Sottoalbero con radice n: albero formato dal nodo n con
tutti i suoi discendenti
Foglia: nodo che non ha figli
Nodo interno: nodo che ha almeno un figlio
n1
n2
n3
n4
n5
n6
n7
Definizioni su ALBERI è
Altezza di un albero T: lunghezza del più lungo cammino
dalla radice di T ad una foglia di T.
Livello del nodo n: lunghezza del cammino dalla radice ad n.
Fratelli: m e m’ so dicono fratelli se hanno lo stesso padre.
n1
n2
n3
n4
n5
n6
n7
Definizioni su ALBERI è
Alberi ordinati: possiamo assegnare un ordine da sinistra a
destra ai figli di un nodo, inoltre
se m ed n sono fratelli ed m è a destra di n allora
ogni discendente di m è a destra di ogni discendente di n
Quindi per ogni coppia di nodi vale la relazione “essere a
destra”.
n1
n2
n3
n4
n5
n6
n7
Struttura dati per ALBERI
Dipende dalle operazioni che si devono effettuare
Generalmente nodi = struct
elemento
puntatori
Array di puntatori
info
p0 …
pb-1
Array di puntatori
ai figli del nodo
b= branching factor
= max numero figli per nodo
Se nodo ha < b figli allora alcuni puntatori
sono NULL
Typedef struct NODE *pNODE
struct NODE{
int info
“array di b puntatori pNODE’’}
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rappresentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rappresentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
e -
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rapperesentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
- h -
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rapperesentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
- h e +
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rapperesentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
- h e +
r s+
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rapperesentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
- h e +
i -
r -
s+
s+
Struttura dati per ALBERI
TRIE: Serve per memorizzare stringhe di caratteri.
1. Ogni nodo ha associata una lettera
2. La stringa rapperesentata dal nodo è la sequenza di lettere sul
cammino dalla radice al nodo
3. Un simbolo (+/-) dice se la stringa rappresentata dal nodo fa
parte di quelle da memorizzare.
Es. Vogliamo memorizzare {he, hers, his, she} (array di 26 elementi)
- h -
s -
e +
i -
h -
r -
s+
e+
s+
Struttura dati per ALBERI
e h -
a b … h
i -
h -
r -
s+
e+
s+
s
… z
e -
s -
e +
…
e
i
h
h -
s r
e +
s
e
i -
h -
s +
e +
s
r -
s +
ALBERI Sinistra-Destra
Per evitare spreco di memoria:
lista a puntatori per rappresentare i figli di un nodo
Typedef struct NODE *pNODE
struct NODE{
infotype info;
pNODE leftchild, rightsibling}
NODE
infotype leftmostchild
rightsibling
ALBERI Sinistra-Destra
NODE
infotype leftmostchild
rightsibling
a
b
e
c
d
g
f
a
b
e
c
/
/
/
/
d
f
/
/
g
/
/
Struttura dati per ALBERI
e h e +
i -
h -
r -
s+
e+
s+
e -
s h -
e +
r -
s + / /
/
/
s -
/
i -
h -
/
s + / /
e + / /
Induzione Strutturale
Possiamo specializzare induzione per alberi
in base alla definizione ricorsiva:
Base un singolo nodo n è un albero (con radice n)
Passo Siano T1,…,Tk, (per qualche k>0) alberi con radici
c1,c2,…,ck, tali che ogni nodo compaia in un solo albero.
Sia r un nuovo nodo. Costruiamo un nuovo albero T:
1. La radice di T è r
2. Aggiungi un edge da r ad ognuna dei nodi c1,…,ck (che
diventano figli di r in T)
c1
T1
r
ck
…
Tk

T=
c1
T1
…
ck
Tk
Induzione Strutturale
Vogliamo provare che l’affermazione S(T) è vera per ogni
albero T
Base: S(T) è vera per ogni albero con un singolo nodo
r
Induzione Strutturale
Vogliamo provare che l’affermazione S(T) è vera per ogni
albero T
Base: S(T) è vera per ogni albero con un singolo nodo
Passo: Sia T con sottoalberi T1…,Tk. Mostriamo che se
S(T1),…,S(Tk) sono tutte vere allora anche S(T) è vera
c1
T1
r
ck
…
Tk

Ipotesi Induttiva su ogni sottoalbero
T=
c1
T1
…
ck
Tk
Induzione Strutturale
Es. Definiamo V(T)= numero di nodi di T
deg(x)= numero di figli di x
Vogliamo provare l’affermazione
S(T): V (T )  1 
 deg(x)
x nodo in T
Induzione Strutturale
Es. Definiamo V(T)=numero di nodi di T e
grado del nodo x =deg(x)= numero di figli di x
Vogliamo provare l’affermazione
S(T): V (T )  1 
 deg(x)
x nodo in T
BASE: Se T ha 1 nodo x, allora x non ha figli e deg(x)=0
 V(T)=1=1+deg(x)
Induzione Strutturale
 deg(x)
S(T): V (T )  1 
x nodo in T
PASSO: Indichiamo con k il numero di figli della radice e
con sottoalberi T1,…,Tk. Siano S(T1),…,S(Tk) vere, cioè
V (Ti )  1 
 deg(x) ,
x nodo in Ti
r
T=
c1
T1
…
ck
Tk
i  1,..., k
Induzione Strutturale
 deg(x)
S(T): V (T )  1 
x nodo in T
PASSO: Indichiamo con k il numero di figli della radice e
con sottoalberi T1,…,Tk. Siano S(T1),…,S(Tk) vere, cioè
V (Ti )  1 
 deg(x) ,
i  1,..., k
x nodo in Ti
Proviamo S(T)
k
k
i 1
i 1
V (T )  1  V (Ti )  1   (1 
r
T=
c1
T1
…
k
ck
Tk
 deg(x) )
x nodo in Ti
 1  k   (  deg(x) )  1  deg( r ) 
i 1
 1
x in Ti
 deg( x)
x nodo in T
 deg( x)
x nodo in T
xr
Induzione Strutturale
Induzione strutturale
 induzione completa
specializzata per alberi
S(T): proprieta P è vera  S(n): proprietà P è vera per
per T
ogni albero con n nodi
Base. Albero con 1 nodo  affermazione vera n=1
Passo. I.I. per ogni sottoalbero  I.I. per ogni m<n
proviamo per T
proviamo per n
Induzione Strutturale
Es. Consideriamo alberi con rappresentazione
sinistra-destra
Vogliamo provare l’affermazione
S(T): il numero di puntatori NULL in T è V(T)+1
BASE: Se T ha 1 nodo x, allora x non ha figli ne fratelli
 V(T)=1,
#NULL=2=V(T)+1
Induzione Strutturale
S(T): #NULL in T è V(T)+1
PASSO: Indichiamo con k il numero di figli della radice e
con sottoalberi T1,…,Tk. Siano S(T1),…,S(Tk) vere, cioè
#NULL in Ti è V(Ti)+1, per ogni i=1,…,k.
r
T=
c1
T1
…
ck
Tk
Induzione Strutturale
S(T): #NULL in T è V(T)+1
PASSO: Indichiamo con k il numero di
figli della radice e con sottoalberi
T1,…,Tk. Siano S(T1),…,S(Tk) vere,
cioè #NULL in Ti è V(Ti)+1, per
ogni i=1,…,k.
r
T=
c1
T1
…
ck
Tk
I puntatori NULL in T sono: rightsibling di r, e quelli di
ogni sottoalbero, tranne il rightsibling di c1,…,ck-1
#NULL in T =
=1 +( #NULL in T1 -1)+…+( #NULL in Tk-1-1)+( #NULL in Tk)
=1+(V(T1)+1-1)) +…+ (V(Tk-1)+1-1)+V(Tk)+1
=1 + V(T1)+…+V(Tk-1)+V(Tk)+1
=V(T) +1
Ricorsione su alberi
r
Schema generale funzione P(T)
{
P(T)
Azione
P(T1);
Azione
P(T2);
…
Azione
P(Tk);
Azione
T=
A0
A1;
Ak-1;
Ak }
c1
T1
…
ck
Tk
Visite di alberi
Visita Preorder: si devono listare i nodi dell’albero in
modo tale che
1. ogni nodo precede nella lista tutti i suoi
discendenti
2. la lista rispetta le relazione sinistra-destra
a
b
e
(a,b,e,c,d,f,e)
c
d
f
g
Visite di alberi
Visita Preorder: si devono listare i
nodi dell’albero in modo tale che
1. ogni nodo precede nella lista tutti
i suoi discendenti
2. la lista rispetta le relazione
sinistra-destra
r
T=
c1
T1
…
ck
Tk
void preorder (pNode n)
{
}
pNODE c; /* figlio di n*/
printf(“%c\n”, n->nodelabel);
c=n->leftmostchild;
while (c != NULL)
{ preorder(c);
c=c->rightsibling;
}
typedef struct NODE *pNODE
struct NODE
{
char nodelabel;
pNODE leftmostchild,
rigthsibling;
}
Visite di alberi
void preorder (pNode n)
{
pNODE c; /* figlio di n*/
printf(“%c\n”, n->nodelabel);
c=n->leftmostchild;
while (c != NULL) { preorder(c);
c=c->rightsibling;}
}
r
T=
c1
…
T1
ck
Tk
CORRETTEZZA
S(T): preorder(T) stampa la lista preorder di T
BASE. Se T ha un solo nodo, lo stampa e si ferma
PASSO. I.I.: preorder(Ti) da Li= lista preorder di Ti,
per ogni i=1,…,k.
Quindi preorder(T) da
L=(r, L1,…,Lk)=lista preorder di T
Visite di alberi
void preorder (pNode n)
{
pNODE c; /* figlio di n*/
printf(“%c\n”, n->nodelabel);
c=n->leftmostchild;
while (c != NULL) { preorder(c);
c=c->rightsibling;}
}
r
T=
R.T.: O(n), dove n è il numero di nodi di T
T(1)=O(1)
T(n)= O(1) + O(n1)+…+O(nk) = O(n)
dove n=1+n1+…+nk
c1
T1
…
ck
Tk
Visite di alberi
Visita Postorder: si devono listare i nodi dell’albero in
modo tale che
1. ogni nodo segue nella lista tutti i suoi discendenti
2. la lista rispetta le relazione sinistra-destra
a
b
e
(e,b,c,f,g,d,a)
c
d
f
g
Visite di alberi
Visita Postorder: si devono listare
i nodi dell’albero in modo tale che
1. ogni nodo segue nella lista tutti i
suoi discendenti
2. la lista rispetta le relazione
sinistra-destra
void postorder (pNode n)
{
}
pNODE c; /* figlio di n*/
c=n->leftmostchild;
while (c != NULL) {postorder(c);
c=c>rightsibling;
}
printf(“%c\n”, n->nodelabel);
r
T=
c1
T1
…
ck
Tk
Visite di alberi
void postorder (pNode n)
{
pNODE c; /* figlio di n*/
c=n->leftmostchild;
while (c != NULL) {postorder(c);
c=c>rightsibling; }
printf(“%c\n”, n->nodelabel);
}
r
T=
c1
…
T1
ck
Tk
CORRETTEZZA
S(T): postorder(T) stampa la lista postorder di T
BASE. Se T ha un solo nodo, lo stampa e si ferma
PASSO. I.I.: postorder(Ti) da Mi= lista postorder del
sottoalbero, per ogni i=1,…,k.
postorder(T) da M=(M1,…,Mk,r)=lista postorder di T
R.T. O(n), dove n è il numero di nodi di T
Computo dell’ Altezza di un albero
Altezza di un nodo n= max distanza di n da una foglia sua
discendente
Altezza albero= altezza radice
Altezza di una foglia = 0
Altezza di un nodo interno n
= 1 + (altezza sottoalbero radicato in n)
= 1 + max altezza figli di n
a
b
e
c
d
f
Altezza di a = 1 + max { altezza di b, altezza di c,
altezza di d }
= 1 + max { 1,0,1}
=1+1=2
g
Computo altezza
Vogliamo una funzione che per ogni nodo calcola l’altezza
del nodo e la scrive nel campo heigth.
typedef struct NODE *pNODE
struct NODE
{
char nodelabel;
int height;
pNODE leftmostchild,
rigthsibling;
}
Altezza di un nodo interno n = 1 + max altezza figli di n
IDEA: per ogni nodo calcola (ricorsivamente) l’altezza di
ogni suo sottoalbero e calcola il max
Visite di alberi
IDEA: per ogni nodo calcola
(ricorsivamente) l’altezza di ogni
suo sottoalbero e calcola il max
r
T=
c1
T1
…
ck
Tk
void computeHt (pNode n)
{
pNODE c;
n->height=0;
c=n->leftmostchild;
while (c != NULL)
{computeHt(c);
if (c->height >= n->height) n->height= 1+c->height;
c=c>rightsibling;
}
}
Computo altezza
void computeHt (pNode n)
{
pNODE c;
n->height=0;
c=n->leftmostchild;
while (c != NULL) {computeHt(c);
if (c->height >= n->height) n->height= 1+c->height;
c=c>rightsibling; }
}
CORRETTEZZA
S(T): computeHt(n) calcola correttamente altezza nodo n
BASE. Se T ha un solo nodo, pone height=0 e si ferma
Computo altezza
void computeHt (pNode n)
{
pNODE c;
n->height=0;
c=n->leftmostchild;
while (c != NULL) {computeHt(c);
if (c->height >= n->height) n->height= 1+c->height;
c=c>rightsibling; }
}
CORRETTEZZA
S(T): computeHt(n) calcola correttamente altezza nodo n
BASE. Se T ha un solo nodo, pone height=0 e si ferma
PASSO. I.I.: computeHt(ni) calcola correttamente l’altezza
del figlio ni di n, per ogni i=1,…,k.
n->heigth= max{1+ n1->height, …, 1+ nk->height}
= max{1+ altezza T1,, …, 1+ altezza Tk} (per I.I)
= 1 + max altezza sottoalberi
Alberi Binari
Ogni nodo ha < 2 figli: figlio destro, figlio sinistro
a
d
b
e
f
g
c
Alberi Binari
Definizione ricorsiva
BASE. Albero vuoto è albero binario
PASSO. Dati 2 alberi binari T1,T2 ed un nuovo nodo r
r
T=
T1
è un albero binario
T2
con sottoalbero di sinistra T1
sottoalbero di destra T2
Alberi Binari
Bastano due puntatori per nodo:
figlio destro, figlio sinistro
Struttura dati
Typedef struct NODE *TREE
struct NODE{
etype nodelabel;
TREE leftchild, rightchild;
}
Ricorsione su Alberi Binari
FUNZIONE (T TREE)
{
Azione A0
FUNZIONE(T1)
Azione A1;
FUNZIONE(T2)
Azione A2;
}
Visita Inorder
Visita Inorder: si devono visitare i nodi dell’albero in
modo tale che
1. ogni nodo segue nella lista tutti i nodi del sottoalbero
di sinistra
2. precede nella lista tutti i nodi del sottoalbero di
destra
r
T=
c1
c2
T1
T2
Lista Inorder di T =
(lista inorder T1, r, lista inorder T2)
Visita Inorder
Visita Inorder: si devono visitare i nodi dell’albero in modo
tale che
1. ogni nodo segue nella lista tutti i nodi del sottoalbero di
sinistra
2. precede nella lista tutti i nodi del sottoalbero di
destra
Lista Inorder: (e,b,a,f,d,g,c)
a
d
b
e
f
g
c
Visita Inorder
Visita Inorder: si devono visitare i
nodi dell’albero in modo tale che
1. ogni nodo segue nella lista tutti i
nodi del sottoalbero di sinistra
2. precede nella lista tutti i nodi del
sottoalbero di destra
void inorder(TREE T)
{
}
if (T!=NULL) {
inorder(T->leftchild);
printf(“%c\n”, T->nodelabel);
inorder(T->rightchild);
}
r
T=
c1
c2
T1
T2
Visita Inorder
void inorder(TREE T)
{
}
if (T!=NULL) {
inorder(T->leftchild);
printf(“%c\n”, T->nodelabel);
inorder(T->rightchild);
}
Inorder: e,b,a,f,d,g,c
a
d
b
e
f
g
c
Alberi Binari di RICERCA
Problema: mantenere un insieme di elementi permettendo
1. Inserzione di nuovi elementi (insert)
2. Cancellazione di elementi dall’insieme (delete)
3. Ricerca di un elemento per sapere se è nell’insieme
(lookup)
Insieme di elementi = dizionario
Assumiamo: elementi del dizionario scelti da un insieme
(detto universo) ordinato (esiste relazione <);
es. interi, reali, stringhe caratteri.
Alberi Binari di RICERCA
Albero binario di ricerca (BST): albero binario con
“label” tale che per ogni nodo n
1. ogni nodo nel sottoalbero sinistro di n ha label < della
label di n
2. ogni nodo nel sottoalbero destro di n ha label > della
label di n
10
7
5
15
11
20
22
Alberi Binari di RICERCA
Albero binario di ricerca (BST): albero binario con
“label” tale che per ogni nodo n
1. ogni nodo nel sottoalbero sinistro di n ha label < della
label di n
2. ogni nodo nel sottoalbero destro di n ha label > della
label di n
10
10
7
5
15
11
15
7
20
5
11
22
22
SI
20
NO
Alberi Binari di RICERCA
Albero binario di ricerca (BST): albero binario con
“label” tale che per ogni nodo n
1. ogni nodo nel sottoalbero sinistro di n ha label < della
label di n
2. ogni nodo nel sottoalbero destro di n ha label > della
label di n
10
10
7
5
15
11
15
7
20
10
5
11
20
5
11
22
22
SI
15
7
NO
20
22
NO
Alberi Binari di RICERCA
Lookup: Dato BST T, risulta x in T?
Ricerca ricorsiva
BASE. T è vuoto  x non è in T
T non vuoto ed x è alla radice di T  x è in T
PASSO. [T non vuoto ed x non è alla radice di T].
Sia y l’elemento alla radice di T
Se x< y  cerca x in sottoalbero sinistro di T
Se x> y  cerca x in sottoalbero destro di T
Alberi Binari di RICERCA
BASE. T è vuoto  x non è in T
T non vuoto ed x è alla radice di T  x è in T
PASSO. [T non vuoto ed x non alla radice]. Sia y l’elemento alla radice di T.
Se x< y  cerca x in sottoalbero sinistro di T
Se x> y  cerca x in sottoalbero destro di T
BOOLEAN lookup(TREE T, etype x)
{
if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=9
10
7
5
9<10
10
15
11
20
7
5
15
11
20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=9
10
7
5
10
15
11
20
7
5
15
11
9>7
20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=9
10
7
5
10
15
11
20
7
5
15
11
20
NULL  FALSE
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=16
10
7
5
16>10
10
15
11
20
7
5
15
11
20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=16
10
7
5
10
15
11
20
7
5
16>15
15
11
20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=16
10
7
5
10
15
11
20
7
5
15
11
20
16<20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=16
10
7
5
10
15
11
20
7
5
15
11
20
NULL  FALSE
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=11
10
7
5
11>10
10
15
11
20
7
5
15
11
20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=11
10
7
5
10
15
11
20
7
5
11<15
15
11
20
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
x=11
10
7
5
10
15
11
20
7
5
15
11
20
11=11  TRUE
Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x)
{if(T==NULL) return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)
}
Running Time. Indichiamo con h(T) l’altezza di T.
Il r.t. di lookup su T è O(h(T))
Indichiamo con R(h) il running time di lookup su albero di
altezza h.
BASE. R(0)=O(1)
PASSO. R(h)=O(1) + R(h-1)
Quindi R(h)=O(h)
Alberi Binari di RICERCA
Insert: Dato BST T, inserisci x in T (se non è presente)
BASE. T è vuoto  crea un nodo contenete x
T non vuoto ed x è alla radice di T  STOP
PASSO. [T non vuoto ed x non è alla radice di T].
Sia y l’elemento alla radice di T
Se x< y  insert x in sottoalbero sinistro di T
Se x> y  insert x in sottoalbero destro di T
Alberi Binari di RICERCA
BASE. T è vuoto  crea un nodo contenete x
T non vuoto ed x è alla radice di T  STOP
PASSO. [T non vuoto ed x non alla radice]. Sia y elemento alla radice di T
Se x < y  insert x in sottoalbero sinistro di T
Se x > y  insert x in sottoalbero destro di T
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x;
T->leftchild=NULL;
T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=6
10
7
5
6<10
10
15
11
20
7
5
15
11
20
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=6
10
7
5
10
15
11
20
7
5
15
11
6<7
20
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=6
10
7
5
10
15
11
20
7
5
15
11
20
6>5
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=6
10
7
5
10
15
11
20
15
7
5
11
6
20
T=NULL
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=9
10
7
5
9<10
10
15
11
20
7
5
15
11
20
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=9
10
7
5
10
15
11
20
7
5
15
11
9>7
20
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=9
10
7
5
10
15
11
20
15
7
5
9
11
20
T=NULL
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=15
10
7
5
15>10
10
15
11
20
7
5
15
11
20
Alberi Binari di RICERCA
TREE insert(TREE T, etype x)
{
if(T==NULL) {
T=TREE(malloc(sizeof(struct NODE));
T->element=x; T->leftchild=NULL; T->rightchild=NULL;
}
else if (x<T->element) return insert(T->leftchild, x);
else if (x>T->element) return insert(T->rightchild, x);
}
x=15
10
7
5
10
15
11
20
7
5
15=15, STOP
15
11
20
Alberi Binari di RICERCA
Delete: Dato BST T, cancella x da T (se è presente)
Alberi Binari di RICERCA
Delete: Dato BST T, cancella x da T (se è presente)
1. X non è in T, ok.
Alberi Binari di RICERCA
Delete: Dato BST T, cancella x da T (se è presente)
1. X non è in T, ok.
2. Nodo n contenente
x è una foglia 
cancella puntatore al
nodo n
10
7
5
n x

20
7
5
10
10
Cancella 5
15
11
NULL
15
11

20
7
15
11
20
Alberi Binari di RICERCA
3. Nodo n contenente
x ha un solo figlio
(nodo m) 
sostituisci n con m
n x NULL
m
10
7
5
Cancella 7

15
11
20
10
10
7
5
y
y
15
11
15

20
5
11
20
Alberi Binari di RICERCA
4. Nodo che contiene x ha due figli:
- trova nel sottoalbero destro di n il nodo che contiene
il più piccolo elemento (siano m il nodo e y l’elemento)
- sostituisci y ad x in n
- cancella m
n x
<x
n y
>x
<x<y
>y>x
cancellando m
contenente
y= min
Alberi Binari di RICERCA
NOTA: l’elemento minimo di un albero si trova in un nodo
che non ha figlio sinistro.
10
7
5
15
11
20
Alberi Binari di RICERCA
ETYPE deletemin(TREE *pT)
{ ETYPE min;
if (*pT)->leftchild==NULL) {
min=(*pT)->element;
(*pT)=(*pT)->rightchild;
return min;}
else return deletemin(&(*pT)->leftchild);
}
10
7
5
11
20
Funzione lavora su puntatore
(*pT) al puntatore all’albero;
Altrimenti cambio albero
locale a deletemin.
10

15
Cancella e restituisce minimo
7
5
15
11
NULL
min=5
20
Alberi Binari di RICERCA
ETYPE deletemin(TREE *pT)
{ ETYPE min;
if (*pT)->leftchild==NULL) {
min=(*pT)->element;
(*pT)=(*pT)->rightchild;
return min;}
else return deletemin(&(*pT)->leftchild);
}
10
7
5
11
20
Funzione lavora su puntatore
(*pT) al puntatore all’albero;
Altrimenti cambio albero
locale a deletemin.
10

15
Cancella e restituisce minimo
7
5
11
NULL
min=5

15
20
10
7
NULL
15
11
20
Return min=5
Alberi Binari di RICERCA
Es. Cancella 4: minimo sottoalbero destro di 4 è 5,
sostituisci label 4 con 5
cancella nodo contenente 5
4
5
10
3
7
1
5
15
11
10
3
7
1
20
5
5
10
3
7
1
5
15
11
20
15
11
20
Alberi Binari di RICERCA
void delete(TREE *pT, ETYPE x)
{
if ((*pT)!=NULL)
if (x < (*pT)->element) delete(&((*pT)->leftchild),x);
else if ( x > (*pT)-> element) delete (&((*pT)->rightchild), x);
else /* x è alla radice */
if ((*pT)->leftchild==NULL) (*pT)=(*pT)->rigthchild;
else if ((*pT)->rigthchild==NULL) (*pT)=(*pT)->leftchild;
else /* radice ha 2 figli */
(*pT)->element)=deletemin(&((*pT)->rigthchild));
}
LEGENDA: cerca x, radice contiene x ed ha al più 1 figlio, ha 2 figli
Alberi Binari di RICERCA
Running Time. Indichiamo con h(T) l’altezza di T.
Il r.t. di operazioni su T è O(h(T))
Indichiamo con R(h) il running time su albero di altezza h.
BASE. R(0)=O(1)
PASSO. R(h)=O(1) + R(h-1)
Quindi R(h)=O(h)
Alberi Binari di RICERCA
Running Time. Indichiamo con h(T) l’altezza di T.
Il r.t. di operazioni su T è O(h(T))
Indichiamo con R(h) il running time su albero di altezza h.
BASE. R(0)=O(1)
PASSO. R(h)=O(1) + R(h-1)
Quindi R(h)=O(h)
Altezza BST con n nodi?
Alberi Binari di RICERCA
Caso migliore: minimizzare altezza
Albero completo: ogni nodo ha 0 o 2 figli,
tutte le foglie sono sullo stesso livello
5
10
3
1
4
7
15
Albero completo di altezza h ha n=2h+1-1 nodi,
Quindi h=log (n+1)-1=O(log n)
Alberi Binari di RICERCA
S(h): Albero binario completo di altezza h ha 2h+1-1 nodi,
Base. h=0 => 1 nodo. OK.
Passo. I.I.
S(h). Mostriamo S(h+1).
Alberi Binari di RICERCA
S(h): Albero binario completo di altezza h ha 2h+1-1 nodi,
Base. h=0 => 1 nodo. OK.
Passo. I.I.
S(h). Mostriamo S(h+1).
Albero completo di altezza h+1
formato da radice e due
sottoalberi di altezza h
5
10
3
1
4
7
15
Alberi Binari di RICERCA
S(h): Albero binario completo di altezza h ha 2h+1-1 nodi,
Base. h=0 => 1 nodo. OK.
Passo. I.I.
S(h). Mostriamo S(h+1).
Albero completo di altezza h+1
formato da radice e due
sottoalberi di altezza h
Quindi
5
10
3
1
4
7
15
numero di nodi in albero binario completo di altezza h+1
= 1 +2 (numero nodi albero binario completo altezza h)
= 1 + 2 (2h+1-1)
= 1 + 2h+2 -2
= 2h+2 -1
Alberi Binari di RICERCA
Caso peggiore: massimizzare altezza
1
2
Insert
1
Insert
2
Insert 3
3
Insert 4
4
…
n
Insert n
Altezza è n-1
In pratica si hanno alberi quasi completi
(quindi h=O(log n))