|
|
Capitolo 6 Il problema del dizionario Algoritmi e Strutture Dati
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Il tipo dato Dizionario Suppongo sempre che mi venga dato un riferimento diretto all’elemento da cancellare Applicazioni: gestione archivi di dati
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Implementazioni elementari Search Insert Delete Array non ord. 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) Ognuno dei 4 metodi banali costa O(n). Voglio fare meglio…
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 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) log k (vedi lezione n. 6)
L’altezza h dell’albero di decisione è (log n).
Il metodo di ricerca per dimezzamenti successivi è ottimale!
Lower bound W(log n) per la ricerca
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Alberi binari di ricerca
(BST = binary search tree)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 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)
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Albero binario di ricerca Esempi Albero binario non di ricerca !
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 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) con n'+n''=n-1
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 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
Proprietà della visita simmetrica di un BST r Albero di altezza < h-1. Tutti i suoi elementi sono minori della radice Albero di altezza < h-1. Tutti i suoi elementi sono maggiori della radice
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * Esempio 15 6 18 3 7 17 20 2 4 13 9 massimo minimo
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 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
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 15 6 20 3 8 17 27 2 4 13 7 16 19 22 search(7) 30
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 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…
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 15 20 17 27 16 19 30 22 ... …anche questo è un BST!! Notare: T(n) = O(h) in entrambi i casi, però:
BST completo h = (log(n))
BST “linearizzato” h = (n) 2
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * insert(elem e, chiave k) Crea un nuovo nodo u con elem=e e chiave=k
Cerca la chiave k nell’albero, identificando così il nodo v che diventerà padre di u
Appendi u come figlio sinistro/destro di v in modo che sia mantenuta la proprietà di ordinamento totale
La complessità della procedura considerata è T(n) = O(h), ove h è l’altezza del BST
|
|
|
|
|
Copyright © 2004 - The McGraw - Hill Companies, srl * 15 6 18 3 9 17 20 2 4 13 10 7 insert(e,8) Se seguo questo schema l’elemento e viene posizionato nella
posizione giusta. Infatti, per costruzione, ogni antenato di e si ritrova e nel giusto sottoalbero.
8
|
|
|
|
|
|
Comments