Esercizi di Algoritmi e Strutture Dati

Moreno Marzollamarzolla@cs.unibo.it

Ultimo aggiornamento: 29 novembre 2010

1 Rotazioni semplici in ABR

Si consideri loperazione di rotazione semplice applicata ad un Albero Bina-rio di Ricerca (ABR). Dimostrare che loperazione di rotazione semplice, comedefinita a lezione, preserva la proprieta di ordinamento degli ABR. In altre pa-role, dimostrare che un ABR, dopo una singola operazione di rotazione semplicerispetto ad un qualsiasi nodo x, e ancora un ABR.

Soluzione Consideriamo la figura seguente:

X Y/ \ / \Y T3 T1 X/ \ / \

T1 T2 T2 T3

Supponiamo di effettuare una rotazione semplice verso destra, usando Xcome perno. Prima della rotazione, valgono le seguenti relazioni:

Y XT1 YT2 YT2 XT3 X

(dove per semplicita usiamo la notazione T1 Y per indicare che per ogninodo Z di T1 vale la relazione Z Y ). E possibile verificare che tutte questerelazioni valgono anche nellalbero di destra (quello ottenuto dopo la rotazione),che quindi e ancora un ABR.

1

marzolla@cs.unibo.it

2 Costruzione di ABR

Dimostrare che qualsiasi algoritmo basato su confronti per la costruzione di unABR con n nodi ha complessita asintotica (n log n).

Soluzione Supponiamo che sia possibile costruire un ABR con n nodi, uti-lizzando confronti, in tempo strettamente inferiore a (n log n). Ricordiamoche, dato un ABR con n nodi, e possibile ottenere la lista ordinata delle chi-avi in esso contenute mediante una visita simmetrica (detta anche visita in-ordine) dellalbero. La visita simmetrica ha costo (n). Quindi, se potes-simo costruire un ABR in tempo inferiore a (n log n), riusciremmo anche aordinare un insieme di n elementi, usando solo confronti, in tempo inferiorea (n log n), il che e impossibile dato il limite inferiore alla complessita delproblema dellordinamento mediante confronti

3 Visita di un ABR

Loperazione di visita di un ABR con n nodi puo essere implementata deter-minando lelemento minimo dellABR, e poi invocando n 1 volte loperazionesuccessor(). Fornire una giustificazione intuitiva del fatto che questo algo-ritmo di visita abbia complessita asintotica (n).

Soluzione Ricordiamo lalgoritmo per determinare il successore di un nodo

algorithm successor(nodo v) -> nodoif (v == null) thenreturn null;

endifif (v.right != null) thenreturn min(v.right);

elsep = v.parentwhile (p != null && v == p.right) do

v = p;p = v.parent;

endwhilereturn p;

endif

dove la procedura min() determina il nodo con chiave minima in un alberoradicato nel nodo v, ed e definita come

algorithm min(nodo v) -> nodowhile (v != null && v.left != null) dov = v.left;

endwhile

2

return v;

Se proviamo a visualizzare il comportamento delloperazione di visita im-plementata mediante determinazione dellelemento minimo seguita da n 1 in-vocazioni della procedura successor(), osserviamo che ciascun arco dellalberoviene attraversato esattamente due volte: una volta in discesa, ad opera dellaprocedura min(), e una volta in salita ad opera della procedura successor(),che nel ramo else risale di figlio in padre fino alla prima svolta a destra. Eanche importante osservare che una volta attraversato in discesa e in salita, unarco non viene piu attraversato. Osserviamo anche che vengono eseguite O(1)operazioni elementari per ogni attraversamento di arco.

A questo punto, osserviamo che un albero on n nodi ha esattamente n 1archi (si dimostra per induzione, e vale per qualsiasi albero, non solo per alberibinari). Quindi il costo delloperazione di visita implementata come sopra e2(n 1) = (n).

4 Incremento di chiavi in un albero AVL

Si consideri un albero AVL contenente n chiavi numeriche. Supponiamo chele chiavi siano tutte distinte tra loro. Vogliamo implementare loperazioneincrementaChiave(k, d) il cui scopo e quello di incrementare il valore dellachiave k di una quantita d (che potrebbe anche essere negativa), facendolo di-ventare k + d. Al termine di questa operazione, la struttura dati risultantedeve ancora essere un albero AVL. Per lipotesi di unicita delle chiavi, il nodocontenente la chiave k, se esiste, e sempre unico; supponiamo anche che ilvalore k + d sia unico. Descrivere un algoritmo per realizzare loperazioneincrementaChiave(k,d), stimandone poi il costo computazionale.

Soluzione Esiste una soluzione banale, che consiste nel rimuovere il nodo conchiave k (che per ipotesi e unico) e inserire un nuovo nodo con chiave k + d. Ilcosto complessivo risulta essere O(log n).

5 Implementazione di un albero AVL

A lezione abbiamo visto che per una corretta implementazione degli alberi AVLe necessario conoscere laltezza dei sottoalberi radicati in ciascun nodo. Infatti,questa informazione consente poi di capire quali sono i sottoalberi pesanti,e quindi procedere alle operazioni di ribilanciamento appropriate. Ricordiamoche laltezza di un albero e la massima profondita cui si trova una sua foglia.Lalbero composto da un singolo nodo (la radice) ha altezza 0.

1. Consideriamo innanzitutto un generico ABR (non bilanciato). Supponi-amo che ciascun nodo v abbia un attributo intero v.h che corrispondeallaltezza del sottoalbero radicato in v. Mostrare come sia possibile es-tendere le operazioni di inserimento e rimozione di nodi di un ABR per

3

mantenere in modo efficiente il valore corretto di v.h per ciascun nodo.Tale modifica non deve alterare il costo computazionale delle operazionidi inserimento e rimozione, che devono mantenersi O(h) nel caso pessimo,essendo h laltezza totale dellalbero.

2. Consderiamo ancora un generico ABR. Dimostrare come loperazione dirotazione semplice puo essere estesa per mantenere il valore corretto di v.hper ciascun nodo. Dopo tale modifica, il costo delloperazione di rotazionesemplice deve essere O(h) nel caso pessimo, essendo h laltezza totaledellalbero.

3. Usare i due punti precedenti per dimostrare come sia possibile mantenerelinformazione sullaltezza di ciascun sottoalbero in un albero AVL senzaalterare il costo computazionale delle operazioni di inserimento e rimozionedi nodi.

Soluzione Assumiamo che un oggetto nodo v abbia gli attributi seguenti:

v.left riferimento al figlio sinistro (oppure null);

v.right riferimento al figlio destro (oppure null);

v.parent riferimento al padre (oppure null se v e la radice);

v.h altezza dellalbero radicato in v.

Definiamo come prima cosa lalgoritmo aggiusta_h(v). Lalgoritmo fun-ziona come segue: assume che i figli del nodo v (se esistono) abbiano il valorecorretto dellattributo h (quindi, assume di conoscere in maniera esatta laltezzadei sottoalberi radicati nei figli, sempre se non sono vuoti). In base a questainformazione, calcola il valore di v.h.

algoritmo aggiusta_h(Nodo v)if ( v.left == null && v.right == null ) thenv.h = 0;

elseif( v.left == null ) then // v.right != nullv.h = v.right.h + 1;

elseif( v.right == null ) then // v.left != nullv.h = v.left.h + 1;

elsev.h = max( v.left.h, v.right.h ) + 1;

endif

A questo punto e facile definire unaltra procedura, che chiameremo aggiusta_h_ricche risale ricorsivamente da un nodo v fino alla radice dellalbero, ricalcolandoil valore dellattributo h di tutti i nodi visitati:

4

algoritmo aggiusta_h_ric(Nodo v)while ( v != null ) doaggiusta_h(v);v = v.parent;

endwhile

Ora siamo in grado di ricalcolare il valore di h in caso di inserimento orimozione di nodi.

Nel caso di inserimento in un ABR, sappiamo che il nuovo nodo venga inser-ito in una foglia v. Dopo linserimento, chiamiamo semplicemente loperazioneaggiusta_h_ric(v) che ricalcola tutte le altezze da v fino alla radice dellalbero.Il costo complessivo e O(h) nel caso pessimo, essendo h laltezza dellalbero.

Nel caso di rimozione, e necessario distinguere i tre casi:

Il nodo rimosso v era una foglia. Sia p il padre di v (se esiste). Dopo averstaccato v, si invoca aggiusta_h_ric(p) e lalgoritmo termina.

Il nodo rimosso v ha un unico figlio w. Sia p il padre di v. Il nodo w vienereso figlio di p (al posto di v, e si invoca loperazione aggiusta_h_ric(p).Lalgoritmo termina.

Il nodo rimosso v ha due figli. Si individua il nodo predecessore w, ilquale non ha figlio destro. Sia p il padre di w. E possibile rimuoverew attaccando il padre p allunico figlio di w. Il nodo w si sostituiscea v. A questo punto si invoca aggiusta_h_ric(p), essendo sicuri chenel cammino da p alla radice la procedura attraversa anche la posizioneprecedentemente occupata dal nodo v che e stato rimosso (posizione oraoccupata da w).

Nel caso della rotazione semplice, consideriamo il caso di rotazione sempliceverso destra rispetto ad un nodo x. Si puo eseguire la procedura seguente:

x/ \y t3/ \

t1 t2

y = x.left;t1 = y.left;t2 = y.right;t3 = x.right;

y.right = x;x.left = t2;x.right = t3;aggiusta_h_ric(x);

5

6 Attraversamento in-ordine iterativo

Scrivere un algoritmo iterativo per effettuare la visita in-ordine di un alberobinario (non necessariamente di ricerca).

Soluzione Per implementare lalgoritmo di visita in-ordine facciamo uso diuno stack (pila). Gli elementi che inseriamo nello stack sono coppie < n, b >,essendo n un riferimento ad un nodo dellalbero, e b un valore booleano che puoessere true o false.

algoritmo inordine-iter(Nodo t)Stack S;S.push( );while (!S.empty()) do := S.pop(); // estrai dallo stackif (f==true) thenvisita il nodo n;

elseif (n.right != null) thenS.push( );

endifS.push( );if (n.left != null) thenS.push( );

endifendif

endwhile

Lidea dellalgoritmo e la seguente: ogni nodo n viene inizialmente inseritonello stack con flag settato a false. Quando un