Interrogazioni su un albero binario di ricerca
Interrogazioni – Operazioni che restituiscono
informazioni su un insieme dinamico S. Non modificano
l’insieme.
Search(S,k) – dato un insieme S ed un valore chiave k
restituisce un puntatore x ad un elemento in S tale che
key[x] = k
Maximum(S) – dato un insieme S su cui è definita una
relazione d’ordine totale, restituisce il puntatore
all’elemento di S con chiave più grande
Minimum(S) – dato un insieme S su cui è definita una
relazione d’ordine totale, restituisce l’elemento di S con
chiave più piccola
Successor(S,x) – dato un insieme S su cui è definita una
relazione d’ordine totale, e dato un puntatore x ad un
elemento di S, restituisce il successivo elemento più
grande in S (o NIL se x punta all’elemento massimo di S).
Predecessor(S,x) - dato un insieme S su cui è definita
una relazione d’ordine totale, e dato un puntatore x ad un
elemento di S, restituisce il successivo elemento più
piccolo in S (o NIL se x punta all’elemento minimo di S).
Ricerca in un ABR
Tree-search(x,k)
If (x=NIL) o (k = key[x])
then return x
If (k < key[x])
then Tree-Search(left[x],k)
else Tree-Search(right[x],k)
Iterative-Tree-search(x,k)
While (xNIL) e (k  key[x])
do if k < key[x]
then x  left[x]
else x  right[x]
Return x
Qual è la complessità dell’operazione di ricerca in un ABR ?
T(n) = O(h)
h = Altezza dell’albero
Confronto con il metodo dei dimezzamenti successivi
Ipotizziamo che l’ albero sia completo –
Supponiamo di eseguire Tree-search(root(T),7).
15
6
20
3
2
8
17
7
4
13
27
16
19
22
30
Supponiamo di avere implementato il dizionario con un array A
ordinato. Eseguiamo ricercaBinariaIter(A,7)
2
3
4
6
7
8
13
15
16
17
19
20
22
27
30
Per le proprietà dell’ABR, se l’ABR fosse completo, allora la
chiave di un nodo v sarebbe l’elemento mediano nell’insieme
ordinato delle chiavi associate all’insieme di nodi costituiti dal
sottoalbero sinistro di v, da v, e dal sottoalbero destro di v
 Ad ogni discesa di livello, dimezzerei lo spazio di ricerca!
Notare …
Non è detto che un ABR sia completo. Dipende da come lo
abbiamo costruito. Ad esempio, i seguenti 2 ABR rappresentano
lo stesso insieme di elementi:
15
6
3
2
20
8
4
7
17
16
13
27
19
22
30
30
Ma anche questo è un ABR
22
27
20
19
17
16
15
...
2
Notare: Tsearch(n) = O(h) in entrambi i casi
Però:
ABR completo  h = (log(n))
ABR “linearizzato”  h = (n)
Minimo e Massimo
Tree-minimum(x)
while (left[x]  NIL)
do x  left[x]
Return[x]
Tree-maximum(x)
while (right[x]  NIL)
do x  right[x]
Return[x]
Complessità - T(n) = O(h)
h = altezza dell’albero
15
6
3
2
18
Tree-maximum(x)
8
4
Tree-minimum(root(T))
17
7
13
9
20
Successore e predecessore
Tree-successor(x)
If (right[x]  NIL)
then return Tree-Minimum(right[x])
y  p[x]
While (y  NIL) e (x=right[y])
do x  y
y  p[y]
Return y
Complessità T(n) = O(h)
15
6
3
2
Cerco il min dell’ABR
con root=right[x]
8
4
18
17
7
13
9
Cerco l’antenato più
prossimo di x il cui
figlio sinistro è la
radice del
sottoalbero che
contiene x
Tree-predecessor(x) è perfettamente simmetrica
20
In conclusione:
Le operazioni di interrogazione Search, Minimum, Maximum,
Successor e Predecessor possono essere eseguite in un albero
binario di ricerca di altezza h in un tempo O(h).
Operazioni di modifica su un albero binario di ricerca
Operazioni di modifica – operazioni su un insieme
dinamico S che modificano le proprietà dell’insieme.
Insert(S,z) – inserisce in S l’elemento puntato da z
Delete(S,k) - rimuove da S l’oggetto con chiave k
Per semplicità, dirò “nodo” o “elemento” intendendo
“puntatore al nodo” e “puntatore all’elemento”,
rispettivamente.
Inserimento
Possiamo sempre inserire un nuovo elemento z come foglia.
Per decidere la posizione del nuovo elemento possiamo usare la
seguente strategia:
- discendiamo tutto l’albero, partendo dalla radice. In
corrispondenza di ogni nodo x, andiamo a sinistra se key[z] <
key[x], andiamo a destra altrimenti.
Supponiamo di voler inserire un nodo
i cui campi sono inizializzati a:
Key[z] = 8
p[z] = NIL
Left[z] = NIL
Right[z] = NIL
15
6
18
3
2
9
4
17
7
20
13
8
10
Se seguo questo schema l’elemento z viene posizionato nella
posizione giusta. Infatti, per costruzione, ogni antenato di z si
ritrova z nel giusto sottoalbero.
Inserimento
Tree-insert(T,z)
y  NIL
x  root[T]
While (xNIL)
do y  x
if (key[z] < key[x])
then x  left[x]
else x  right[x]
p[z]  y
If (y  NIL)
then if (key[z] < key[y])
then left[y]  z
else right[y]  z
else root[T]  z
Cerchiamo la posizione giusta
per una foglia con chiave pari
a key[z].
y punterà al padre di z
Aggiorniamo il puntatore p[z]
Aggiorniamo i puntatori del
nodo y
Se y=NIL, l’albero contiene
solo il nodo z.
Il nodo z è allora la radice
dell’albero. Non è necessario
aggiornare I puntatori left[z]
e right[z]
Complessità T(n) = O(h)
h = altezza dell’ABR
N.B. Operazioni di inserimento successive possono
“linearizzare” l’albero.
Cancellazione
Sia z (se esiste) il nodo con chiave k. Ci sono 3 situazioni
possibili:
1) Cancellazione di un nodo z privo di figli Modifichiamo il padre di z (p[z]) in modo che non punti
più a z
2) Cancellazione di un nodo z con un unico figlio Estraiamo il nodo z creando un collegamento tra il padre
di z (p[z]) ed il figlio di z
3) Cancellazione di un nodo z avente due figli.
Estraiamo il successore y di z e sostituiamo il contenuto
di z con il contenuto di y
15
6
3
2
3
18
9
17
7
4
5
1
13
10
2
20
Cancellazione
Tree-Delete(T,k)
z=Tree-search(root[T],k)
If (z  NIL) then
If (left[z]=NIL) o (right[z]=NIL)
then y  z
else y  Tree-Successor(z)
If (left[y]  NIL)
then x  left[y]
else x  right[y]
If (x  NIL)
then p[x]  p[y]
If (p[y] = NIL)
then root[T]  x
else if (y = left[p[y]])
then left[p[y]]  x
else right[p[y]]  x
If (yz)
then key[z]  key[y]
15
6
3
2
3
18
9
17
7
4
5
1
13
10
2
20
Nodo senza figli
Tree-Delete(T,k)
z=Tree-search(root[T],k)
If (z  NIL) then
If (left[z]=NIL) o (right[z]=NIL)
then y  z
else y  Tree-Successor(z)
If (left[y]  NIL)
then x  left[y]
else x  right[y]
cioè x=NIL
If (x  NIL)
then p[x]  p[y]
If (p[y] = NIL)
Se il nodo z era la radice, allora
then root[T]  x
root[T] = NIL
else if (y = left[p[y]])
altrimenti
then left[p[y]]  x sostituisce il puntatore a z con NIL
else right[p[y]]  x
If (yz)
15
then key[z]  key[y]
6
3
2
18
9
17
7
4
5
NIL
13
10
T(n) = O(h)
20
Nodo con un figlio
Tree-Delete(T,k)
z=Tree-search(root[T],k)
If (z  NIL) then
If (left[z]=NIL) o (right[z]=NIL)
then y  z
else y  Tree-Successor(z)
If (left[y]  NIL)
then x  left[y]
x = puntatore all’unico figlio di z
else x  right[y]
If (x  NIL)
then p[x]  p[y]
p[x] = puntatore al padre di z
If (p[y] = NIL)
se z era la radice
then root[T]  x
la nuova radice è il figlio di z
else if (y = left[p[y]])
altrimenti
then left[p[y]]  x
crea connessione tra il padre di z
else right[p[y]]  x
ed il figlio di z
If (yz)
15
then key[z]  key[y]
6
3
2
18
9
17
7
4
5
13
10
T(n) = O(h)
20
Nodo con due figli
Tree-Delete(T,k)
z=Tree-search(root[T],k)
If (z  NIL) then
If (left[z]=NIL) o (right[z]=NIL)
then y  z
else y  Tree-Successor(z)
y = successore di z
If (left[y]  NIL)
then x  left[y]
else x  right[y]
x = figlio destro del succes. di z
If (x  NIL)
N.B. – il figlio ds di y potrebbe non esistere
then p[x]  p[y] il padre di x diventa il padre di y (cancello y)
If (p[y] = NIL)
N.B. il padre di y non può mai essere NIL
then root[T]  x
else if (y = left[p[y]]) il padre di y deve puntare al nuovo figlio x
then left[p[y]]  x
else right[p[y]]  x
If (yz)
then key[z]  key[y] sostituisce la chiave di z con la chiave di y
15
6
z
4
3
2
18
9
y
4
17
7
13
10
Success. di z
x
5
T(n) = O(h)
20
In conclusione:
Le operazioni di inserimento e di cancellazione di un
nodo in un ABR hanno tempo di esecuzione T(n) = O(h)
dove h è l’altezza dell’albero.