Un albero quad, a volte Quadtree, Q-albero o QT, è il termine computer science che si riferisce a un metodo di organizzazione dei dati in quattro quadranti. Basi di dati a volte usano quad alberi per archiviare e trovare i loro dischi. Questo tipo di struttura organizzativa funziona particolarmente bene per trovare un po 'particolare, o di pixel in una immagine bidimensionale.

L'albero quad segue un po' la struttura dati albero comunemente usato in informatica. La normale struttura dati albero assomiglia ad un albero a testa in giù, dove un nodo padre in cima l'albero ha uno o più figli nodi ad esso collegati. Ogni altro nodo su l'albero ha un nodo padre e possono avere qualsiasi numero di figli nodi, compreso lo zero.

A differenza di una normale struttura dati albero, una struttura quad albero richiede che ogni nodo interno ha esattamente quattro nodi figli . Quando si illustrano le strutture albero più quad, vedrete un nodo che ha quattro figli nodi appesi da esso, con linee che collegano il nodo padre con i suoi nodi figli. L'illustrazione può continuare, con i quattro figli più nodi appesi ciascuno dei primi quattro nodi figli.

Altre volte, l'illustrazione di un albero quad sarà una regione o di piazza. Ogni volta che la regione raggiunge la sua massima capacità per la memorizzazione dei dati, è diviso in quattro quadranti. Normalmente, le regioni e le quadranti sono piazze, anche se possono essere rettangoli o altre forme, anche.

Un albero quad è una buona struttura di dati per l'organizzazione di pixel in una foto e per l'organizzazione di computer grafica. L'immagine può essere suddiviso in quadranti, e ogni quadrante può essere suddiviso in quattro. Questo può essere ripetuto più e più volte fino a raggiungere il livello di singoli pixel. Se un quadrante contiene i pixel che sono tutti dello stesso colore, però, non c'è motivo di dividere ulteriormente il quadrante.

Anche se i dati memorizzati in una struttura ad albero quad può richiedere un sacco di spazio di memorizzazione rispetto ad altri metodi di organizzazione dei dati per la computer grafica, la struttura quad albero ha diversi vantaggi. In primo luogo, è possibile eliminare la fotografia o l'immagine intera in un'unica fase, cancellando il nodo principale, che cancella tutti i suoi nodi figli, anche. In secondo luogo, è possibile ridurre rapidamente la risoluzione di una foto semplicemente di compensazione il livello finale di nodi figli. Questo, in tal modo di ridurre la quantità di spazio di archiviazione che esso richiede. Infine, trovando una particolare area della fotografia per la manipolazione delle immagini è più facile con la struttura quad albero.

Quad alberi vengono utilizzati in alcune situazioni anche altri, tra cui l'indicizzazione spaziale. Anche se gli alberi quad sono limitati a due immagini bidimensionali, che rappresentano una immagine tridimensionale può seguire una struttura simile, chiamato Octree, che è la suddivisione di un cubo in otto figli.