(a)
Alberi Binari di Ricerca Dato il seguente albero binario di ricerca T:
Indicare il numero di confronti necessari per la ricerca del valore 32 (Includere anche l’eventuale confronto di successo):
(a) Strutture dati elementari: Pila Data una pila P inizialmente vuota, applicare a P la sequenza di operazioni:
Push(7) Push(2) Push(6) Push(8) q ←Top() Push(9) Pop() q ←Top()
Indicare il valore finale di q:
(b)
Strutture dati elementari: Coda
Data una coda C inizialmente vuota, applicare a C la sequenza di op- erazioni:
Enqueue(8) Enqueue(2) Enqueue(15) Dequeue() Enqueue(7) Dequeue() Dequeue() Enqueue(4) q ←First() Indicare il valore finale di q:
(a)
Alberi Binari di Ricerca Dato il seguente albero binario di ricerca T:
Indicare il numero di confronti necessari per la ricerca del valore 32 (Includere anche l’eventuale confronto di successo):
Applicare la procedura di inserimento Tree-Insert(T, 44) ed indicare il valore del nodo padre del valore inserito al termine della procedura:
A seguito del precedente inserimento, applicare la procedura di eliminazione Tree-Delete(T, 39) cos’ì definita:
Tree-Delete(T, z)
if left[z] = nil or 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 left[p[y]] = y
then left[p[y]] ← x
else right[p[y]] ← x
if y ̸= z
then key[z] ← key[y]
return y
Indicare il valore del nodo a cui viene assegnato un nuovo genitore al termine della procedura. Se tale nodo non esiste, indicare 0:
(b)
Alberi AVL Dato il seguente albero AVL:
Indicare il fattore di bilanciamento del nodo 42:
Indicare il valore del nodo critico all’inserimento del valore 26. Se tale nodo non esiste, indicare 0:
A seguito del precedente inserimento, inserire in sequenza gli ulteriori valori 25, 17 e 19, tenendo conto delle possibili rotazioni. Indicare l’altezza del nodo 30 a seguito di tutti gli inserimenti: