Lez. 9 1

Universita' di FerraraFacolta' di Scienze Matematiche, Fisiche e Naturali

Laurea Specialistica in Informatica

Algoritmi Avanzati

Alberi di ricerca binaria

Copyright © 2006-2009 by Claudio Salati.

2

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.

3

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

• . . .

4

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 in-ordine.

• L'elemento a e' presente nell'insieme se e solo se c'e' un nodo v dell'albero per cui a = v.element

5

Alberi di Ricerca Binaria: RAPPRESENTAZIONE

typedef struct node *nodeRef;

struct node {

elementName element;

nodeRef leftSon;

nodeRef rightSon;

};

nodeRef insieme;

• 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

6

Verifica se l’insieme e’ vuoto

Boolean isEmpty(nodeRef tree) { return(tree==NULL);

}

7

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));

}

8

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)

9

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);

}

10

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);

}

11

Ricerca di elemento minimo e massimo: esercizio

Scrivere la versione iterativa delle due funzioni

• nodeRef minElement (nodeRef tree);

• nodeRef maxElement (nodeRef tree);

12

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;

}

13

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)}

14

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)

15

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

16

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

17

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)}

18

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)

19

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 O HA SOLO IL FIGLIO SINISTRO!)

20

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 STRETTO

21

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)

22

• 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)

Complessita' media: dimostrazione - 2

23

T(n) =

• ed essendo T(0) = 0

(1)

• Abbiamo quindi una relazione ricorsiva che definisce T(n).

Complessita' media: dimostrazione - 3

( )

n

1n+)jn(T+)1j(T=∑n

1=j

---

∑1n

0=j

)j(T*n2

+1n=-

-

∑1n

1=j

)j(T*n2

+1n=)n(T-

-

24

• Proviamo se la relazione e' soddisfatta da T(n) = c * n * log(n) (che e' la complessita' "desiderata").

• Sostituiamo nella relazione ricorsiva (1):

(2)

• Quanto vale la sommatoria che compare in (2)?

Complessita' media: dimostrazione - 4

? ( )∑1n

1=j

)jlog(*j*nc*2

+1n=)nlog(*n*c -

25

• Consideriamo una generica funzione monotona crescente f(x)

(3)

Complessita' media: dimostrazione - 5

n

k

nn

k

)k(fdx)x(f)k(f1

1

11

1

26

Ma

per cui, sottraendo (f(n) - f(1)) dall'integrale di (3):

(4)

consideriamo allora f(x) = x * ln(x)

tenendo conto che

e sostituendo nella disequazione (4)

(vedi pagina seguente)

Complessita' media: dimostrazione - 6

)f()nf()k(f)k(fn

k

n

k

11111

1

11

1

1

11nn

k

n

dx)x(f)k(f))(f)n(f(dx)x(f

42

22 x)xln(

xdx)xln(x

27

cioe'

Complessita' media: dimostrazione - 7

4

10

4

n)nln(*

2

n

)kln(k

)0)nln(n(4

10

4

n)nln(*

2

n

22

1n

1k

22

4

1

4

n)nln(

2

n)kln(k

221n

1k

28

E dividendo per ln(2)

che sostituiamo nella relazione ricorsiva (2):

quindi, a meno di termini di ordine minore: T(n) = O(n*log(n))

Complessita' media: dimostrazione - 8

)2ln(*4

1

)2ln(*4

n)nlog(

2

n)klog(k

221n

1k

n*)2ln(*2

c1n*

)2ln(*2

c1)nlog(*n*c

)2ln(*4

1

)2ln(*4

n)nlog(

2

n

n

c21n

22