Testo completo
ESERCIZIO DI ASD DEL 16 MARZO 2009
Binary Search Tree Colorabile
Sia T un BST (avente anche le foglie fittizie come nei RBT). Sia C un colore (Rosso oppure Nero) ed h ≥ 0 un intero. Si consideri il problema di determinare se T pu`o essere un RBT con radice di colore C ed altezza nera h.
1 Si scriva lo pseudocodice di una procedura per risolvere tale problema.
2 Si dimostri la correttezza della procedura proposta.
3 Si determini la complessit`a della procedura proposta.
Date: 16 Marzo 2009.
1
Documenti correlati
Nel caso C sia ROSSO le linee 8–9 effettuano questo controllo e le due chiamate ricorsive terminano correttamente per ipotesi induttiva2. lef t[x] pu` o essere NERO e radice di
Suggerimento: La procedura pi` u efficiente che si pu` o ottenere opera nello stesso tempo di una visita BFS. 3 Se ne dimostri
La correttezza della procedura Diametro Naive segue immediata- mente dalla definizione di diametro, dalla correttezza della procedura BFS e dal fatto che BFS(G, x) calcola le
[r]
Per refutare l’affermazione occorre invece trovare un controesempio.. Date: 11
Soluzione.. Inoltre si vede che E `e coercitivo. Quindi le orbite sono orbite chiuse attorno all’origine e girano in senso orario. Sono tutte orbite periodiche e l’origine `e stabile
PROBLEMA – Un rombo ha la diagonale maggiore di 12 cm , la diagonale minore che è 2/3 della diagonale maggiore e il lato che misura la metà della diagonale minore.. Calcola area
Ha senso sommare 12 treni e 300 passeggeri per sapere quante persone possono partire ogni giorno in treno per raggiungere Roma?. No , non ha
