Algoritmi e Laboratorio a.a. 2009-10 Lezionielio/DIDATTICA/aa0910/AlgELab/slides/lez34-albe... ·...

1

Università di Torino – Facoltà di Scienze MFNCorso di Studi in InformaticaCurriculum SR (Sistemi e Reti)

Algoritmi e Laboratorio a.a. 2009-10 Lezioni

prof. Elio Giovannetti

Lezione 34 – Alberi di ricerca binari(versione 20/01/10)

Quest' opera è pubblicata sotto una Licenza Creative CommonsAttribution-NonCommercial-ShareAlike 2.5.

Quest' opera è pubblicata sotto una Licenza Creative CommonsAttribution-NonCommercial-ShareAlike 2.5.

Sommario• Motivazioni e definizioni (di albero di ricerca binario).• Realizzazioni (illustrate con solo ricerca e inserimento):

• programmazione imperativa non a oggetti (C), consottoalbero vuoto rappresentato da costante (null):pp ( )

• versione con procedure ricorsive;• versione con procedure iterative;

• programmazione a oggetti (Java, C#):• sottoalbero vuoto rappresentato da null:

- versione con procedure ricorsive;- versione con procedure iterative;

20/01/10 18.43 E. Giovannetti - AlgELab-09-10 - Lez.34 2

versione con procedure iterative;• sottoalbero vuoto rappresentato da oggetto-nodo:

- versione con procedure ricorsive;- versione con procedure iterative;

• operazione di cancellazione: versioni ricorsiva e iterativa.

2

Motivazioni: implementazioni di dizionarioRicordando che dizionario è una collezione di elementi sullaquale si possono operare ricerca, inserimento e cancellazione,le realizzazioni finora viste hanno le seguenti complessitàtemporali (del caso medio e peggiore):• array non ordinato:

• ricerca: O(n) (ricerca sequenziale);• inserimento: O(1) (l'elemento si può inserire al fondo);• cancellazione: O(n) (bisogna cercare l'elemento)

• array ordinato: • ricerca: O(log n) (ricerca binaria);


( g ) ( )• inserimento: O(n) (bisogna spostare tutti gli el. seguenti);• cancellazione: O(n) (come sopra);

(continua nella slide successiva)

• lista non ordinata:• ricerca: O(n) (ricerca sequenziale);

(1) (l' l ò )• inserimento: O(1) (l'elemento si può inserire in testa);• cancellazione: O(n) (bisogna cercare l'elemento);

• lista ordinata: • ricerca: O(n) (su lista la ricerca binaria non ha senso);• inserimento: O(n) (bisogna cercare il posto);• cancellazione: O(n) (bisogna cercare l'elemento);



3

Nota

• Perché nelle due slides precedenti si è usata la notazione Oinvece della notazione Θ ?

• Risposta: perché, per semplicità, in esse non si è scritto "complessità del caso peggiore" o "del caso medio" ma complessità del caso peggiore o del caso medio , ma semplicemente "complessità" senza qualificazioni; per essa valgono quindi le considerazioni e le definizioni riportate nelle slides 14, 15, 16, 17 di Lez. 08 (Complessità problemi).



Si noti:• array ordinati:

• il posto dove inserire l’elemento, o l'elem. da cancellare, possono essere trovati in tempo logaritmico possono essere trovati in tempo logaritmico,

• ma il successivo spostamento degli elementi che seguono richiede un tempo lineare;

• liste ordinate:• l'inserimento o la cancellazione in un dato punto non

richiedono spostamenti degli elementi successivi, quindi i hi d l t t t


richiede solo un tempo costante;• ma la precedente ricerca del posto dove inserire o del-

l'elemento da cancellare, non potendo essere fatta con la ricerca binaria, richiede un tempo lineare.

4

Alberi di ricerca.• Vogliamo trovare una struttura dati che combini i rispettivi

vantaggi di array ordinato e lista, e che quindi sia:• una struttura concatenata, in cui inserimento e cancella-

zione si possano fare per semplice modifica di puntatori; l l l• una struttura in cui sia possibile la ricerca logaritmica.

• Una tale struttura è un albero di ricerca.• Se l'albero è bilanciato, le tre operazioni principali sono

tutte logaritmiche.• Sequenze di inserimenti e cancellazioni su un albero

possono sbilanciarlo riducendo quindi l'efficienza delle operazioni successive fino a farla diventare lineare


operazioni successive, fino a farla diventare lineare.• Studiamo dapprima la struttura albero-di-ricerca semplice.• Studieremo poi alcune strutture albero-di-ricerca più

complesse che garantiscono il bilanciamento e quindi la logaritmicità delle tre operazioni principali.

Alberi di ricerca binari (ARB)Binary Search Trees (BST)

Definizione non induttiva.Sia E un tipo su cui è definita una relazione d'ordine totale.Sia E un tipo su cui è definita una relazione d ordine totale.Un albero di ricerca binario di elementi di tipo E è un albero binario di elementi di tipo E in cui per ogni nodo V vale la proprietà che, assumendo che non vi siano elementi uguali fra loro:

tutti gli elementi contenuti nel sottoalbero sinistro sono minori dell'elemento in V;


minori dell elemento in V;tutti gli elementi contenuti nel sottoalbero destro sono maggiori dell'elemento in V.

5

Alberi di ricerca binari: una definizione equivalenteDefinizione induttiva (equivalente alla precedente)

Se E è un tipo su cui è definita una relazione d'ordine totale:• un albero vuoto è un albero di ricerca binario di elementi di

tipo E;tipo E;• se T1 e T2 sono due alberi di ricerca binari di elementi di

tipo E, ed el è un elemento di tipo E tale che:• tutti gli elementi di T1 sono minori di el;• tutti gli elementi di T2 sono maggiori di el;

allora l'albero (T1 el T2) è un albero di ricerca binario di


elementi di tipo E.

elT1 T2

el

T1 T2

Una proprietà importante:la sequenza di visita in-ordine è in ordine !

In un albero di ricerca binario la sequenza dei nodi nella visita in-ordine è una sequenza ordinata.Dimostrazione per induzione strutturaleDimostrazione per induzione strutturale.Base (albero vuoto o con un solo nodo): ovvia. Passo (albero con più di un nodo, chiamiamone r la radice):Ip. Induttiva: La sequenza in-ordine s1, s2, … , sk del sottoal-bero sinistro e quella d1, d2, …, dh del sottoalbero destro sono sequenze ordinate.Tesi Induttiva: La sequenza in-ordine dell’intero albero è Tesi Induttiva: La sequenza in ordine dell intero albero è ordinata. Dim.: La sequenza in-ordine dell’albero è, per definizione, s1, s2, … , sk , r, d1, d2, …, dh. Poiché, per la definiz. di albero di ricerca, r è maggiore di tutti gli s e minore di tutti i d, …


6

Dizionari realizzati come alberi di ricerca binariIl tipo astratto Dizionario, secondo la Definizione 1 oppuresecondo la Definizione 2, può essere realizzato tramite unalbero di ricerca binario, dove ogni elemento è:• se si usa la Definizione 1: una coppia chiave-valore;f pp ;• se si usa la Definizione 2: un oggetto contenente un campo

che ha il ruolo di chiave, oppure un oggetto dal quale è ricavabile un valore che funziona da chiave.

Un albero di ricerca è una struttura ordinata: sul tipo dellechiavi deve dunque risultare definito un ordine totale


chiavi deve dunque risultare definito un ordine totale.

Nota: Ciò non è invece richiesto per un dizionario qualsiasi. Vedremo che vi sono realizzazioni efficienti del tipo astrattodizionario che non richiedono un ordine sulle chiavi.

Dizionari realizzati come alberi di ricerca:confronto fra chiavi di elementi.

Il confronto fra chiavi può essere realizzato in modi diversi:• procedura (in C) o (brutto) metodo statico (Java, C#)

keyOf(E el) che restituisce la chiave dell'elemento el;keyOf(E el) che restituisce la chiave dell elemento el;• metodo di istanza (= non statico) getKey() della classe E

degli elementi, che restituisce la chiave di this;• ...A sua volta il tipo delle chiavi può essere:• un tipo primitivo (come int): il confronto si fa per mezzo


degli operatori <, > e = ;• un tipo di oggetto (come String): in Java il confronto si

deve fare con il metodo compareTo; in C# (come in C++) vi è invece la possibilità dell'overloading degli operatori <, > ,==

7

Dizionari realizzati come alberi di ricerca:confronto fra (chiavi di) elementi.

Le istruzioni di confronto possono quindi avere forme diverse:tKey = keyOf(t->element); //C (progr. non a oggetti)if(key < tKey) ...l if(k )else if(key > tKey) ...else ...

oppure: Java, con interi come chiavi (o C#)nodeKey = node.element.getKey();

o nodeKey = element.getKey();if(key < nodeKey) ...

oppure: Java con oggetti come chiavi


oppure: Java, con oggetti come chiavi confronto = key.compareTo(element.getKey());if(confronto < 0) ...else if(confronto > 0) ...

eccetera.

Alberi di ricerca binariAlberi di ricerca binarinella programmazione non a oggetti

(C, oppure C# usato alla C)


8

Notazione di pseudocodice

Per semplicità chiameremo occasionalmente:• KeyType o Chiave: il tipo delle chiavi• ElemType o Elemento: il tipo degli elementi;ElemType o Elemento: il tipo degli elementi;• keyOf(ElemType el) o chiaveDi(Elemento el): funzione che

restituisce la chiave dell'elemento el;• ARB o BST: il tipo degli alberi di ricerca binari di elementi

di tipo ElemType o Elemento con chiave di tipo KeyType (oChiave)t l t l t t t l d di di t


• t.element: elemento contenuto nel nodo-radice di t;• t.left o t.sinist: sottoalbero sinistro di t;• t.right o t.destr: sottoalbero destro di t.

Esempio: Albero di Ricerca Binario di Studenti in Cfile BST.h

typedef char * string;typedef struct StudentStruct * Student;typedef struct NodeStruct * Tree;yp

int keyOf(Student elem);Student newStudent(int n, string s);void printStudent(Student el);

int isEmpty(Tree t);


void add(Student el, Tree* t);Student find(int key, Tree t);Student remove(int key, Tree* t);void printInord(Tree t);

9

Esempio: ARB di Studenti in C (continua).file BST.c

... #include "BST.h"

struct StudentStruct {i t tint matr;string nome;

};

Student newStudent(int n, string s) {Student pStruct = malloc(...);...

}


}

int keyOf(...) ...

ecc.

Esempio: ARB di studenti in C (continua).Tree newNode(Student el) {Tree pnode = malloc(sizeof(Node));pnode->element = el;pnode->left = NULL;pnode->right = NULL;return pnode;

}

int isEmpty(Tree t) {return t == NULL;

}


}...

10

Esempio: albero di ricerca binario generico in C.file GenBST.h

typedef struct Node* Tree;int isEmpty(Tree t);int isEmpty(Tree t);void* find(int key, Tree t);void add(void* el, Tree * t);void* removeMin(Tree * pt);void* remove(int key, Tree * pt);void printInord(Tree t);


void printInord(Tree t);...

Esempio: albero di ricerca binario generico in C.

file BSTElement.h

int keyOf(void* el);int keyOf(void el);void printElem(void* el);


11

Esempio: albero di ricerca binario generico in C.

file GenBST.c

#include "BSTElement.h"#include "GenBST h"#include "GenBST.h"...// tipo Nodostruct NodeStruct {void* element; Tree left; Tree right;


Tree right;};. . .

Ricerca ricorsiva di un elemento(visione non object-oriented)

Elemento ricerca(Chiave k, ARB t) {if(t è vuoto) return segnalazione elemento non trovato;else if(k < chiaveDi(t.element)) return ricerca(k, t.sinist);f( ( m )) ( , );else if(k > chiaveDi(t.element)) return ricerca(k, t.destr);else return t.element;

}

Si noti che la ricorsione ha due basi:• sottoalbero vuoto,


• sottoalbero con radice l'elemento cercato

12

Dalla ricerca ricorsiva a quella iterativa.Elemento ricerca(Chiave k, ARB t) {

if(t è vuoto) return segnalazione di elemento non trovato;else if(k < chiaveDi(t.element)) return ricerca(k, t.sinist);else if(k > chiaveDi(t.element)) return ricerca(k, t.destr);else return t element;else return t.element;

}Le due chiamate ricorsive sono entrambe di coda e si eliminano facilmente (con un po' di attenzione):Elemento ricerca(Chiave k, ARB t) {

while(t non è vuoto) { // attenzione: while a due uscite !if(k < chiaveDi(t.element)) t = t.sinist;


if(k chiaveDi(t.element)) t t.sinist;else if(k > chiaveDi(t.element)) t = t.destr;else return t.element;

}return segnalazione di elemento non trovato;

}

Esempio: Ricerca iterativa in ARB (di studenti) in CStudent find(int key, Tree t) {int tKey; // usando una variabile in più si evita ogniwhile(t) {// volta il doppio calcolo della chiave del nodo

tKey = keyOf(t->elem);if(key < tKey) t = t->left;else if(key > tKey) t = t->right;else return t->elem;

}return NULL;

} Nota: se l'elemento cercato non esiste,l d l s l stit d il l NULL


la procedura lo segnala restituendo il valore NULL.

Osserva: la ricerca in un albero di ricerca binario assomiglia, non casualmente, alla ricerca binaria in array ordinato;nella versione iterativa il ciclo while a due uscite della ricerca sull'albero è analogo a quello della ricerca in array.

13

Ricerca iterativa con while a una sola uscitaIl while a due uscite è equivalente a un while "regolare" a una sola uscita, avente nel test, come condizione aggiuntiva in AND, la negata della condizione di uscita "irregolare" dal corpo del ciclo:

Elemento ricerca(Chiave k, ARB t) {while(t non è vuoto && k ≠ chiaveDi(t.element)) {

if(k < chiaveDi(t.element)) t = t.sinist;else t = t.destr;

}


}return t è vuoto ? segnalaElementoNonTrovato : t.element

}

Esempio: Ricerca iterativa con while regolare in CPer evitare il doppio calcolo di keyOf(t->element) si può usare il comune "trucco" dell'assegnazione inserita dentro la condizione del while:

Student find(int key, Tree t) {int tKey;while(t && key != (tKey = keyOf(t->element))){if(key < tKey) t = t->left;else t = t->right;

}


return !t ? NULL : t->element;}

14

Esempio: ricerca in ARB generico con chiave int in C

void* find(int key, Tree t) {int tKey;while(t) {tKey = keyOf(t->elem);y y ( )if(key < tKey) t = t->left;else if(key > tKey) t = t->right;else return t->elem;

}return NULL;

}


Esercizio 1 (facilissimo)Scrivere la versione ricorsiva della ricerca in C.

Inserimento di un elemento: definizione ricorsivavoid inser(Elemento el, ARB t) {

if(t è vuoto)modifica t creando un nodo-radice contenente el;

else if(chiaveDi(el) < chiaveDi(t.element)) inser(el, t.sinist);else if(chiaveDi(el) > chiaveDi(t.element)) inser(el, t.destr);else sostituisci t.element con el;

}

La procedura precedente può venire tradotta direttamente in una procedura in un linguaggio di programmazione soltanto se


p g gg p gesso permette il passaggio parametri per riferimento (C, C++, C#, ma non Java), oppure se si sceglie di rappresentare il sottoalbero vuoto non come il valore null (fisicamente = 0) ma come un vero oggetto nodo, di cui viene quindi automaticamen-te passato il riferimento.

15

Es.: inserimento ricorsivo in C# (usato alla Pascal)static void Add(Student elem, ref Tree t) { if(t == null) t = new Tree(elem);else {int key = KeyOf(elem);int tKey = KeyOf(tree elem);int tKey = KeyOf(tree.elem);if(key < tKey) Add(elem, ref t.left);else if(key > tKey) Add(elem, ref t.right);else t.element = elem;;

}}

L'istruzione t = new Tree(elem) modifica proprio la cella


L istruzione t = new Tree(elem) modifica proprio la cella passata come argomento effettivo, non una sua copia locale.

Nota: C#, come Java, non ha i puntatori espliciti: quindi se lo si usa alla Pascal o C i tipi Tree e Node coincidono.

Inserimento ricorsivo in CPoiché in C non esistono i parametri per riferimento, bisogna usare esplicitamente i puntatori e l'operatore-indirizzo:void add(Studente el, Tree * pt) {int key = keyOf(el);int key = keyOf(el);if(*pt) {int tKey = keyOf((*pt)->element);if(key < tKey) add(el, &((*pt)->left));else if(key > tKey) add(el, &((*pt)->right));else (*pt)->element = el;

}


}else *pt = newNode(el);

}

Naturalmente anche in C si può invece scegliere, volendo, la tecnica che useremo in Java (vedi più avanti).

16

Inserimento di un elemento: definizione iterativaNella definizione ricorsiva entrambe le chiamate ricorsive sono di coda, e possono quindi essere eliminate:void inser(Elemento el, ARB t) {

while(t non è vuoto) {if( hi Di( l) hi Di(t l t)) t t i i tif(chiaveDi(el) < chiaveDi(t.element)) t = t.sinist;else if(chiaveDi(el) > chiaveDi(t.element)) t = t.destr;else { sostituisci t.element con el; return; }

} NOTA: ciclo while con due uscite !modifica t creando un nodo contenente el;

} La procedura precedente può venire tradotta direttamente i d i li i di i l


in una procedura in un linguaggio di programmazione soltanto se il linguaggio permette la manipolazione libera di puntatori e indirizzi (C, TurboPascal, ma non Java né C#), oppure se si sceglie di rappresentare il sottoalbero vuoto non come nullma come un vero oggetto nodo. Il solo passaggio-parametri per indirizzo non basta.

Inserimento di un elemento: definizione iterativaPerché il solo passaggio-parametri per indirizzo non basta ?Risposta: Nella versione ricorsiva t è un parametro per riferimento: perciò la chiamata ricorsiva su t left o t rightperciò la chiamata ricorsiva su t.left o t.rightsostituisce non t con t.left o t.right, bensì l'indirizzo di t con l'indirizzo di t.left o t.right.

Ciò non si può fare semplicemente con l'istruzionet = t.left o t = t.right;


occorre avere un operatore-indirizzo.

In C la procedura iterativa si ottiene direttamente da quella ricorsiva per eliminazione manuale della ricorsione di coda.

17

Inserimento iterativo in C.void add(Student el, Tree * pt) {int key = keyOf(el);while(*pt) { ciclo while con due uscite

int tKey = keyOf((*pt)->elem);if(key < tKey) pt = &((*pt)->left);else if(key > tKey) pt = &((*pt)->right);else { (*pt)->elem = el; return; }

} *pt = newNode(el);

}N t il i l hil d it è l ll d ll


Nota: il ciclo while con due uscite è analogo a quello della ricerca e, come quello, può essere trasformato in un while regolare aggiungendo una condizione in AND nel test.Si noti che la procedura funziona perfettamente anche nell'introduzione di un elemento in un albero vuoto.

Inserimento iterativo in Cin dizionario-ARB generico con chiavi intere.

void add(void* el, Tree * pt) {int key = keyOf(el);while(*pt) {( p ) {

int tKey = keyOf((*pt)->elem);if(key < tKey) t = &((*pt)->left);else if(key > tKey) d = &((*pt)->right);else { (*pt)->elem = el; return; }

}*pt = newNode(el);

}


}

Dictionary newNode(void* el) {...

}

18

Inserimento iterativo in C: come avviene.(con sottoalbero vuoto realizzato come valore null)

inserimento di 88 > (*pt)->elem

pt = &((*pt)->right)

null7 null

4pt:

7 null

pt:pt:

4


Inserimento iterativo in C: come avviene.(con sottoalbero vuoto realizzato come valore null)

null non è un oggetto bensì un valore immediato quindi immo-dificabile (come 3 o 5); allora bisogna sostituire il contenuto della cella contenente null.

inserimento di 8

7

*pt = newNode(8) pt:pt:

4


8

19

La cancellazione di un elemento negli ARB.Visione schematica (non object-oriented)

• La cancellazione è la più complessa delle tre operazioni La cancellazione è la più complessa delle tre operazioni fondamentali.

• Utilizza la procedura ausiliaria di estrazione del minimo (o del massimo) di un (sotto)albero (removeMin).


Ricerca e cancellazione del minimo di un (sotto)alberoVersione ricorsiva (programmazione non a oggetti)

Sia T un (sotto)albero non vuoto.Caso base. Il sottoalbero sinistro di T è vuoto:

el

R R

dove = null


Il minimo è l'elemento el contenuto nel nodo radice di T.Il (sotto)albero T' che si ottiene cancellando il minimo è il sottoalbero destro di T.

20

Ricerca e cancellazione del minimoCaso ricorsivo. Il sottoalbero sinistro di T non è vuoto:

Il minimo di T è il minimo del suo sottoalbero sinistro.


Per cancellare il minimo di T si cancella il minimo del suo sottoalbero sinistro.

Ricerca e cancellazione del minimo: vers. ricorsivaElemento estraiMin(ARB t) {

if(t è vuoto) return segnalazione di minimo inesistente;if(t.sinist non è vuoto) return estraiMin(t.sinist);else {{

Elemento min = t.element;sostituisci t con t.destr;return min;

}}La procedura può essere realizzata direttamente nel modo


La procedura può essere realizzata direttamente nel modo descritto soltanto se il linguaggio di programmazione scelto permette il passaggio parametri per riferimento, oppure se il sottoalbero vuoto è rappresentato da un vero oggetto nodo.L'unica chiamata ricorsiva è di coda: può essere eliminata.

21

Ricerca e cancellazione del minimo: vers. iterativaElemento estraiMin(ARB t) {

if(t è vuoto) return segnalazione di minimo inesistente;while(t.sinist non è vuoto) t = t.sinist;Elemento min = t.element;m m m ;sostituisci t con t.destr;return min;

}

Realizzabile direttamente solo se il linguaggio permette la manipolazione di puntatori e indirizzi, oppure se il sottoalbero vuoto è rappresentato da un vero oggetto nodo;


sottoalbero vuoto è rappresentato da un vero oggetto-nodo; altrimenti bisogna considerare separatamente i due casi:• il nodo minimo è una foglia: lo si sostituisce con null;• il nodo minimo ha un figlio destro: esso viene messo al posto

del nodo cancellato (vedi implementazione più avanti).

Cancellazione di un elemento di data chiavein un (sotto)albero. Versione ricorsiva.

Casi Base.• il (sotto)albero T è vuoto: l'elemento da cancellare non c'è;

la chiave nella radice di T è uguale a quella da cancellare:• la chiave nella radice di T è uguale a quella da cancellare:• (almeno) uno dei due sottoalberi di T è vuoto: l'albero

risultante è l'altro sottoalbero;el


R R

Nota: questo caso include anche automaticamente il caso in cui entrambi i sottoalberi di T sono vuoti.

22

Cancellazione di un elemento di data chiavein un (sotto)albero. Versione ricorsiva (continua)

Casi Base (continua)• chiave in radice di T uguale a quella da cancellare (continua)

bi i lb i di T i• entrambi i sottoalberi di T sono non vuoti:si cancella il minimo nel sottoalbero destro di T e lo si mette nella radice di T.


L R

Cancellazione di un elemento di data chiavein un (sotto)albero. Versione ricorsiva (continua)

Caso ricorsivo. La chiave nella radice di T non è uguale alla chiave k (dell'elemento) da cancellare.Si cancella l'elemento di chiave k nel sottoalbero sinistro o Si cancella l elemento di chiave k nel sottoalbero sinistro o destro di T, a seconda che k sia minore o maggiore della chiave dell'elemento nella radice di T.


23

Cancellazione di un elemento di data chiave in un (sotto)albero: v. ricorsiva (per semplicità senza restituzione dell'elemento)void cancella(Chiave k, ARB t) {

if(t è vuoto) azione per chiave inesistente;else {

if(k < chiaveDi(t element)) cancella(k t sinist);if(k < chiaveDi(t.element)) cancella(k, t.sinist);else if (k > chiaveDi(t.element)) cancella(k, t.destr);else {if(t.sinist è vuoto) sostituisci t con t.destr;else if(t.destr è vuoto) sostituisci t con t.sinist;else t.element = estraiMin(t.destr);

}}


}}

realizzabile direttamente soltanto se il linguaggio ammette iparametri per riferimento, oppure se si rappresenta il sotto-albero come un vero oggetto nodo; altrimenti è sconsigliabile.

Cancellazione di un elemento in un (sotto)albero:versione iterativa

void cancella(Chiave k, ARB t) { while(t non è vuoto && k ≠ chiaveDi(t.element)) {

if(k < chiaveDi(t.element)) t = t.sinist;else if(k > chiaveDi(t element)) t = t destr;else if(k > chiaveDi(t.element)) t = t.destr;

}if(t è vuoto) azione per chiave inesistenteelse {

if(t.sinist è vuoto) sostituisci t con t.destr;else if(t.destr è vuoto) sostituisci t con t.sinist;else t.element = estraiMin(t.destr);

}


}}Realizzabile direttamente solo se il linguaggio permette la manipolazione di puntatori e indirizzi, oppure se il sottoalbe-ro vuoto è rappresentato da un oggetto-nodo.

24

Esercizio 2• Si scriva in C la procedura di cancellazione di un elemento

in un albero di ricerca, sia in versione ricorsiva che in versione iterativa.


Alberi di ricerca binariAlberi di ricerca binarinella programmazione a oggetti (Java)


25

ARB nella programmazione a oggetti: introduzione.

• Sia in C# che in Java è conveniente definire, come per qualunque albero binario, una classe-Nodo annidata nella classe-AlberoDiRicerca.

• La classe-Nodo annidata corrisponde al tipo-Albero del C.• La classe-AlberoDiRicerca circondante contiene solo il

puntatore alla radice.• I sottoalberi (nodi) vuoti possono essere rappresentati da:

• il valore null: efficiente in spazio e anche in tempo (un livello in meno di ricorsione); ma con certi linguaggi e certe scelte realizzative la scrittura di alcune procedure è molto complessa (es cancellazione ricorsiva);


è molto complessa (es. cancellazione ricorsiva);• speciali oggetti nodi-vuoti: elimina la difficoltà prece-

dente permettendo la scrittura di metodi concisi ed eleganti, a prezzo di una maggiore occupazione di memoria (e di un livello in più di ricorsione).

Alberi di ricerca binarinella programmazione a oggetti (Java):

versione con (sotto-)alberi vuoti rappresentati dalla costante null.


26

ARB nella programmazione a oggetti.Realizzazione ricorsiva dei metodi.

• In essa si definiscono in modo ricorsivo i metodi di ricerca, inserimento e cancellazione, che agiscono sul nodo this e sui suoi sotto-alberi, e non sono visibili dall'esterno.suoi sotto alberi, e non sono visibili dall esterno.

• Nella classe circondante AlberoDiRicerca si pone un campo-radice di tipo Nodo, e vi si definiscono i metodi pubblici di ricerca, inserimento e cancellazione: ognuno di essi deve trattare direttamente il caso della radice nulla, e in caso contrario deve invocare sulla radice il suo omonimo metodo della classe Nodo.


Ricerca object-oriented ricorsiva,con sottoalbero vuoto rappresentato da null

Nella classe Node:poiché ovviamente this non può essere null, la base della ricorsione, per il caso in cui l'elemento non si trova, non può p pessere il sottoalbero vuoto, ma deve essere il genitore del sottoalbero vuoto. ElemType find(int key) {int thisKey = element.getKey();if(key < thisKey)return left == null ? null : left.find(key);


else if (key > thisKey)return right== null? null : right.find(key);

else return element; }

27

Ricerca object-oriented ricorsiva,con sottoalbero vuoto rappresentato da null

Nella classe BinSearchTree:

ElemType find(int key) {yp ( y) {return root == null ? null : root.find(key);

}


Inserimento object-oriented ricorsivo,con sottoalbero vuoto rappresentato da null

Nella classe-Nodo:Anche qui, poiché this non può essere null, la base della ricorsione si ha nel genitore del sottoalbero vuoto.

id i i i(El l) {void inserisci(Elemento el) {if(chiaveDi(el) < chiaveDi(t.element)) {if(sinist == null) sinist = new Nodo(el);else sinist.inserisci(el);

}else if(chiaveDi(el) > chiaveDi(t.element)) {if(destr == null) destr = new Nodo(el);


if(destr == null) destr = new Nodo(el);else destr.inserisci(el);

}else element = el;

}

28

Inserimento object-oriented ricorsivo,con sottoalbero vuoto rappresentato da null

Nella classe AlberoDiRicerca o BinSearchTree:

public void inserisci(Elemento el) {if( di ll) di N d ( l)if(radice == null) radice = new Nodo(el);else radice.inserisci(el);

}

La traduzione in Java o in C# dei due metodi precedenti è immediata: basta tradurre i confronti, utilizzando dei temporanei per non ricalcolare i valori delle chiavi o – se si

l l l f


usa compareTo – il risultato del confronto.

Esercizio 3 (facilissimo):scrivere i metodi in Java e completare la classe AlberoDiRicerca (o ABR, o BinSearchTree, ecc.).

Cancellazione object-oriented ricorsiva,con sottoalbero vuoto rappresentato da null

Realizzabile facilmente soltanto se il linguaggio ammette iparametri per riferimento, oppure se si rappresenta il sotto-albero come un vero oggetto nodo; altrimenti è sconsigliabilealbero come un vero oggetto nodo; altrimenti è sconsigliabile.


29

ARB nella programmazione a oggetti.Realizzazione iterativa dei metodi.

Le procedure di ricerca, inserimento e cancellazione vengono realizzate direttamente come metodi pubblici della classe realizzate direttamente come metodi pubblici della classe Albero, senza metodi omonimi nella classe Nodo.Il metodo iterativo di ricerca risulta così quasi identico a quello della versione tradizionale non a oggetti. I metodi iterativi di inserimento e cancellazione, invece, in Java e C# risultano più complessi che nella concisa versione C poiché l'assenza dei puntatori espliciti obbliga per modi-


C, poiché l assenza dei puntatori espliciti obbliga, per modi-ficare un campo sinist o destr, ad accedere all'intero nodo che lo contiene.

Ricerca object-oriented iterativa,con sottoalbero vuoto rappresentato da null

Nella classe BinSearchTree (in Java):public ElemType find(int key) {p yp ( y) {

Node node = root;while(node != null) {int nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else return node.element;


}return null;

}

30

Inserimento object-oriented iterativo,con sottoalbero vuoto rappresentato da null (1)

Il ciclo while (a due uscite) è simile a quello della ricerca:while(node != null) {...int nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else {node.element = el; return;}

}Se si esce dal ciclo regolarmente, cioè per node == null,


per poter effettuare l'inserimento bisogna accedere algenitore del nodo nullo; nel ciclo occorre quindi percorrere il ramo dell'albero tenendo due "puntatori": cioè, oltre al nodo corrente, anche il suo genitore (vedi slide seguente).


Il ciclo while (a due uscite) è simile a quello della ricerca:while(node != null) {parent = node; // aggiorna ogni volta il genitorep ; // gg g gint nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else {node.element = el; return;}

}Se si esce dal ciclo regolarmente, cioè per node == null,


per poter effettuare l'inserimento bisogna accedere algenitore del nodo nullo; nel ciclo occorre quindi percorrere il ramo dell'albero tenendo due "puntatori": oltre al nodo corrente, anche il genitore.

31


Il ciclo while (a due uscite) è simile a quello della ricerca:while(node != null) {

parent = node;p ;nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else {node.element = el; return;}

}Dopo l'uscita regolare dal ciclo occorre rifare l'ultimo test


per stabilire dove va inserito il nuovo nodo, se a sinistra o a destra:if(key < nodeKey) parent.left = new Node(el);else parent.right = new Node(el);


Il int nodeKey; Node parent; Node node = root;while(node != null) {parent = node;p ;int nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else {node.element = el; return;}

}if(key < nodeKey) parent.left = new Node(el);


else parent.right = new Node(el);Il nodo corrente node va ovviamente inizializzato alla radice.Le variabili nodeKey e parent, essendo utilizzate anche dopo l'uscita dal while, devono essere dichiarate anch'esse fuori dal ciclo.

32


La procedura scritta finora però non funziona nel caso in cui la radice sia null, perché allora il puntatore al nuovo nodo va messo nel campo root dell'oggetto-tree, e non in un campo p gg , pleft o right di un nodo.È il classico "problema del primo elemento", che deve essere trattato con un'istruzione specifica posta in un if-else:if(root == null) root = new Node(el);else {...Node node = root;


Node node = root; while(node != null) { ...

Ma allora il test del while la prima volta è certamente true, il corpo del ciclo viene eseguito almeno una volta, e quindi con-viene spostare il test alla fine del corpo, usando un do-while.


public void add(ElemType el) {if(root == null) root = new Node(el);else {int key = el.getKey();i t d Kint nodeKey;Node parent; Node node = root; do { // ciclo a due uscite

parent = node;nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else {node element = el; return;}


else {node.element el; return;}} while(node != null);if(key < nodeKey) parent.left = new Node(el);else parent.right = new Node(el);

}} Come si vede, è una procedura più complessa che la versione C o C#.

33

Inserimento di un elemento: versione iterativa JavaSottoalbero vuoto realizzato come valore null

null non è un oggetto bensì un valore immediato quindi immo-dificabile (come 3 o 5); allora bisogna sostituire il contenuto della cella contenente null, cioè bisogna modificare il nodo

it ( t)genitore (parent).Modificando node si modifiche-rebbe solo una variabile locale; bisogna modificare parent.right

null

node:nullparent:


el

Un'altra versione dell'inserimento iterativo in Java, equivalente alla precedente.

• Come si è visto, la scrittura del ciclo in modo che non abbia uscite "irregolari" è piuttosto innaturale. Allora si può adottare la soluzione radicale di scrivere un ciclo che abbia adottare la soluzione radicale di scrivere un ciclo che abbia solo uscite irregolari, ma al momento giusto.

• Inoltre, invece di tenere un genitore corrente, si può fermare l'iterazione un passo prima.

• Si ottiene così una procedura lievemente più prolissa ma non meno (anzi, forse più) efficiente, e non meno elegante (non ripete l'ultimo test non ha bisogno di due puntatori)


(non ripete l ultimo test, non ha bisogno di due puntatori).

34

Un'altra versione (continuazione)Continua a ripetere la seguente sequenza di istruzioni:• se chiave da inserire < chiave del nodo corrente:

• se il figlio sinistro non è nullo,il nodo corrente diventa il figlio sinistro;

l f l è ll f l • se il figlio sinistro è nullo, crea un nuovo figlio sinistro con la nuova chiave, poi termina;

• se chiave da inserire > chiave del nodo corrente:• se il figlio destro non è nullo,

il nodo corrente diventa il figlio destro;• se il figlio destro è nullo, crea un nuovo figlio destro con

la nuova chiave poi termina;


la nuova chiave, poi termina; • se chiave da inserire = chiave del nodo corrente:

sostituisci l'elemento nel nodo corrente con quello nuovo,poi termina.

Un'altra versione: il codice.public void add(ElemType el) { if(root == null) root = new Node(el);else { int key = el.getKey(); Node node = root;

while(true) {int nodeKey = node element getKey();int nodeKey = node.element.getKey();

if(key < nodeKey) {if(node.left != null) node = node.left;else {node.left = new Node(el); return;}

}

else if(key > nodeKey) {if(node.right != null) node = node.right;else {node.right = new Node(el); return;}


}

else {node.element = el; return;}}

}}

35

Cancellazione di un elemento in un (sotto)albero:ripartiamo dalla versione astratta iterativa

void cancella(Chiave k, ARB t) { while(t non è vuoto && k ≠ chiaveDi(t.element)) {

if(k < chiaveDi(t.element)) t = t.sinist;l if(k hi Di( l )) delse if(k > chiaveDi(t.element)) t = t.destr;

}if(t è vuoto) azione per chiave inesistenteelse {

if(t.sinist è vuoto) sostituisci t con t.destr;else if(t.destr è vuoto) sostituisci t con t.sinist;else t element = estraiMin(t destr);


else t.element = estraiMin(t.destr);}

}

Cancellazione iterativa in Java con albero vuoto nullprivate ElemType removeMin(Node parent, Node node) {elimina, restituendone il valore, il minimo del sottoalbero di radice node, se parent è il genitore di node. PREcondizione per l'invocazione: parent != null, node != root.while(node.left != null) {parent = node;node = node.left; scende a sinistra finché possibile

}

ElemType min = node.element;parent.left = node.right;return min; removeMin


}

-

parent:

node:

metodo privatoausiliario

36

Cancellazione iterativa in Java con albero vuoto nullUna (fra le tante) possibile soluzioni, abbastanza compatta, ma comunque complessa:

public void remove(int key) {Node parent;Node parent;Node node = root;parent = null;int nodeKey;while(node != null && key != (nodeKey= node.element.getKey())){

parent = node;if(key < nodeKey) node = node.left;


else node = node.right;}

all'uscita dal while node è nullo, oppure node punta al nodo da eliminare e parent è il suo genitore.

Cancellazione iterativa in Java con albero vuoto nullif(node == null) return; la chiave da eliminare non c'è

// node è il nodo da eliminare:if(node.left == null || node.right == null) {

// il nodo da eliminare ha al più UN figlio non nullo:p gNode onlyChild = // fratello di un figlio nullo

node.left == null ? node.right: node.left; // onlyChild è il figlio da "tirare in su":

if(node == root) root = onlyChild;// caso della radiceelse if(node == parent.left)parent.left = onlyChild;else parent.right = onlyChild;

} // nota: onlyChild può anche essere nullo funziona ugualmente


} // nota: onlyChild può anche essere nullo, funziona ugualmenteelse // il nodo da eliminare ha due figli non nulli:

node.element = removeMin(node, node.right);estrae il minimo del figlio destro, e lo mette nel nodo:

} Nota: la precondizione per la chiamata di removeMin, cioè node != null, è sempre soddisfatta.

37

La procedura in una sola paginapublic void remove(int key) {

Node parent;Node node = root;parent = null;int nodeKey;

while(node != null && key != (nodeKey = node.element.getKey())) {parent = node;if(key < nodeKey) node = node.left;else node = node.right;

}

if(node == null) return;

if(node.left == null || node.right == null) {Node onlyChild = node left == null? node right : node left;


Node onlyChild = node.left == null? node.right : node.left;if(node == root) root = onlyChild;else if(node == parent.left) parent.left = onlyChild;else parent.right = onlyChild;

}else node.element = findAndRemoveMin(node, node.right);

}

Nota

• La procedura precedente è abbastanza più complicata della descrizione astratta dell'algoritmo, pur essendone sempli-cemente la realizzazione.

• La complicazione dipende più che dall'algoritmo in sè dalle • La complicazione dipende, più che dall algoritmo in sè, dalle caratteristiche del linguaggio e dal modo in cui si è scelto di rappresentare in memoria la struttura-dati.

• Esercizio 4: Definire nella classe BinSearchTree, utilizzando il metodo privato removeMin visto nelle slides precedenti, un metodo pubblico

El T Mi ()


ElemType removeMin()

il quale restituisca, e contemporaneamente elimini, l'elemento minimo dell'intero albero.

38

Alberi di ricerca binarinella programmazione a oggetti (Java):

versione con (sotto-)alberi vuoti rappresentati da speciali oggetti.


Realizzazioni con nodo vuoto come oggetto fittizio.

• Per poter trattare in modo uniforme sottoalberi non-vuoti e vuoti si può scegliere di rappresentare i sottoalberi vuoti per mezzo non del valore null, ma di nodi speciali "vuoti". Così "oggettiviamo" il valore nullCosì oggettiviamo il valore null.

• Tale tecnica può venire adottata sia nella programmazione a oggetti che nella programmazione imperativa tradizionale; tuttavia in C la presenza dell'operatore-indirizzo '&' e dei puntatori espliciti permette già, come abbiamo visto, tale trattamento uniforme in modo conciso ed elegante.Vi t t i di l' d ll' tt t l l


• Viene presentato quindi l'uso dell'oggetto vuoto solo per la programmazione in Java.

39

Realizzazioni con l'oggetto fittizio "nodo vuoto".La classe annidata Node.

public class BinSearchTree {private class Node {...Node() { // costruttore di nodo vuoto

element = null; left = right = null;

}in realtà le inizializzazioni a null dei tre campi sono superflue perché effettuate automaticamente da Java; ma non è male scriverle, per la comprensione del programma.


, p mp p g mm

boolean isEmpty() {return left == null && right == null;

}...

La classe Node con oggetto fittizio "nodo vuoto":metodi ausiliari.

• Per inserire un nuovo elemento ora non si deve più sostituire un valore null con un puntatore ad un nuovo nodo; si tratta invece di sostituire il nodo vuoto con un nodo non vuoto.invece di sostituire il nodo vuoto con un nodo non vuoto.

• Ma allora, poiché comunque un nodo c'è già, è più facile e più conveniente modificare il nodo vuoto "riempiendolo" con il nuovo dato, e creando come suoi figli due nuovi nodi vuotiper mantenere coerente la rappresentazione.

• A tal fine è utile definire nella classe-Nodo un metodo ausiliario che modifica il nodo this trasformandolo in una


ausiliario che modifica il nodo this trasformandolo in una foglia non vuota (con due figli vuoti).

• Inoltre saranno utili anche metodi ausiliari più generali di modifica del nodo this.

40

Classe Node: metodi ausiliari.Trasforma this in una foglia non vuota:void setToLeaf(ElemType elem) {element = elem;left = new Node(); Nota Bene: ogni nuovo vuotoright = new Node(); deve essere fisicamente right = new Node(); deve essere fisicamente

} distinto dagli altri.Rende this uguale al nodo-argomento node:void setTo(Node node) {element = node.element;left = t.left;right = t.right;


g g}

Cambia separatamente i campi di this:void setTo(ElemType elem, Node l, Node r) {

...

Inizializzazione della classe BinSearchTreepublic class BinSearchTree {private class Node {...

}...// costruttore della classe BinSearchTreepublic BinSearchTree() {root = new Node();

}


...}

41

ARB con oggetto fittizio "nodo vuoto": realizzazione ricorsiva.

• Come al solito, è naturale definire i metodi ricorsivi nella classe-Nodo, e porre nella classe-Albero i corrispondenti metodi pubblici che li richiamano.p

• La presenza del nodo vuoto permette nella classe-Nodo la ricorsione con base la foglia nulla come in C, quindi più semplice ed elegante anche se un po' più inefficiente (più chiamate ricorsive).

• La presenza del nodo vuoto permette di trattare il caso della radice vuota in modo uniforme rispetto agli altri: così,


f p g ,per ognuna delle operazioni principali, il metodo pubblico nella classe-Albero non deve più fare alcun controllo, ma semplicemente invocare il corrispondente metodo ricorsivo della classe-Nodo.

Es.: inserimento ricorsivo in ARB con nodo vuotoNella classe Node:void add(ElemType el) {

if(isEmpty()) setToLeaf(el);else {int key = el getKey();int key = el.getKey();int thisKey = element.getKey(); if(key < thisKey) left.add(el);else if(key > thisKey) right.add(el);else element = el;

}}


Nella classe BinSearchTree:public void add(ElemType el) {root.add(el);

}Esercizio 5: definire i metodi per la ricerca ricorsiva.

42

ARB con nodo vuoto: realizzazione iterativa.

• Come nella realizzazione iterativa senza nodo fittizio vuoto, le procedure di ricerca, inserimento e cancellazione vengono realizzate direttamente come metodi pubblici della classe albero senza metodi omonimi nella classe nodoclasse- albero, senza metodi omonimi nella classe-nodo.

• Poiché sia inserimento che cancellazione consistono in una ricerca della posizione del nodo, e d'altra parte ora non serve più il riferimento al genitore, è conveniente definire un metodo ausiliario di ricerca-nodo che restituisce il if i t l d t t (i d ll' l t ) I t


riferimento al nodo trovato (invece dell'elemento). I tre metodi principali poi richiamano tale metodo.

ARB con nodo vuoto: realizzazione iterativa.Il metodo di ricerca-nodo

private Node findNode(int key) {Node node = root;while(!node isEmpty()) {while(!node.isEmpty()) {

int nodeKey = node.element.getKey();if(key < nodeKey) node = node.left;else if(key > nodeKey) node = node.right;else return node; // oppure break;} return node;


;}

Nota: se non si trova un elemento con la chiave cercata, viene restituito il nodo vuoto.

43

ARB con nodo vuoto: realizzazione iterativa.I metodi di ricerca e inserimento di elemento.

public ElemType find(int key) {Node node = findNode(key);return node.element;

}Nota: se ElemType è un tipo di oggetto, quando la chiave cercata non si trova, viene restituito il valore null, che è contenuto nel campo element del nodo vuoto.

public void add(ElemType el) {


Node node = findNode(el.getKey());if(node.isEmpty()) node.setToLeaf(el);else node.element = el;

}(se la chiave cercata c'è già, può non essere in una foglia)

Inserimento di un elemento: versione iterativaSottoalbero vuoto realizzato come oggetto

Si esce dal ciclo quando node è il sottoalbero vuoto:

node: node:

vuoto

node: node:

el

vuoto vuoto


La variabile node, locale del metodo findNode (e che quindi si trova sullo stack), contiene un riferimento al nodo vuoto; tale nodo si può quindi modificare, trasformandolo in un nodo che contiene l'elemento da inserire.

44

Riassumendo (1):• Le tre operazioni fondamentali di un albero di ricerca

binario – ricerca, inserimento e cancellazione – ammettono delle semplici definizioni induttive, corrispondenti a procedure ricorsive.

• Data la natura "dicotomica" di un albero di ricerca binario, tali procedure sono tutte e tre ricorsive di coda, e possono quindi essere trasformate in procedure iterative.

• La ricerca, non modificando l'albero, può essere realizzata in modo sia ricorsivo che iterativo in qualunque linguaggio di


modo sia ricorsivo che iterativo in qualunque linguaggio di programmazione traducendo direttamente la definizione induttiva (versione ricorsiva) ed eventualmente eliminando la ricorsione di coda (versione iterativa).

Riassumendo (2):• Inserimento e cancellazione, che modificano l'albero,

possono venire realizzate con semplice traduzione diretta della definizione induttiva (ed eventuale eliminazione della ricorsione di coda) soltanto se:

• versione ricorsiva:versione ricorsiva• il linguaggio ammette i parametri per riferimento;• oppure si rappresentano i nodi vuoti come oggetti;

• versione iterativa:• il linguaggio ammette la manipolazione di puntatori e

indirizzi (C, TurboPascal);• oppure si rappresentano i nodi vuoti come oggetti.


Rappresentare i nodi vuoti come oggetti permette un analogodel passaggio di null per riferimento.Con tale rappresentazione inserimento e cancellazione, siaricorsivi che iterativi, si realizzano molto semplicemente pertraduzione diretta delle loro definizioni astratte.

45

Esercizio 6 (con carta e matita).• Si modifichi l'algoritmo di inserimento in modo che esso

restituisca l'eventuale vecchio elemento con la stessa chiave presente nel dizionario, oppure null se la nuova chiave inserita non era ancora presente (vedi slides su specifica del tipo astratto dizionario)

• Si modifichi l'algoritmo di cancellazione in modo che esso restituisca l'elemento cancellato, oppure null se non si trova un elemento da cancellare.


Esercizio 7 (di implementazione).Si implementi l'operazione di cancellazione, in almeno uno deidue modi seguenti, che sono quelli di più facile realizzazione:

• versione iterativa in C, usando i puntatori e l'operatore &;ElemType removeMin(Tree * t) void remove(int key, Tree * t)

• versione iterativa in Java con nodo fittizio vuoto(si può sfruttare il metodo findNode):

ll l Bi S hT


nella classe BinSearchTreeprivate ElemType removeMin(Node node)public void remove(int key)

46

Esercizio 8 (di implementazione).Si implementi l'operazione di cancellazione nella• versione ricorsiva in Java con nodo fittizio vuoto.

Nota: Tale implementazione potrà servire da base per la Nota: Tale implementazione potrà servire da base per la realizzazione della cancellazione negli alberi AVL.


Algoritmi e Laboratorio a.a. 2009-10 Lezionielio/DIDATTICA/aa0910/AlgELab/slides/lez34-albe... ·...

Documents

Transcript of Algoritmi e Laboratorio a.a. 2009-10 Lezionielio/DIDATTICA/aa0910/AlgELab/slides/lez34-albe... ·...