) stavo facendo un vecchio esame e questo è come ho risolto un esercizio.Un albero quadramentale è una struttura dati ad albero in cui ogni nodo interno ha esattamente quattro figli. In questo esercizio utilizzeremo un quadtree per rappresentare delle città in base alla loro posizione geografica.
NW sta per north-west, NE per north-east, SE per south-east e SW per south-west.
Ciascun nodo \(v\) del quadtree memorizza il nome \(v.name\) e le coordinate \(v.x\), \(v.y \) della città. Inoltre ciascun nodo contiene un puntatore \(v.p\) verso il suo nodo padre (o NIL se è la radice "root") e puntatori \(v.NW\), \( v.NE\), \(N.SE\) e \( v.SW\) verso i propri figli.
Domanda 1:
Mi fa un esempio di albero con 4 città, Friborgo (F), Yverdon (Y), Losanna (L) e Neuchatel (N).
Dove le coordinate sono rispettivamente (578461, 183802), (539316,181385), (537895,152098) e (561944,205330).
L'albero parte da Friborgo, e mi dice che il puntatore di Friborgo, F.NW va a Neuchatel (okay), F.NE e F.SE sono NIL (okay) mentre F.SW va a Losanna. Ora per Losanna mi dice L.NW è NIL, L.NE punta a Yverdon, e L.SE e L.SW anche vuoti. E okay, ma poi tutti i puntatori di Yverdon sono vuoti mi dice ma secondo me dovrebbe esserci il puntatore Y.NE che punta a Neuchatel perché Neuchatel sta a nord est di Yverdon, perché non c'è? Ugualmente mi dice che tutti i puntatori di Neuchatel sono vuoti...
Progetta un algoritmo (in pseudocodice) e analizza il tempo di esecuzione delle seguenti procedure per il quadrtee.
1) Search(Q.root,x,y) che restituisce il nome della città localizzata in \((x,y) \) se una tale città esiste nel quadree radicato in Q.root
2) PrintSouthMost(Q.root) - che restituisce il nome della città più a sud tra tutte.
Il tempo di esecuzione dovrebbe essere il più piccolo possibile per il caso tipico in cui l'altezza del quadrtee è logaritmico. Per ricevere il massimo dei punti la tua implementazione non deve avere un tempo di esecuzione eccessivamente alto.
Io per 1) ho fatto così:
Fondamentalmente implemento un algoritmo ricorsivo, che cerca se la radice è la città richiesta altrimenti cerca nel sottoalbero adatto dove il figlio diventa la nuova radice.
Search(Q.root,x,y)
- Codice:
v = Q.root
if v.x = x and v.y = y
return v.name
else
if x < v.x and y >= v.y
if v.NW not NIL
Search(v.NW,x,y)
else
return "error: no city with coordinate (x,y) exsits"
if x >= v.x and y > v.y
if v.NE not NIL
Search(v.NE,x,y)
else
return "error: no city with coordinate (x,y) exsits"
if x > v.x and y =< v.y
if v.SE not NIL
Search(v.SE,x,y)
else
return "error: no city with coordinate (x,y) exsits"
if x <= v.x and y < v.y
if v.SW not NIL
Search(v.SW,x,y)
else
return "error: no city with coordinate (x,y) exsits"
end
Ora ciascuna esecuzione di Search effettua solo operazioni che richiedono un tempo costante oppure richiama Search stessa. Chiaramente nel peggiore dei casi arriva in fondo all'albero quindi il tempo di esecuzione sarà \( \Theta(h) \) dove \(h\) è l'altezza dell'albero, quindi se è ben "bilanciato", ovvero \(h\) è logaritmico avrà un tempo di esecuzione che sarà un \( \Theta(\log n) \) dove \(n\) è numero delle città.
La soluzione al problema dice questo
Search(Q.root,x,y)
- Codice:
v = Q.root
if v= NIL
return does not exist
if v.x = x and v.y = y
return v
if x < v.x and y >= v.y
Search(v.NW,x,y)
if x >= v.x and y > v.y
Search(v.NE,x,y)
if x > v.x and y =< v.y
Search(v.SE,x,y)
if x <= v.x and y < v.y
Search(v.SW,x,y)
end
Io non capisco perché cerca subito che v non sia NIL, in che senso v può essere NIL ? Non capisco. Inoltre non capisco perché prima di richiamare, ad esempio, Search(v.NW,x,y) non controlla che tale nodo figlio esista effettivamente.
Per 2)
ho fatto così
PrintSouthMost(Q.root)
- Codice:
ans = SearchMostSouth(Q.root)
return ans.name
Dove
SearchMostSouth(Q.root)
- Codice:
v = Q.root
if v.SW == NIL and v.SE == NIL
return v
else
w = new element with all pointer set to NIL w.name is a fake name and w.x = 0 and w.y = infinity
e = new element with all pointer set to NIL w.name is a fake name and w.x = 0 and w.y = infinity
if v.SW not NIL
w = SearchMostSout(v.SW)
if v.SE not NIL
e = SearchMostSout(v.SE)
if w.y <= e.y
return w
if e.y <= w.y
return e
end
ma le soluzioni dicono questo
Dove
SearchMostSouth(Q.root)
- Codice:
v = Q.root
w = infinity
e = infinity
if v.SW not NIL
(w,wname) = SearchMostSout(v.SW)
if v.SE not NIL
(e,ename) = SearchMostSout(v.SE)
if w <= e, v.y
return (w,wname)
if e <= w, v.y
return (e,ename)
if v.y <= e,w
return (v.y,v.name)
end
Non capisco se il mio codice è sbagliato oppure se funziona bene e sono fondamentalmente lo stesso codice
