Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Binari di Ricerca

Prof. Pier Luca Lanzi

Alberi Binari di RicercaAlgoritmi e Calcolo Parallelo


Riferimenti

• Bertossi Alan A., Montresor Alberto. “Algoritmi e strutture di dati” (seconda edizione), CittàStudi 2010

• Stanley B. Lippman, Barbara E. Moo, Josee Lajoie“C++ Primer”, 5th Edition Addison-Wesley

2


Alberi binari di ricerca

Strutture dati che supportano operazioni di ricerca, minimo, massimo, prev, next, inserimento, e

cancellazione

Applicazioni: dizionari, code di priorità

L'idea è portare la ricerca binaria in un albero binario


Alberi Binari di Ricerca

• Definizione: albero binario in cui ogni nodo x contiene un insieme di dati data[x] associati ad una chiave key[x] da un dominio totalmente ordinato

• Le chiavi dei nodi del sottoalbero sinistro left[x] sono ≤ key[x]

• Le chiavi dei nodi del sottoalbero destro right[x] sono ≥ key[x]

4


Alberi Binari di Ricerca: Ricerca di un Elemento

• Ricerca dell’elemento 32

• Considera la radice x=37, confronta key[x] con 32

• Considera la radice x=24, confronta key[x] con 32

• Trova la chiave

32≤37Passa al sottoalbero sinistro

24≤32Passa al sottoalbero destro

5


Alberi Binari di Ricerca: Ricerca di un Elemento

• Ricerca dell’elemento 41

• La ricerca si ferma nel sottoalbero destro di 40

• Il sottoalbero è vuoto, l’elementonon è presente nell’albero

6

?


Alberi binari di ricerca:Operazioni Ammesse

• Tree key()

• Tree value()

• Tree left()

• Tree right()

• Tree parent()

• Tree lookup(Item k)

• Tree insert(Item k, Item d)

• Tree delete()

7

• Ogni nodo deve mantenere

• Figlio sinistro, destro

• Padre

• Chiave

• Valore

Figliosinistro

Padre

Figliodestro

Chiave, Valore


Ricerca

TREE-SEARCH (x, k)if x= NIL or k = key[x] then return xif k < key[x] then return TREE-SEARCH(left[x], k)else return TREE-SEARCH(right[x], k)

9


10Ricerca

TREE-SEARCH (x, k)if x= NIL or k = key[x] then return xif k < key[x] then return TREE-SEARCH(left[x], k)else return TREE-SEARCH(right[x], k)


Ricerca Iterativa

ITERATIVE-TREE-SEARCH(x, k)1 while x ≠ NIL and k ≠ key[x]2 do if k < key[x]3 then x ← left[x]4 else x ← right[x]5 return x

La ricerca può essere riscritta in forma iterativa

12


Ricerca Ricorsiva/Iterativa 13

Ricorsiva

Iterativa


Costo Computazionale della Ricerca

• Le operazioni di ricerca sono confinate ai nodi posizionati lungo un singolo percorso (path) dalla radice ad una foglia

• Il tempo di ricerca è Θ(h)

• Qual è il caso pessimo?

• E il caso ottimo?

14

h = altezza dell’albero


Minimo, Massimo, Elemento Successivo e Precedente

15


Minimo & Massimo

MinimoTREE-MINIMUM (x)1 while left[x] ≠ NIL2 do x ← left[x]3 return x

MassimoTREE-MAXIMUM(x)1 while right[x] ≠ NIL2 do x ← right[x]3 return x

16


Elemento Successivo

TREE-SUCCESSOR(x)if right[x] ≠ NIL then return TREE-MINIMUM (right[x])y ← p[x]while y≠NIL and x=right[y] do x ← y y ← p[y]return y

17


Successore/Predecessore

• Definizione: il successore di un nodo u è il più piccolo nodo maggiore di u

• Due casi

• Caso 1: u ha un figlio destro Il successore u' è il minimo del sottoalbero

destro di u

• Caso 2: u non ha un figlio destro Il successore è il primo avo u' tale per cui u sta

nel sottoalbero sinistro di u’

18


Successore/Predecessore 19


Inserimento

• Supponiamo di dover inserire l’elemento 35

• Dove dovrebbe essere inserito affinché l’albero rimanga un albero binario di ricerca ?

• Devo cercare la chiave!Inserimento di una nuova chiave

Ricerca Posizione + Inserimento della foglia

35

20


Inserimento

TREE-INSERT(T, z) 1 y ← NIL 2 x ← root[T] 3 while x ≠ NIL 4 do y ← x 5 if key[z] < key[x] 6 then x ← left[x] 7 else x ← right[x] 8 p[z] ← y 9 if y = NIL11 then root[T] ← z // Tree T was empty11 else if key[z] < key[y]12 then left[y] ← z13 else right[y] ← z

T albero di ricerca binaria

z nodo da inserirekey[z] = vleft[z] = NILright[z] = NIL

21


Cancellazione: Tre Casi Possibili 22


Cancellazione: Pseudocodice

TREE-DELETE(T, z) 1 if left[z] = NIL or right[z] = NIL 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ NIL 5 then x ← left[y] 6 else x ← right[y] 7 if x ≠ NIL 8 then p[x] ← p[y] 9 if p[y] = NIL10 then root[T] ← x11 else if y = left[p[y]]12 then left[p[y]] ← x13 else right[p[y]] ← x14 if y ≠ z15 then key[z] ← key[y]16 copy y's satellite data into z17 return y

23


Qual è la complessità delle operazioni diricerca, cancellazione, inserimento?

Le operazioni di ricerca, inserimento,cancellazione sono O(h) per un albero

binario di ricerca di altezza h

Qual è il caso peggiore? Il caso migliore?

L’altezza attesa di un albero binario di ricerca con n nodi è O(lg n)


Alberi Bilanciati?

• Fattore di bilanciamento Il fattore di bilanciamento β(v) di un nodo v è la

massima differenza di altezza fra i sottoalberi di v

• Esempio: albero perfetto: β(v)=0 per ogni nodo v

• In generale, sono necessarie tecniche per mantenere bilanciato l'albero

25


Esempio di Operazione di Bilanciamento

26

T3

T3

T1

T2

v

u

T1T2

v

u


Alberi Bilanciati

• Alberi AVL (Adel'son-Vel'skii e Landis, 1962) β(v) ≤ 1 per ogni nodo v Bilanciamento ottenuto tramite rotazioni

• B-Alberi (Bayer, McCreight, 1972) β(v) = 0 per ogni nodo v Specializzati per strutture in memoria secondaria

• Alberi 2-3 (Hopcroft, 1983) β(v) = 0 per ogni nodo v Bilanciamento ottenuto tramite merge/split, grado

variabile

• B-alberi binari (Andersson, 1993)

• Alberi Red-Black (Bayer, 1972)

27


Sommario

• Alberi Binari di Ricerca Struttura dati ispirata alla ricerca binaria Le chiavi dei nodi del sottoalbero

sinistro left[x] sono ≤ key[x] Le chiavi dei nodi del sottoalbero

destro right[x] sono ≥ key[x]

• Operazioni: ricerca, minimo, massimo, prev, next, inserimento, e cancellazione

• Complessità Ricerca, Inserimento, Cancellazione sono O(h)

per un albero di altezza h Un albero binario di ricerca con n nodi generato

in maniera casuale ha un’altezza O(lg n)

28

Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Binari di Ricerca

Education

Transcript of Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Binari di Ricerca