[Teoria] Quadtree e ricerca di città

[Studente Anonimo]

Ho preso un corso per informatici (e mi trovo un po' in difficoltà ) 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)

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)

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)

ans = SearchMostSouth(Q.root)
return ans.name

Dove
SearchMostSouth(Q.root)

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)

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

[Quinzio]

"3m0o":
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...

Non ho letto e capito tutto il post, ma in questo punto mi sembra che la tua domanda sia:
se una citta' A e' a nord di una citta' B, perche' poi non mi ritrovo la citta' B a sud della citta' A ?
Secondo me la risposta e' perche' sono esempi fatti male.
Invece di limitarsi alla spiegazione astratta dell'albero, vogliono sempre fare degli esempi concreti, ma alla fine il risultato e' che confondono le idee e nient'altro. Siamo a livello delle elementari, dove invece di chiedere quanto fa 10+10, fanno l'esempio di Pierino che va al mercato e compra 10 uova, ecc. ecc.

Comunque le tue risposte mi sembrano giuste come idea, il concetto l'hai capito, poi si tratta di implementarlo in questo o quel linguaggio di programmazione.
L'unica cosa che non si capisce e' perche' all'inizio si inizializza sempre v alla radice.
v = Q.root
E come fa a funzionare bene poi ?

[Studente Anonimo]

Quindi potrebbero non esserci delle foglie finali?

"Quinzio":
L'unica cosa che non si capisce e' perche' all'inizio si inizializza sempre v alla radice.
v = Q.root
E come fa a funzionare bene poi ?

Comunque io l'ho fatto per pigrizia di non scrivere ogni volta Q.root ma non so perché le soluzioni lo facciano.
Per funzionare bene intendo se fa quello che è richiesto che faccia l'algoritmo

[apatriarca]

Il tuo albero funziona in modo simile a un albero di ricerca binario, ma è pensato per dati bidimensionali invece che monodimensionali. A ogni livello scegli quindi un punto/città e vai a mettere le RESTANTI città nei quattro alberi figli. Neuchatel è già in F.NW e non può essere quindi anche in Y.NE che è contenuto in F.SW. Se una città potesse stare in più posizioni dell'albero non avresti più un albero ma un grafo e se ogni città contenesse come figli tutte le altre città avresti anche dei cicli e la tua ricerca andrebbe avanti all'infinito.

Per il secondo punto la tua soluzione e quella fornita differiscono principalmente nel valore di ritorno della funzione. Per il resto mi sembrano più o meno equivalenti. Non mi è però chiara la notazione che fa uso della virgola nella soluzione dell'esercizio.