Algoritmi e strutture dati

HEAP 1. L'albero deve essere completo fino al penultimo livello e gli elementi dell'ultimo livello devono essere inseriti da sinistra verso destra. 2. In una max heap: il padre deve essere sempre più grande dei suoi figli, il massimo sta nella radice e una max heap è ordinata come un vettore decrescente. 3. In una min heap: il padre deve essere sempre più piccolo dei suoi figli, il minimo sta nella radice e una min heap è ordinata come un vettore crescente. TABELLE DI HASH Ci sono due metodi che permettono di risolvere il problema delle collisioni nelle tabelle di Hash: 1. Hashing con Chaining : a. inserimento = O(1); b. cancellazione (n); c. ricerca (n) o (1, dove = n/m. L'hashing con chaining usa una struttura dati del tipo Linked List. Le linked List possono essere: 1. Singled Linked: a. Ricerca O() b. Cancellazione (n) c. Inserimento (n) 2. Double Linked: a. Ricerca O() b. Cancellazione (1) c. Inserimento (1) 2. Open Adressing a. Con Linear Probing hk,i) = k+i) mod m) b. Con Quadratic Probing hk,i) = (h(k) + c1i + c2i2 ); dove h(k) = (k mod m). Con la tecnica dell'Open Adressing cancellazione, inserimento e ricerca hanno un costo pari a O(n) 3. Con scansione Doppia a. Hk,i) = (h1(k) + h2(k)i) ALBERI BINARI C B D A F G 1. Vista pre-ordine = T(n) = O(n), la radice la metto per prima [ C D A B F G] 2. Post-ordine = T(n) = O(n), la radice la metto alla fine [ A D F G B C] 3. In-visita = T(n) = O(n), la radice la metto in mezzo [ D A C F B G] ALBERI BINARI DI RICERCA Negli alberi binari di ricerca : 1. Il minimo scende sempre a sinistra 2. il massimo scende sempre a destra Caso Peggiore L'albero è completamente sbilanciato T(n) = O(n) Caso Migliore L'albero è completo T(n) = (log n) Search Nel caso migliore quando devo ricercare la radice ha complessità (1). Nel caso peggiore ha complessità O(n). Inserimento T(n) = O(n) Cancellazione T(n) = O (n) 1. se il nodo da cancellare non ha figli lo cancello direttamente 2. se il nodo ha un figlio destro o uno sinistro allora sostituisco il nodo cancellato col figlio che ha. 3. se il nodo che devo cancellare ha entrambi i figli, il nodo cancellato va sostituito col suo successore immediato. Successore 1. Se Z ha il figlio destro scendo nel sotto albero di sinistra fino a che posso 2. Se Z non ha figlio destro ed è il figlio destro scelgo e vado a vedere negli avi il primo figlio sinistro 3. Se Z non è figlio destro e non ha figli il successore è il padre. A B 60 60 10 10 Z 15 15 13 25 19 26 10 è il primo figlio sinistro quindi il successore di 25 è il 60 13 25 Z 19 Successore Continua »