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

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