Che cos'è un Quadtree?
Un quadtree è una struttura ad albero basata sulla potenza di quattro e utilizzata per organizzare i file in un database. Ogni nodo genitore o iniziale ha quattro nodi figlio e ogni figlio contiene una certa quantità di dati. Quando il limite di dati si estende oltre il suo limite, da quel nodo verranno creati quattro figli. Ci sono due principali strutture a quadrifoglio: la regione e l'albero dei punti, ognuno leggermente diverso nel design. Mentre un quadrifoglio viene spesso utilizzato con i database, può anche essere utilizzato per trovare pixel in immagini bidimensionali (2D), poiché i pixel in un'immagine 2D possono sempre essere separati in quattro parti.
Tutte le strutture ad albero sono realizzate con nodi padre, ramo, nodo e figlio, o foglia. Il genitore è il punto di partenza e contiene ampi dati basati su categorie, mentre il figlio detiene file e documenti. In un quadrifoglio, ogni genitore deve avere quattro figli. Mentre ci devono essere quattro figli, non tutti i bambini devono contenere dati; quelli senza sono noti come nodi null. Questi nodi null spesso rimangono stagnanti e attendono i dati.
Ogni nodo figlio in un quadtree ha un limite di dati. Questo limite è generalmente definito dalla dimensione complessiva del database. Quando ci sono così tante informazioni che oltrepassa il limite, il nodo figlio diventa un nodo genitore essenzialmente dando alla luce - creando quattro nodi figlio che occupano tutti i dati extra. Di solito ci saranno uno o due nodi null da questa creazione, ma questo dipende interamente dalla quantità di dati nel nodo.
Ci sono due quadricipiti principali: regione e punto. Il quadrilatero della regione viene utilizzato per scomporre un'intera regione 2D in parti basate sulla potenza di quattro, come quattro, otto o 16 parti, e spesso usato per le rappresentazioni. Questa struttura è ideale per immagini o grafici di campi dati. La versione dei punti è come un albero binario ed è utilizzata al meglio con i punti ordinati. Anche questa variante è un vero albero, perché esiste un punto centrale da cui scaturiscono tutti i nodi, a differenza della versione della regione in cui i nodi sono sparsi.
L'uso più comune di quadtree è di separare e organizzare un database, ma questo non è il suo unico utilizzo. Gli algoritmi fatti per trovare un pixel specifico in un'immagine usano comunemente quadricre, perché ogni pixel in un'immagine può essere separato in quattro parti uguali. Ciò rende i quadrifici particolarmente adatti alla ricerca di pixel.