vuoi
o PayPal
tutte le volte che vuoi
N N N N N N N N N N N N
Esercizio 16
Si consideri la struttura dati albero generale i cui nodi hanno gli attributi: e e si sviluppi
key, fratello, figlio padre
un algoritmo per verificare se è soddisfatta la seguente proprietà speciale:
> per ogni nodo x diverso dalla radice
key[padre[x]] key[x],
Soluzione
test_property(T)
x <- root[T]
return test(x)
test(x)
if (padre[x] == NIL) OR (key[padre[x] > key[x])
return (test(figlo[x]) AND test(fratello[x])
else return false
Esercizio 17
Si sviluppi un algoritmo per calcolare il grado massimo dei nodi di un albero generale rappresentato tramite gli
attributi: e (Ricordiamo che il grado di un nodo di un albero è pari al numero dei suoi
fratello, figlio padre.
figli.)
Soluzione
Esercizio 18
• Dire se il seguente albero binario di ricerca può essere colorato in modo da diventare un albero R/B. Giustificare
la risposta. (Il simbolo * rappresenta la foglia-NIL.)
30
/ \
17 35
/ \ / \
4 20 * *
/ \ / \
1 5 * *
/ \ / \
* * * 7
/ \
* *
• Disegnare l’albero che si ottiene applicando una rotazione destra alla radice dell’albero precedente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
