Cos'è un quadroe?
Un Quadtree è una struttura simile a un albero basato sulla potenza di quattro e utilizzata per organizzare i file in un database. Ogni genitore, o iniziale, il nodo ha quattro nodi figlio e ogni figlio detiene una certa quantità di dati. Quando il limite di dati si riversa sul limite, verranno realizzati quattro bambini da quel nodo. Esistono due strutture quadtree principali: la regione e l'albero dei punti, ognuna leggermente diversa nel design. Mentre un Quadtree 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 a forma di albero sono realizzati con genitore o ramo, nodi e figli o foglie, nodi. Il genitore è il punto di partenza e contiene dati basati su categorie ampie, mentre il figlio detiene file e documenti. In un quadroe, ogni genitore deve avere quattro figli. Mentre ci devono essere quattro bambini, non tutti i bambini devono contenere dati; Quelli senza sono conosciuti come nodi null. Questi nodi null rimangono spessostagnante e attendere i dati.
Ogni nodo figlio in un quadroe ha un limite di dati. Questo limite è generalmente definito dalla dimensione complessiva del database. Quando ci sono così tante informazioni che spinge oltre il limite, il nodo figlio diventa un nodo genitore dando vita essenzialmente, creando quattro nodi figlio che occupano tutti i dati extra. Di solito ci saranno uno o due nodi nulli di questa creazione, ma questo dipende interamente da quanti dati fossero nel nodo.
Ci sono due quadri principali: regione e punto. La Quadtree della regione viene utilizzata per decomporre un'intera regione 2D in parti in base alla potenza di quattro - come quattro, otto o 16 parti - e spesso utilizzata per le rappresentazioni. Questa struttura è la migliore per le immagini o i grafici dei campi di dati. La versione punto è come un albero binario ed è meglio utilizzata con punti ordinati. Questa variante è anche un vero albero, perché c'è un punto centrale dache tutti i nodi si spengono, a differenza della versione della regione in cui sono sparsi i nodi.
L'uso più comune del Quadtree è separare e organizzare un database, ma questo non è il suo unico utilizzo. Gli algoritmi realizzati per trovare un pixel specifico in un'immagine usano comunemente quadtrees, poiché ogni pixel in un'immagine può essere separato in quattro parti uguali. Questo rende Quadtrees in modo univoco adatto alla ricerca di pixel.