Desidero confrontare l'R-Tree e il Quadtree per i dati geospaziali. Mentre c'è letteratura là fuori, faccio fatica a trovare documenti che coprano un reale confronto di base. Quindi ho deciso di fare questa domanda.Confronto tra alberi R e quadrilateri
A mio parere, l'R-Tree ha il vantaggio di essere equilibrato e l'albero non ha foglie vuote. Come svantaggio, l'operazione di base come l'inserimento o l'eliminazione potrebbe comportare la ristrutturazione dell'intero indice.
Il Quadtree è il contrario, non è bilanciato e ha le foglie vuote, ma non ha bisogno di essere ristabilito.
Quindi, da un punto di vista fatico, direi che l'R-Tree ha bisogno di meno memoria ed è più veloce per la ricerca a causa dell'altezza minima. Il quadruplo è migliore quando ci sono molte operazioni di aggiornamento, ma l'albero risultante potrebbe essere sbilanciato.
Questi punti sono corretti secondo lei? Ci sono dei buoni documenti là fuori che trattano questo argomento?
Auf Wiedersehen, Andre
"ristrutturazione dell'intero indice". No. La ristrutturazione è limitata a un singolo percorso, non all'indice "intero". Prendi in considerazione l'implementazione di entrambi e, facendo alcuni benchmark, per sapere davvero come si comportano. Non usare solo la teoria. –
ci sono molti diversi tipi di quad tree, quindi conosci la maggior parte di essi prima di provare a confrontare. inoltre una leggera variazione nell'implementazione può fornire tempi di esecuzione molto diversi (ad esempio, passare un oggetto rettangolo e passare 4 parametri x, y, larghezza, altezza). – AlexWien