Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Alberi di ricerca binaria
Copyright © 2006-2009 by Claudio Salati.
Lez. 9
1
ALBERI DI RICERCA BINARIA
• SI CONSIDERI UN UNIVERSO MOLTO VASTO, I CUI
ELEMENTI SONO LINEARMENTE ORDINATI DA UNA
RELAZIONE "  ".
• AD ESEMPIO:
• N = { NUMERI NATURALI }
• { STRINGHE ALFABETICHE O ALFANUMERICHE }
• ...
• LA RELAZIONE "  " DIPENDE DAL PARTICOLARE universo
CONSIDERATO.
• SI ASSUME COMUNQUE CHE IL CONFRONTO TRA DUE
ELEMENTI SIA ESEGUIBILE IN TEMPO COSTANTE.
2
ALBERI DI RICERCA BINARIA
• Si considera il caso in cui NON CI INTERESSA OPERARE TRA
INSIEMI, MA SOLO SU UN SINGOLO INSIEME PER:
• INSERIRE UN ELEMENTO
N.B.: si assume che un elemento possa essere inserito
nell’insieme una sola volta
(non possa comparire nell’insieme piu’ di una volta)
• CANCELLARE UN ELEMENTO
• VERIFICARE SE UN ELEMENTO APPARTIENE
ALL'INSIEME
• TROVARE L'ELEMENTO MINIMO (O MASSIMO)
DELL'INSIEME
• Trovare l’elemento immediatamente precedente o quello
immediatamente successivo di un elemento dato
• ...
3
Alberi di Ricerca Binaria: RAPPRESENTAZIONE
• Si puo' mappare l'insieme su un albero binario che abbia le
seguenti proprieta':
1. AD OGNI NODO v DELL'ALBERO E' ASSOCIATO UN
ELEMENTO DELL'INSIEME, IL CUI VALORE E'
v.element
2. PER OGNI NODO u DEL SOTTOALBERO SINISTRO DI v E'
u.element < v.element
3. PER OGNI NODO u DEL SOTTOALBERO DESTRO DI v E'
u.element > v.element
4. ogni elemento dell'insieme e' associato ad uno ed un solo
solo nodo dell'albero.
• Gli elementi dell'insieme sono quindi memorizzati nell'albero in inordine.
• L'elemento a e' presente nell'insieme se e solo se c'e' un nodo v
4
dell'albero per cui a = v.element
Alberi di Ricerca Binaria: RAPPRESENTAZIONE
typedef struct node
struct node {
elementName
nodeRef
nodeRef
};
nodeRef insieme;
*nodeRef;
element;
leftSon;
rightSon;
• se insieme =  allora insieme == NULL
• NOTA CHE L'ALBERO NON E' BILANCIATO
• non si fa nessuna assunzione sul fatto che l'albero sia
bilanciato
• non si fa niente per mantenere l'albero bilanciato
5
Verifica se l’insieme e’ vuoto
Boolean isEmpty(nodeRef tree) {
return(tree==NULL);
}
6
Ricerca di un elemento
nodeRef search (nodeRef tree,
elementName el) {
// cerca nell'insieme rappresentato dal (sotto-)
// albero tree l'elemento di nome el
// ritorna il puntatore al nodo che contiene el
// o NULL se l'albero non contiene el
return(tree==NULL ?
NULL
: tree->element == el ?
tree
: tree->element > el ?
search(tree->leftSon, el)
: // tree->element < el
search(tree->rightSon, el));
}
7
Ricerca di un elemento
nodeRef search (nodeRef tree,
elementName el) {
if (tree==NULL)
return(NULL);
else if (tree->element == el)
return(tree)
else if (tree->element > el)
return (search(tree->leftSon, el));
else // tree->element < el
return(search(tree->rightSon, el));
// end if
}
• si potrebbe verificare se un albero e' vuoto prima di chiamare
search() per quell'albero.
(per risparmiare una costosa chiamata di procedura)
8
Ricerca di un elemento - versione iterativa
nodeRef search (nodeRef tree,
elementName el) {
while ((tree != NULL) &&
(tree->element != el))
if (tree->element > el)
tree = tree->leftSon;
else // tree->element < el
tree = tree->rightSon;
// end if
}
return(tree);
}
9
Ricerca di elemento minimo e massimo
nodeRef minElement (nodeRef tree) {
assert(tree!=NULL);
return(tree->leftSon != NULL?
minElement(tree->leftSon)
: tree);
}
nodeRef maxElement (nodeRef tree) {
assert(tree!=NULL);
return(tree->rightSon != NULL?
maxElement(tree->rightSon)
: tree);
}
10
Ricerca di elemento minimo e massimo: esercizio
Scrivere la versione iterativa delle due funzioni
• nodeRef minElement (nodeRef tree);
• nodeRef maxElement (nodeRef tree);
11
Inserimento di un nuovo elemento - 1
void addNode (nodeRef *ptree,
elementName el) {
(*ptree) = malloc(sizeof(struct node));
(*ptree)->leftSon = NULL;
(*ptree)->rightSon = NULL;
(*ptree)->element = el;
}
12
Inserimento di un nuovo elemento - 2
void nonEmptyInsert (nodeRef tree,
elementName el) {
assert(tree != NULL && el  tree);
if (el < tree->element)
if (tree->leftSon != NULL)
nonEmptyInsert(tree->leftSon, el);
else
addNode(&(tree->leftSon), el);
// end if (tree->leftSon != NULL)
else // (el > tree->element)
if (tree->rightSon != NULL)
nonEmptyInsert(tree->rightSon, el);
else
addNode(&(tree->rightSon), el);
// end if (tree->rightSon != NULL)
// end if (el < tree->element)
}
13
Inserimento di un nuovo elemento - 3
void nodeInsert (nodeRef *ptree,
elementName el) {
// P = { el non e' gia' presente in
//
**ptree }
if ((*ptree) == NULL)
addNode(ptree, el);
else
nonEmptyInsert(*ptree, el);
}
• Esercizio: modificare nodeInsert() cosi' che ritorni OK se
l'inserimento del nuovo elemento ha effettivamente avuto luogo
con successo, NOK se l'inserimento e' fallito, ad esempio
perche' l'elemento da inserire era gia' presente nell'albero
(N.B.: questa modifica consentirebbe di eliminare i vincoli
presenti nella precondizione della funzione)
14
Cancellazione di un elemento - 1
void nonEmptyDelete (nodeRef *father,
nodeRef tree,
elementName el) {
// P = { el  tree }
if (tree->element != el)
if (el < tree->element) {
assert(tree->leftSon != NULL);
nonEmptyDelete(&(tree->leftSon),
tree->leftSon, el);
} else { // (el > tree->element)
assert(tree->rightSon != NULL);
nonEmptyDelete(&(tree->rightSon),
tree->rightSon, el);
} // end if (el < tree->element)
else // (tree->element == el)
// continua alla pagina seguente
15
Cancellazione di un elemento - 2
// continua void nonEmptyDelete ()
// (tree->element == el)
if ((tree->leftSon == NULL) &&
(tree->rightSon == NULL)) {
// il nodo e' una foglia
*father = NULL;
free(tree);
} else if (tree->leftSon == NULL){
// il nodo ha solo il figlio di destra
*father = tree->rightSon;
free(tree);
} else if (tree->rightSon == NULL){
// il nodo ha solo il figlio di sinistra
*father = tree->leftSon;
free(tree);
} else { // il nodo ha due figli
// continua alla pagina seguente
16
Cancellazione di un elemento - 3
// continua void nonEmptyDelete ()
// il nodo ha due figli
tree->element =
(maxElement(tree->leftSon))->element;
nonEmptyDelete(&(tree->leftSon),
tree->leftSon,
tree->element);
}
} // end if (tree->element != el)
}
17
Cancellazione di un elemento - 4
void delete (nodeRef *ptree,
elementName el) {
// P = { el  *ptree }
assert((*ptree) != NULL);
nonEmptyDelete(ptree, (*ptree), el);
}
• Esercizio: modificare delete() cosi' che ritorni OK se la
cancellazione dell'elemento dall'insieme ha effettivamente avuto
luogo con successo, NOK se la cancellazione e' falllita, ad
esempio perche' l'elemento da rimuovere non era presente
nell'albero
(N.B.: questa modifica consentirebbe di eliminare i vincoli
presenti nella precondizione della funzione)
18
Alberi di Ricerca Binaria
• Correttezza degli algoritmi:
 lasciata per esercizio
• Complessita' degli algoritmi:
• SE L'ALBERO FOSSE BILANCIATO LE OPERAZIONI
SAREBBERO O(log(n)), CON n NUMERO DEGLI ELEMENTI
NELL'ALBERO
• COSI' NEL CASO PEGGIORE SONO O(n)
• SONO POSSIBILI MIGLIORAMENTI SPICCIOLI.
VEDI AD ESEMPIO delete(), DOVE LA CHIAMATA
RICORSIVA E L'IDENTIFICAZIONE DEL SOSTITUTO
POSSONO ESSERE SOSTITUITE DA UNA PROCEDURA
COLLASSATA, CHE EVITI ANCHE LA RICORSIONE DATO
CHE IL maxElement() TROVATO NON PUO' AVERE 2
FIGLI, ALTRIMENTI NON SAREBBE MAX (O E' UNA FOGLIA
19
O HA SOLO IL FIGLIO SINISTRO!)
Complessita' degli algoritmi: tempo atteso
• CONSIDERIAMO PERO' IL TEMPO ATTESO DI n OPERAZIONI ED
IN PARTICOLARE DI n INSERZIONI DI ELEMENTI DIVERSI CHE
SIANO IN ORDINE RANDOM
• IL NUMERO ATTESO DI CONFRONTI PER SVOLGERE QUESTO
INSIEME DI OPERAZIONI E' O(n*log(n))
(tempo atteso  tempo medio)
• GENERALIZZANDO:
• OPERANDO SUL SET CON OPERAZIONI CHE RIFERISCONO
ELEMENTI SCELTI IN MODO CASUALE LA COMPLESSITA'
MEDIA DI CIASCUNA OPERAZIONE E' O(log(n))
• COME SE L'ALBERO FOSSE BILANCIATO!
• ESISTONO TECNICHE (e.g. 2-3 B-TREE) CHE CONSENTONO DI
AVERE OPERAZIONI DI COMPLESSITA' O(log(n)) IN SENSO
20
STRETTO
Complessita' media: dimostrazione - 1
• T(n) = NUMERO DI CONFRONTI RICHIESTI PER CREARE
L'ALBERO CON L'INSERZIONE DEGLI ELEMENTI a(1), a(2),
..., a(n)
• evidentemente: T(0) = 0
• b(1), ..., b(n) SIA LA SEQUENZA CRESCENTE DEGLI a(i)
• a(1) = b(j), j QUALUNQUE TRA 1 E n
• PER COME FUNZIONA insert(),
• a(1) SARA' LA RADICE DELL'ALBERO
• b(1), ..., b(j-1) COSTITUIRANNO IL SUO SOTTOALBERO
SINISTRO (di j-1 elementi)
• b(j+1), ..., b(n) COSTITUIRANNO IL SUO SOTTOALBERO
DESTRO (di n-j elementi)
21
Complessita' media: dimostrazione - 2
• LA COMPLESSITA' DI CREARE IL SOTTOALBERO SX E':
 T(j-1) + (j-1) confronti con la radice
• LA COMPLESSITA' DI CREARE IL SOTTOALBERO DX E':
 T(n-j) + (n-j) confronti con la radice
• Quindi:
 T(n) = ((j-1) + T(j-1)) + ((n-j) + T(n-j)), cioe'
 T(n) = n-1 + T(j-1) + T(n-j)
• j PUO' ASSUMERE QUALSIASI VALORE TRA 1 E n, PERCIO'
IN MEDIA E'
(vedi pagina seguente)
22
Complessita' media: dimostrazione - 3
T(n) =
n
=
∑( T(
j - 1) + T( n - j ) + n - 1)
j=1
n
2 n-1
= n - 1 + * ∑ T( j )
n j=0
• ed essendo T(0) = 0
2 n-1
T( n ) = n - 1+ * ∑ T( j )
n j=1
(1)
• Abbiamo quindi una relazione ricorsiva che definisce T(n).
23
Complessita' media: dimostrazione - 4
• Proviamo se la relazione e' soddisfatta da T(n) = c * n * log(n)
(che e' la complessita' "desiderata").
• Sostituiamo nella relazione ricorsiva (1):
2*c n 1
c * n * log( n ) = n - 1+
* ∑( j * log( j ))
n
j=1
?
(2)
• Quanto vale la sommatoria che compare in (2)?
24
Complessita' media: dimostrazione - 5
• Consideriamo una generica funzione monotona crescente f(x)
n
n

1
n
f
(
k
)

f
(
x
)
dx

f
(
k

1
)



k

1
1
(3)
k

1
25
Complessita' media: dimostrazione - 6
n


f
(
k

1
)

f
(
k
)

f(
n

1
)

f(
1
)






k

1
k

1 

n
Ma
per cui, sottraendo (f(n) - f(1)) dall'integrale di (3):
n

1
n
n

1
1
k

1
1
(4)
f
(
x
)
dx

(
f
(
n

1
)

f
(
1
))

f
(
k
)

f
(
x
)
dx



consideriamo allora f(x) = x * ln(x)
2
2
x
x
tenendo conto che
x

ln(
x
)
dx

ln(
x
)


2
4
e sostituendo nella disequazione (4)
(vedi pagina seguente)
26
Complessita' media: dimostrazione - 7
n2
n2  1
 *ln(
0 (nln(
n
)

n)0)
2

4  4

n1

kln(
k)
k1
n2
n2  1
 *ln(
0 
n
)

2
  4
4


cioe'
n

1
2
2
n
n1
k

ln(
k
)

ln(
n
)


2
44
k

1
27
Complessita' media: dimostrazione - 8
E dividendo per ln(2)
n

1
2
2
n
n
1
k

log(
k
)


log(
n
)
 

2
4
*
ln(
2
)
4
*
ln(
2
)
k

1
che sostituiamo nella relazione ricorsiva (2):
2
2
2

c
n
n
1
 


n

1
 
log(
n
)




n 2
4
*
ln(
2
)4
*
ln(
2
)


c  
c 





c
*
n
*
log(
n
)

1

*
n

1





2
*
ln(
2
)
2
*
ln(
2
)
*
n

 

quindi, a meno di termini di ordine minore: T(n) = O(n*log(n))
28