Che materia stai cercando?

Algoritmi - Ordinamento, strutture dati, alberi, code di priorità e tabelle hash

Algoritmi e semplici spiegazioni di come essi operano e delle loro caratteristiche riguardanti:
- Ordinamento: InsertionSort, MergeSort, QuickSort, CountingSort, RadixSort, BucketSort, DeterministicSelection
- Strutture dati: pile, code, liste (array list e linked list)
- Alberi: alberi binari, alberi binari di ricerca, AVL, alberi red-black
- Code di priorità: heap (caratteristiche,... Vedi di più

Esame di Algoritmi e strutture dati docente Prof. M. Pinotti

Anteprima

ESTRATTO DOCUMENTO

Alberi binari

- Possono essere:

• propri: ogni nodo interno ha esattamente 2 figli (d’ora in poi solo questi)

• impropri: ogni nodo interno ha al più 2 figli

- Operazioni:

• leftChild(v)

• rightChild(v)

• sibling(v): fratello

- Proprietà: n = num. nodi, e = nodi esterni, i = nodi interni, h = altezza

• e = i + 1

• n = 2e – 1

• h <= i

• h <= (n – 1) / 2

• h

e <= 2

• h >= log e

2

• h >= log (n + 1) – 1

2

- Visita inorder: miscuglio fra preorder e postorder, visita i nodi da sx a dx

inOrder(T, v)

if leftChild(v) != null then

inOrder(T, leftChild(v))

visit v

if rightChild(v) != null then

inOrder(T, rightChild(v))

Tutte le visite impiegano O(n)

- Implementazione

1. Linked Structure: ogni nodo è rappresentato da 4 campi: uno per il valore, uno

per il padre, 2 per i figli

2. Array: la visita avviene per livelli (FIFO). Il nodo v è in A[rank(v)]:

• rank(root) = 0

• se node è figlio sx: rank(node) = 2 * rank(parent(node)) + 1

• se node è figlio dx: rank(node) = 2 * rank(parent(node)) + 2

Alberi binari di ricerca

Problema: elenco di numeri ordinato in input e voglio cercare una chave k

- Soluzione 1: uso un array

BinarySearch(A, k , low, high)

if low > high then

return null

else mid ← (low + high) / 2

if k = key(mid) then

return mid

else if k < key(mid) then

return BinarySearch(A, k, low, mid – 1)

else return BinarySearch(A, k, mid + 1, high)

T (n) = O(log n) → ottimale

BS 2

Spazio = O(n) → ottimale

BS

Il problema è che usando una array l’insieme deve essere statico perché inserimento e

cancellazione costano O(n)

- Soluzione 2: albero binario di ricerca

• Proprietà: presi u, v e w 3 nodi con u Є sottoalbero di sx di v e w Є sottoalbero di

dx di v impongo che: key(u) <= key(v) <= key(w)

• I nodi esterni non immagazzinano nessuna chiave

• La visita inorder ritorna le chiavi in senso crescente

• Ora posso risolvere il problema con seguente algoritmo:

TreeSearch(k, v)

if isExternal(v) then

return v

if k = key(v) then

return v

else if k < key(v)

return TreeSearch(k, leftChild(v))

else return TreeSearch(k, rightChild(v))

T = O(h)

TS

• Algoritmo iterativo alternativo (stessa complessità):

IterativeTreeSearch(k, T)

v ← T.root()

while v is not an external node do

if k = key(v) then

return v

else if k < key(v) then

v ← T.leftChild(v)

else v ← T.rightChild(v)

return v

• Operazioni:

1. inserzione (O(h)): come la ricerca, scorre tutta l’altezza dell’albero

confrontando di volta in volta la chiave da inserire con l’elemento salvato nel

nodo finché non giunge al nodo esterno giusto, quindi rimpiazza il nodo

esterno con uno interno contenente il nuovo elemento

2. cancellazione (O(h)): in questo caso ho anche il problema che una volta

eliminato il nodo devo preservare la proprietà dell’albero. Ho 3 casi:

1) il nodo da cancellare non ha figli: lo rimpiazzo con un nodo esterno

2) ha 1 figlio: al posto del nodo eliminato e del figlio foglia metto il figlio nodo

e il suo sottoalbero

3) ha 2 figli: k = nodo da cancellare. Cerco nel sottoalbero del figlio dx di k il

nodo dopo k in ordine crescente (il quale ha al più un figlio) e lo metto al posto

di k. Il suo eventuale figlio va dove era k prima di essere spostato. Il nodo da

mettere al posto di quello cancellato può essere o quello subito dopo o quello

subito prima in ordine crescente

Quindi gli alberi binari impiegano O(n) spazio e O(h) tempo per le operazioni di

ricerca, inserzione e cancellazione.

- Range Queries

• findAllInRange(k , k ): restituisce tutte le chiavi comprese fra k e k .

1 2 1 2

• Procedimento:

1. trovo k 1

2. trovo k 2

3. restituisco i numeri compresi fra loro 2

• Casi:

1. key(v) < k : cerco in rightChild(v)

1

2. k <= key(v) <= k : riporto v e cerco in entrambi i figli

1 2

3. key(v) > k : cerco in leftChild(v)

2

RangeQuery(k , k , v)

1 2

if isExternal(v) then

return 0

if k <= key(v) <= k then

1 2

L ← RangeQuery( k , k , leftChild(v))

1 2

R ← RangeQuery( k , k , rightChild(v))

1 2

return L [unione] {element(v)} [unione] R

else if key(v) < k then

1

return RangeQuery(k , k , rightChild(v))

1 2

else if k < key(v) then

2

return RangeQuery(k , k , leftChild(v))

1 2

T (n) = O(n + s) (s: numero di elementi ritornati)

RQ

- Ricerca basata su indici

Una contraddizione degli alberi binari è che non siamo più in grado di trovare

l’i-esimo elemento più piccolo in O(i) come con gli array. Per ovviare suppongo di

supportare una nuova operazione:

select(i): ritorna l’elemento con l’i-esima chiave più piccola

Per supportarla aggiungo ad ogni nodo v un campo n che indica il numero di nodi

v

del sottoalbero con radice in v (compreso v). Nodo esterno: n =0. Ora inserzione e

v

cancellazione devono tenere conto del nuovo campo:

1. inserzione di w: n = 1 e incremento di 1 tutti gli antenati di w sul cammino da

w

w alla radice

2. cancellazione di w: decremento di 1 gli n di tutti i nodi v sul cammino da w

v

alla radice

TreeSelect(i, v)

w ← leftChild(v)

if i <= n then

w

return TreeSelect(i, w)

else if i = n + 1 then

w

return (key(v), element(v))

else return TreeSelect(i – n – 1, rightChild(v))

w

- Costruzione albero binario di ricerca: O(nlog n)

2

Dato un insieme ordinato si procede così:

1. metto come root l’elemento di mezzo

2. leftChild(v) è l’elemento di mezzo della metà sx

3. rightChild(v) è l’elemento di mezzo della metà dx

4. e così via…

AVL

• Albero binario di ricerca quasi perfettamente bilanciato.

• rank(v) (o r(v)) (rango): altezza di v

• Propietà fondamentale: se un nodo v ha 2 figli (x e y) allora |r(x) – r(y)| <= 1

• h = O(log n)

2

- Rotazioni

Inserzione e cancellazione minano la proprietà dell’AVL e quindi una volta fatte

l’albero va ricostrruito attreverso una singola o doppia rotazione. In tutte le rotazioni i

4 sottoalberi con radice nei 3 nodi non cambiano il loro ordine da sx a dx. Siano:

1. z = primo nodo (partendo da quello inserito e andando verso root) tale che z è

sbilanciato, ovvero la differenza dell’altezza dei figli è più di 1

2. y = figlio di z con h maggiore

3. x = figlio di y con h maggiore

Si distinguono 2 casi:

1. rotazione singola: x, y e z sono tutti figli destri o sinistri

a = z b = y

rotazione singola

b = y c = x

a = z

c = x

T 0 T 1 T T T T

0 1 2 3

T T

2 3

c = z b = y

rotazione singola a = x c = z

b = y

a = x T 3 T T T T

T 0 1 2 3

2

T T

0 1

2. rotazione doppia: x, y e z sono un po' e un po'

a = z b = x

rotazione doppia

c = y a = z c = y

b = x

T 0 T T T T T

3 0 1 2 3

T T

1 2

c = z b = x

rotazione doppia

a = y a = y c = z

b = x T 3

T T T T T

0 0 1 2 3

T T

1 2

Algoritmo restructure(x)

1: a,b e c: left-to-right (inorder) listing of the nodes x, y and z and T , T , T , T : left-

0 1 2 3

to-right (inorder) listing of the 4 subtrees of x, y and z that are rooted at x, y and z

2: replace the subtree rooted at z with a new subtree rooted at b

3: Let a be the left child of b and let T and T be the left and right subtrees of a,

0 1

respectively.

4: Let c be the right child of b and let T and T be the left and right subtrees of

2 3

c, respectively.

5: Recalculate the heights of a, b, and c, (or a “standin” function for height), from

the corresponding values stored at their children, and return b.

T (n) = O(1)

restructure

insertAVL(k, e, T)

v ← IterativeTreeSearch(k, T)

if v non è un nodo esterno then

return “C’è già in T un elemento con chiave k”

espandi v in in nodo interno con 2 nodi esterni figli

v.key ← k

v.element ← e

v.height ← 1

rebalanceAVL(v, T)

removeAVL(k, T)

v ← IterativeTreeSearch(k, T)

if v è un nodo esterno then

return “Non c’è nessun elemento in T con chiave k”

if v non ha nodi esterni figli then

u è il nodo in T con chiave più vicina a k

sposta la coppia chiave-valore di u in v

v ← u

w è il figlio di v con altezza più piccola

rimuovi w e v da T, rimpiazzando v con il fratello di w (z)

rebalanceAVL(z, T)

rebalanceAVL(v, T)

v.height ← 1 + max(v.leftChild().height, v.rightChild().height)

while v non è root di T do

v ← v.parent()

if |v.leftChild().height - v.rightChild().height| > 1 then

y è il figlio più alto di v e x è il figlio più alto di y

v ← restructure(x)

v.height ← 1 + max(v.leftChild().height, v.rightChild().height)

Operazione Tempo Cambi

strutturali

find O(logn) nessuno

insert O(logn) O(1)

remove O(logn) O(logn)

Alberi red-black

• Altro modo per creare un albero binario bilanciato

• Invece di portarmi dietro l’atezza, di ogni nodo mi porto dietro un’altra info: il suo

colore, che può essere o nero o rosso (1 bit)

• Propietà

1. ciascun nodo è o rosso o nero

2. la radice è nera

3. le foglie sono nere

4. i figli di un nodo rosso sono entrambi neri

5. conseguentemente alla 4, non posso avere 2 figli rossi di fila sullo stesso cammino

6. per ogni nodo x, tutti i cammini da x alle sue foglie contengono lo stesso numero di

nodi neri (altezza nera)

• L’altezza è O(log n)

2

• h <= 2h nera

• Le operazioni di ricerca, inserimento e cancellazione impiegano O(log n) (come

2

AVL)

• Inserimento e cancellazione possono richiedere un successivo riordinamento

dell’albero (rotazione), che comunque impega O(1)

• Stessa complessità temporale degli AVL per find, insert e remove

CODE DI PRIORITA

• Key: oggetto assegnato ad un element come suo specifico attributo

• Servono per rispondere velocemente al problema: restiruire l’elemento di maggiore

priorità

• La priorità è tipicamente valutata sulle chiavi degli elementi

• Operazioni:

1. insert(k, e): inserisce nella coda P l’elemento e con chiave k

2. removeMin(): ritorna e rimuove da P l’elemento con la più piccola chiave

3. findMin(): come removeMin() ma non lo rimuove

Heap

• Migliore struttura dati per implementare una coda di priorità

• minHeap: il root è l’elemento più piccolo. maxHeap: root è l’elemento più grande.

D’ora in poi si considerano solo i minHeap

• Immagazzina gli elementi in un albero binario

• Proprietà:

1. immagazzina tutte le chiavi nei nodi interni

2. heap order: per ogni nodo interno v tale che v != root vale che

key(v) >= key(parent(v))

ogni nodo interno ha rango almeno 2 e rango(root) = 1

3. albero binario quasi perfettamente bilanciato:

∘ i livelli 0, 1, 2, … , h-1 hanno il maggior numero di nodi possibili: fino al

livello h-1 è perfettamente bilanciato

∘ al livello h-1 i nodi interni sono a sx di quelli esterni

∘ al livello h le foglie sono tutte addossate a sx

∘ l’ultimo nodo è quello più a dx e di maggiore profondità

è quindi un albero binario completo

4. h = log n

2

- Implementazione con un array

• L’heap è facilmente implementato con un array

• Gli indici dell’array vanno da 1 a n (n: numero chiavi nell’heap)

• L’albero è popolato partendo dalla cima (root) a scendere, dal nodo più a sx a quello

più a dx

• root = A[1]

• I figli di A[i] sono A[2i] (figlio sx) e A[2i + 1] (figlio dx)

• Il padre di A[i] è A[i/2]

• I metodi root, parent, leftChild, rightChild, sibling, isInternal, isExternal, isRoot e

findMin sono facilmente eseguibili in O(1)

• Altre operazioni come extractMin, insertKey e delete potrebbero portare alla perdita

della proprietà dell’heap e quindi può essere necessario un successivo riordinamento

• Nel caso dell’extractMin, la key che era nella root, che viene estratta, viene

inizialmente rimpiazzata con l’ultima key dell’heap (più infondo e più a dx). Dopo di

che, se A[1] è > di A[2] o di A[3], va scambiato col minimo fra i 2 (lo si fa scendere).

Stessa cosa va fatta se il vecchio A[1] è > dei suoi 2 nuovi figli e così via. Nel caso

peggiore la nuova root va fatta scendere fino all’ultimo livello. Il procedimento di far

scendere una chiave se necessario è chiamato Heapify.

Heapify(A, i)

l ← 2 * i

r ← 2 * i + 1

if l <= heap_size(A) and A[l] < A[i] then

smaller ← l

else smaller ← i

if r <= heap_size(A) and A[r] < A[smaller] then

smaller ← r

if smaller != i then

Swap(A[i], A[smaller])

Heapify(A, smaller)

IterativeHeapify(A, i) (n=dimensione heap)

while i < n do

if 2i+1 < n then //2 childrens

if A[i] <= A[2i] and A[i] <= A[2i+1] then

return

else j ← min(A[2i], A[2i+1])

Swap(A[i], A[j])

i ← j

else //1 or 0 children

if 2i <= n then //1 child

if A[i] > A[2i] then

Swap(A[i], A[2i])

return

return

T (n) = O(log n)

Heapify 2

Quindi l’extractMin è:

extractMin(A, n): O(log n)

2

tmp ← A[1]

A[1] ← A[n]

n ← n-1

Heapify(A, 1)

return tmp

• Nell’insertKey, la nuova chiave viene inserita a dx dell’ultimo nodo interno,

creando un nuovo nodo interno. Dopo di che si deve controllare se la nuova chiave è

più piccola di suo padre: se si devo scambiare i 2. Questo controllo va fatto per tutti i

nuovi padri nella chiave inserita via via che la faccio salire. Quindi, al contrario

dell’Heapify, qua la chiave può solo salire.

insertKey(A, k)

n ← n+1

A[n] ← k

t ← n

while t > 1 do

if A[t/2] > A[t] then

Swap(A[t/2], A[t])

t ← t/2

else t ← 1

T (n) = O(log n)

insertKey 2

• Nel delete, rimpiazzo la chiave eliminata con quella salvata nell’ultimo nodo ed

elimino quest’ultimo nodo ormai vuoto. Dopo di che controllo se l’ultima key

spostata viola la proprietà con padre o con i figli. Infatti in questo caso la chiave può

salire (se il padre è più grande) o può scendere (figlio/i più piccolo/i).

delete(A, p)

tmp ← A[p]

A[p] ← A[n]

n ← n-1

if A[p] < A[p/2] then

while A[p] < A[p/2] do

Swap(A[p], A[p/2])

p ← p/2

if p = 1 then

return tmp

else if A[p] > A[2p] or A[p] > A[2p + 1]

Heapify(A, p)

return tmp

else return tmp

T (n) = O(log n)

delete 2


PAGINE

25

PESO

122.43 KB

AUTORE

mike_it

PUBBLICATO

4 mesi fa


DESCRIZIONE APPUNTO

Algoritmi e semplici spiegazioni di come essi operano e delle loro caratteristiche riguardanti:
- Ordinamento: InsertionSort, MergeSort, QuickSort, CountingSort, RadixSort, BucketSort, DeterministicSelection
- Strutture dati: pile, code, liste (array list e linked list)
- Alberi: alberi binari, alberi binari di ricerca, AVL, alberi red-black
- Code di priorità: heap (caratteristiche, implementazione, creazione di un heap), HeapSort
- Tabelle hash: mappe, tabelle hash
Ogni sezione contiene la spiegazione delle caratteristiche principali riguardanti l'argomento ed i principali algoritmi corredati da analisi della complessità e semplice spiegazione a parole di come operano.


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Perugia - Unipg
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher mike_it di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Perugia - Unipg o del prof Pinotti Maria Cristina.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!