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