Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Soluzione esercizio di approfondimento Fornire un’implementazione alternativa dell’operazione di merge(CodaPriorità c1, CodaPriorità c2), analizzandone la convenienza asintotica rispetto all’implementazione appena fornita (di costo (n)). Soluzione: Sia k=min{|c1|,|c2|}. Inseriamo ad uno ad uno tutti gli elementi della coda più piccola nella coda più grande; questo costa O(k log n), dove n=|c1|+|c2|. L’approccio conviene quindi per k log n=o(n), cioè per k=o(n/log n). 1 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e Strutture Dati Capitolo 6 Il problema del dizionario Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Il tipo dato Dizionario Suppongo sempre che mi venga dato un riferimento diretto all’elemento da cancellare Applicazioni: gestione archivi di dati 3 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Implementazioni elementari Search Insert Delete O(n) O(1) O(1) Array ordinato O(log n) O(n) O(n) Lista non ordinata O(n) O(1) O(1) Lista ordinata O(n) O(n) O(1) Array non ord. 4 Ognuno dei 4 metodi banali costa O(n). Voglio fare meglio… Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Lower bound (log n) per la ricerca • Consideriamo l’albero di decisione di un qualsiasi algoritmo che risolve il problema della ricerca in un insieme di n elementi tramite confronti • L’albero deve contenere almeno n+1 foglie • Un albero binario con k foglie in cui ogni nodo interno ha esattamente due figli, ha altezza h(k) almeno log k (vedi lezione n. 6) L’altezza h dell’albero di decisione è (log n). Il metodo di ricerca per dimezzamenti successivi è ottimale! 5 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Alberi binari di ricerca (BST = binary search tree) 6 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Definizione Albero binario che soddisfa le seguenti proprietà: – ogni nodo v contiene un elemento elem(v) cui è associata una chiave chiave(v) presa da un dominio totalmente ordinato, nonché un puntatore al padre, un puntatore al figlio sinistro e un puntatore al figlio destro – le chiavi nel sottoalbero sinistro di v sono < chiave(v) – le chiavi nel sottoalbero destro di v sono > chiave(v) 7 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Esempi ! Albero binario di ricerca 8 Albero binario non di ricerca Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Visita simmetrica di un BST • Visita in ordine simmetrico – dato un nodo x, elenco prima il sotto-albero sinistro di x (in ordine simmetrico), poi il nodo x, poi il sotto-albero destro di x (in ordine simmetrico) Inorder-tree-walk(node x) If (x NULL) then Inorder-tree-walk(left[x]) stampa key[x] Inorder-tree-walk(right[x]) • Inorder-tree-walk(radice del BST) visita tutti i nodi del BST • Analisi complessità: la complessità della procedura considerata è T(n) = (n). Infatti: T(n) = T(n') + T(n'') + O(1) 9 con n'+n''=n-1 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Proprietà della visita simmetrica di un BST Inorder-tree-walk(radice del BST) visita i nodi del BST in ordine crescente rispetto alla chiave! Verifica: Indichiamo con h l’altezza dell’albero. Per induzione sull’altezza dell’ABR: Base (h=0): banale (il BST consiste di un unico nodo); Passo induttivo (h generico): ipotizzo che la procedura sia corretta per h-1 r Albero di altezza < h-1. Tutti i suoi elementi sono minori della radice 10 Albero di altezza < h-1. Tutti i suoi elementi sono maggiori della radice Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Esempio 15 6 3 18 7 17 20 massimo 2 13 4 minimo 9 11 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano search(chiave k) -> elem Traccia un cammino nell’albero partendo dalla radice: su ogni nodo, usa la proprietà di ricerca per decidere se proseguire nel sottoalbero sinistro o destro 12 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano search(7) 15 6 3 2 13 20 8 4 7 17 13 16 27 19 22 30 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano Confronto con la ricerca binaria • La complessità della procedura di ricerca considerata è T(n) = O(h), ove h è l’altezza del BST. • Nell’esempio precedente, il BST era completo, e quindi h=Θ(log n) • Per le proprietà del BST, quando esso è completo, per ogni nodo v la chiave associata è l’elemento mediano nell’insieme ordinato delle chiavi associate all’insieme di nodi costituiti dal sottoalbero sinistro di v, da v, e dal sottoalbero destro di v Ad ogni discesa di livello, dimezzo lo spazio di ricerca, in modo analogo a quanto avveniva per l’array ordinato!! … ma un BST non sempre è completo… 14 Copyright © 2004 - The McGraw - Hill Companies, srl Algoritmi e strutture dati Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano 30 …anche questo è un BST!! 22 27 20 19 17 16 15 ... 2 15 Notare: T(n) = O(h) in entrambi i casi, però: BST completo h = (log(n)) BST “linearizzato” h = (n) Copyright © 2004 - The McGraw - Hill Companies, srl