In totale sono due esercizi:
Esercizio 1:
Un BST esteso T è un BST in cui ogni nodo x di T ha, oltre ai campi standard, un campo n[x] che memorizza il numero di nodi presenti nel sottoalbero di T radicato in x (incluso x).
Si risponda ai seguenti quesiti.
a. Scrivere lo pseudocodice di una procedura efficiente InsertIntoExtendedBST(T, k) che inserisce la chiave intera k nel BST esteso T. Si calcoli la complessità e si dimostri la correttezza della procedura proposta.
b. Si consideri il problema dell’inserimento di una chiave in un BST esteso che è contemporaneamente un red-black tree. Quali modifiche sono necessarie? Si mostri come rispettare le proprietà dei BST estesi nel caso di una rotazione a sinistra.
Per quanto riguarda il punto a avevo pensato di modificare la funzione inserimento di un BST che mentre inserisce un nodo incrementa il campo n[x].
- Codice:
InsertIntoExtendedBST(T, k)
{
y = NIL
x = T.root
while x!=NIL
{
y = x
T.n[x] = T.n[x]+1
if z.key < x.key
x = x.left
else
x = x.right
}
z.p = y
if y == NIL
T.root = z
elseif z.key < y.key
y.left = z
else
y.right = z
}
La complessità rimane la stessa della funzione originale quindi O(h)
Il punto b invece ho qualche problema a trovare cosa devo aggiungere per rendere la funzione compatibile con i red black tree.
Per quanto riguarda le rotazioni a sinistra avevo invece notato che basta scambiare tra di loro i valori n[x] e n[y] (x è il nodo che dopo la rotazione "sale" di livello mentre y quello che "scende")
Esercizio 2:
Sia G = (V, E) un grafo orientato e aciclico.
Dato un nodo x ∈ V , l’altezza h[x] di x in G è definita come la lunghezza massima di un qualsiasi percorso da x ad una foglia (i.e., nodo senza archi uscenti) di G.
a. Scrivere lo pseudocodice di una procedura Height(G) che, dato G in input, calcoli, per ogni x ∈ V , l’altezza h[x] di x in G.
b. Si determini la complessità e si dimostri la correttezza della procedura proposta.
Qui non sono per nulla sicuro dello svolgimento che ho fatto
- Codice:
Height(G)
{
for(each v in G.V)
{
G.h[v] = 0
}
for(each v in G.V)
{
BFS(G, v) // Calcola il vettore delle distanze
for(each u in V)
{
if(u.adj == NIL && u != v) // Se la lista di adiacenza è nulla allora il nodo è una foglia
{
if(v.d[u] > h[v])
h[v] = v.d[u]
}
}
}
}
Qui avevo pensato di inizializzare l'array delle altezze a 0 e poi sfruttare l'array delle distanze ricavato da BFS, scorrerlo e vedere per i nodi con lista di adiacenza nulla (foglia) se l'altezza ricavata è maggiore di quella memorizzata in quel momento.
Questi sono gli esercizi, avviso che non mi son messo a guardare la complessità in quanto prima volevo essere sicuro dello svolgimento corretto. E' corretto quello che ho fatto oppure è completamente da rifare?