Hva er en Quad Tree?

June 6  by Eliza

En quad treet, noen ganger firertre, er Q-treet eller QT, informatikk begrep som refererer til en metode for å organisere data i fire kvadranter. Databaser bruker noen ganger quad trær for å lagre og finne sine poster. Denne typen organisering fungerer spesielt godt for å finne en bestemt bit eller piksel i et todimensjonalt bilde.

Quad treet følger noe treet datastruktur som vanligvis brukes i informatikk. Den normale tre datastrukturen ser ut som en opp-ned treet, hvor en forelder node på toppen av treet har ett eller flere barn noder koblet til den. Annenhver node på treet har én forelder node og kan ha en rekke barn noder, inkludert null.

I motsetning til en vanlig tre datastruktur, krever en quad trestruktur at hver interne node har nøyaktig fire barn noder. Når som illustrerer de fleste quad trestrukturer, vil du se en node som har fire barn noder hengende fra det, med linjer som forbinder forelder node med sine barn noder. Illustrasjonen kan fortsette, med fire flere barnenoder som henger fra hver av de opprinnelige fire barnenoder.

Andre ganger vil illustrasjon av en quad treet være en region eller firkantet. Når regionen har nådd sin maksimale kapasitet for lagring av data, er det delt inn i fire kvadranter. Normalt regionene og kvadrantene er firkanter, selv om de kan være rektangler eller andre former også.

En quad treet er en god datastruktur for organisering av piksler i et bilde og for å organisere datagrafikk. Bildet kan deles inn i kvadranter, og hver kvadrant kan deles inn i fire til. Dette kan gjentas igjen og igjen til du kommer til nivået av individuelle piksler. Hvis en kvadrant inneholder piksler som er alle i samme farge, men det er ingen grunn til ytterligere dele kvadranten.

Selv om data som er lagret i en quad trestruktur kan kreve mye lagringsplass i forhold til andre måter å organisere data for datagrafikk, har quad trestruktur flere fordeler. Først kan du slette hele fotografi eller grafikk i et enkelt trinn ved å tømme rotnoden, som fjerner alle sine barn noder, også. Sekund, du raskt kan redusere oppløsningen i et bilde ved å fjerne det siste nivået av barn noder. Dette vil dermed redusere mengden lagringsplass det krever. Til slutt, finne et bestemt område av fotografiet for bildemanipulering er enklere med quad trestruktur.

Quad trær blir brukt i noen andre situasjoner, også, inkludert romlig indeksering. Selv quad trær er begrenset til to-dimensjonale bilder som representerer et tredimensjonalt bilde kan følge en lignende struktur, kalt en octree, som er inndelingen av en kube i åtte barn.