Interrogazioni su un albero binario di ricerca Interrogazioni – Operazioni che restituiscono informazioni su un insieme dinamico. 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 l’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 elemento x di S, restituisce il successivo elemento più grande in S (o NIL se x è l’elemento massimo). Predecessor(S,x) - dato un insieme S su cui è definita una relazione d’ordine totale, e dato un elemento x di S, restituisce il successivo elemento più piccolo in S (o NIL se x è l’elemento minimo). 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 (xNIL) 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, un elemento x (quando l’albero è completo) è l’elemento “mediano” nell’insieme ordinato composto da x, dal sottoalbero sinistro di x e dal sottoalbero destro di x 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,z) - rimuove da S l’oggetto puntato da z 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 (xNIL) 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 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,z) 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 (yz) then key[z] key[y] Return y 15 6 3 2 3 18 9 17 7 4 5 1 13 10 2 20 Nodo senza figli Tree-Delete(T,z) 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] (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 (yz) then key[z] key[y] Return y 15 6 3 2 18 9 17 7 4 5 NIL 13 10 T(n) = O(1) 20 Nodo con un figlio Tree-Delete(T,z) if (left[z]=NIL) o (right[z]=NIL) then y z y=z else y Tree-Successor(z) If (left[y] NIL) then x left[y] x = puntatore al 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 (yz) then key[z] key[y] Return y 15 6 3 2 18 9 17 7 4 5 13 10 T(n) = O(1) 20 Nodo con due figli Tree-Delete(T,z) 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 succes. di y non può avere f.sinistri then p[x] p[y] aggiorna il puntatore al padre di x If (p[y] = NIL) se z era la radice then root[T] x il figlio ds del succ di x diventa radice else if (y = left[p[y]]) altrimenti then left[p[y]] x else right[p[y]] x If (yz) then key[z] key[y] sostituisce chiave di z con chiave di y Return 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.