Lezione 27 - Strutture ad albero avanzatehome.deib.polimi.it/comai/info3/File/Lezione 27...r $ l o p...

Politecnico di Milano - Prof. Sara Comai 1

LEZIONE 27: Strutture ad albero avanzate

• Modulo 1: Trie• Modulo 2: Alberi bilanciati• Modulo 3: Strutture dati spaziali

Informatica 3


Lezione 27 - Modulo 1

Trie

Informatica 3


Trie (1)

• Definizione di trie: struttura data basata sulla decomposizione dello spazio della chiave– suddivisione uguale dell’intervallo della chiave– memorizza i record nelle foglie

– Esempio di trie: • codice di Huffmann


Trie binario

• Il fattore di ramificazione è determinato dall’alfabeto utilizzato: – {0, 1} trie binario

120

4240

32

24

72 37

1

1

1

1

1

1

1

00

00

0

0 0

0

0

0


Trie alfabetico (1)

• Il fattore di ramificazione è determinato dall’alfabeto utilizzato:

– caratteri alfabetici + $ trie alfabetico a

n

t$ e

a

t

er$

lop

e

$

d

e

er

$

u

ck$

h

ors

e

$


Trie alfabetico (2)

• Il fattore di ramificazione è determinato dall’alfabeto utilizzato:

– caratteri alfabetici + $ trie alfabetico

a

n

d

t$ e

l

antelopeanteater

e

ant

deer duck

h

horse

a

u


PATRICIA Trie

• PATRICIA Trie (PATRICIA = Practical Algorithm To Retrieve Information Coded In Alphanumeric)– albero binario pieno che memorizza i record nelle foglie e

utilizza i nodi interni per memorizzare la posizione del pattern di bit della chiave utilizzata per decidere quale ramo prendere

0

1

2 3

5 64

120

42402 7

24

32 37

1xxxxxx0xxxxxx

01xxxxx00xxxxx

0101xxx

010101x000xxxx



Alberi bilanciati

Informatica 3


Introduzione

• I BST possono diventare sbilanciati– operazioni di ricerca e aggiornamento costose– occorre utilizzare altri algoritmi di aggiornamento

che abbiano buone prestazioni e che mantengano l’albero bilanciato

• Albero AVL– modifica le procedure di inserimento e cancellazione dei

BST in modo da mantenere l’albero bilanciato• Albero splay

– non richiede che l’albero sia bilanciato ma bilancia il BST ogni volta che vi si accede per una ricerca o per un aggiornamento


Albero AVL

• Albero AVL: – BST per il quale vale la seguente proprietà:per ogni nodo l’algezza dei suoi sotto-alberi di sinistra e

di destra differisce al massimo di 1

accesso a un albero con n nodi: O(log n)inserimenti/cancellazioni: se sono proporzionali

alla profondità dell’albero sono O(log n)


Esempio

• 4 casi: S nodo più profondo sbilanciato1) il nuovo nodo è il figlio di sinistra del figlio di sinistra di S2) il nuovo nodo è il figlio di destra del figlio di sinistra di S3) il nuovo nodo è il figlio di sinistra del figlio di destra di S4) il nuovo nodo è il figlio di destra del figlio di destra di S

37

24

7 32

2

42

40 42

120

37

24

7 32

2

42

40 42

120

5


Rotazione singola

• Casi 1 e 4: rotazione singola

P

S

A

B

C

S

P

A B C


Rotazione doppia

• Casi 2 e 3: rotazione doppia

G

P

B

A

C

S D

GP

B

AC

S

D


Albero splay

• Albero che migliora le prestazioni di un BST– non bilanciato obiettivo: mantenere basso il

costo totale di tutti gli accessi– le singole operazioni non sono efficienti (O(n))– una serie di m operazioni richiede O(m log n) per

un albero di n nodi con m>=n

– Ogni volta che il nodo S viene acceduto (inserito, cancellato, cercato) viene eseguito il processo di splaying

• S viene spostato alla radice• se S viene cancellato, il padre di S viene spostato alla

radice


Rotazione singola

• Se S è figlio della radice viene applicata una rotazione singola

P

S

B

C

A

P

S

B C

A


Rotazione a zigzag

• Se S è il figlio sinistro di P e P è il figlio destro di G • oppure S è il figlio destro di P e P e il figlio sinistro di Gviene applicata una rotazione a zigzag

– spesso si ha una riduzione dell’altezza dell’albero

G

S

C

D

B

P

A

S

P

DC

P

BA


Rotazione a zigzig

• Se S è il figlio sinistro di P e P è il figlio sinistro di G • oppure S è il figlio destro di P e P e il figlio destro di Gviene applicata una rotazione a zigzig

– sposta il nodo S verso la radice

G

S

B

D

A

P

C

S

G

D

A

C

P

B


Esempio (1)

• Ricerca del valore 89 splaying

17

25

90

99

18 42

72

89

75

G

P

S

17

25

90

99

18 89

72

7542


Esempio (2)


17

25

90

99

18 89

72

7542

G

P

S

17

25

89

90

18 72

7542

99


Esempio (3)


17

25

89

90

18 72

7542

99

P

S 17

25

89

90

18 72

7542

99


Conclusioni

• Le rotazioni dell’albero splay tendono a far avvicinare alla radice i nodi a cui si accede più di frequente

• Il processo tende a ribilanciare l’albero

• L’operazione di inserimento avviene come per il BST, a cui segue l’operazione di splying

• L’operazione di cancellazione è equivalente al caso BST e il nodo padre viene spostato alla radice



Strutture dati spaziali

Informatica 3


Introduzione

• Tutte le strutture dati viste finora: – ricerca su una chiave monodimensionale

• Applicazioni spaziali che trattano posizioni nello spazio– sistemi informativi geografici– informatica grafica– intelligenza artificiale

strutture dati spaziali- dati organizzati per posizione


k-d tree (1)

• k-d tree: BST modificato in cui le ramificazioni ad ogni livello sono definite da un discriminatore: – il discriminatore a livello i è i mod k per k

dimensioni

– Es. dati con coordinate xy: k=2• ad ogni livello il discriminatore alterna tra x e y

• Un nodo N a livello 0 (radice) ha nel sottoalbero di sinistra i nodi il cui valore x è minore di Nx (il sottoalbero di destra ha i nodi il cui valore x è maggiore di Nx)

• Un nodo M a livello 1 ha nel sottoalbero di sinistra i nodi il cui valore y è minore di My

• ecc.


k-d tree (2)

• Esempio:

B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------


k-d tree: ricerca

• Esempio: ricerca di P(69,50)

B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------


k-d tree: ricerca


B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------


k-d tree: ricerca


B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------

x: 40<69


k-d tree: ricerca


B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------


k-d tree: ricerca


B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------

y: 10<50


k-d tree: ricerca


B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------


k-d tree: inserimento

• Esempio: inserimento di P(10,50)

B

C

A

EF

D

A(40,45)

B(15,70)C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ----------------------------

y ---------------------


k-d tree: inserimento

• Esempio: inserimento di P(10,50)

B

C

A

EF

D

A(40,45)

B(15,70) C(70,10)

D(69,50)

E(55,80) F(80,90)

x -------------

y -----

x ---

y ---------------------P(10,50)

P


Quadtree (e octree)

• Utilizzato per la rappresentazione di superfici 2D (quadtree) o solidi 3D (octree)– Tecnica di decomposizione spaziale: superficie o solido

come combinazinoe di superfici o solidi con caratteristiche più semplici (es. pixel o voxel)

– Esempio di oggetto 2D:


Quadtree (1)

• L’idea fondamentale dei quadtree (e octree) è quella del principio della suddivisione binaria.

• Quadtree: – si ottiene suddividendo ricorsivamente un piano 2D in 4

quadranti (0,1,2,3).– Quando il quadtree rappresenta un’area 2D ogni quadrante

può essere:• pieno• vuoto• parzialmente pieno

– Un quadrante parzialmente pieno è ulteriormente suddiviso in sottoquadranti.


Quadtree (2)

• Il procedimento termina quando o tutti i quadranti sono pieni o vuoti oppure quando si raggiunge una soglia (cut-off depth).

• Se 4 quadranti sono tutti vuoti o tutti pieni vengono sostituiti con il quadrante del livello superiore


Quadtree (3)

2 3

0 1P

E

P P P

F F E EF FE F FE EF FF EF FE F FE F F

P P P P PPF F FFE E

F

P

FE

0 1 23

pienovuoto

parzialm. pieno


Octree

• Octree:– Sono simili ai quadtree: qui le 3 dimensioni

vengono suddivise in ottanti anzichè quadranti.– Gli ottanti vengono identificati tramite un numero

(da 0 a 7) oppure tramite un nome simbolico (es. NE, SO, SW…).

• Operazioni tipiche: unione/intersezione di due alberi – si calcola in maniera molto semplice, visitando i

due alberi top-down in parallelo.


Operazioni su Octree/Quadtree

• UNIONE tra due alberi (quad- oppure octree)• si considerano le coppie di nodi

corrispondenti tra i due alberi– se uno dei due nodi è vuoto si copia nell’albero

che rappresenta l’unione l’altro nodo– se uno dei due nodi è pieno si copia questo nodo

nell’unione– altrimenti si considerano i sottoquadranti/ottanti e

si ripete lo stesso ragionamento• INTERSEZIONE tra due alberi: si calcola

come l’unione, invertendo “vuoto” e “pieno”.


Esempio di unione

P

FEE E F EE E

PE

P

F

EE

PF

FEF

P

F F F

E

P

P

FEE E

E

P

FF

quadtree 1 quadtree 2

unione


Esempio di intersezione

P

FEE E F EE E

PE

P

F

EE

PF

FEF

P

F F F

E

P

EE

P

F F

E

P

EE

quadtree 1 quadtree 2

intersezione

Lezione 27 - Strutture ad albero avanzatehome.deib.polimi.it/comai/info3/File/Lezione 27...r $ l o p...

Documents

Transcript of Lezione 27 - Strutture ad albero avanzatehome.deib.polimi.it/comai/info3/File/Lezione 27...r $ l o p...