Hva er en firetre?
En firetre er en trelignende struktur basert på kraften til fire og brukes til å organisere filer i en database. Hver foresatte eller startende node har fire underordnede noder, og hvert barn har en viss datamengde. Når datagrensen går over grensen, blir det laget fire barn fra den noden. Det er to hoveddeler med firetre: regionen og punktetreet, som hver er litt forskjellige i design. Mens en firetre oftest brukes med databaser, kan den også brukes til å finne piksler i todimensjonale (2D) bilder, fordi pikslene i et 2D-bilde alltid kan skilles i fire deler.
Alle trelignende strukturer er laget med foreldre eller gren, noder og barn, eller blad, noder. Forelderen er utgangspunktet og inneholder brede kategoribaserte data, mens barnet har filer og dokumenter. I en firetre må alle foreldre ha fire barn. Selv om det må være fire barn, er det ikke alle barn som må inneholde data; de uten er kjent som nullnoder. Disse nullknutene forblir ofte stillestående og venter på data.
Hver barneknute i en firetre har en datagrense. Denne grensen er vanligvis definert av den totale databasestørrelsen. Når det er så mye informasjon at den skyver utover grensen, blir barneknuten en overordnede knutepunkt ved å føde i grunnen - lage fire barneknuter som tar opp alle ekstra data. Det vil vanligvis være en eller to nullnoder fra denne opprettelsen, men dette avhenger helt av hvor mye data som var i noden.
Det er to viktigste firtrær: region og punkt. Regionens firetre brukes til å dekomponere en hel 2D-region i deler basert på kraften fra fire - for eksempel fire, åtte eller 16 deler - og brukes ofte til representasjoner. Denne strukturen er best for bilder eller datafeltgrafer. Poengversjonen er som et binærtre og brukes best med bestilte poeng. Denne varianten er også et ekte tre, fordi det er et sentralt punkt hvor alle nodene springer fra, i motsetning til regionversjonen der nodene er spredt.
Den vanligste bruken av firtreet er å skille og organisere en database, men dette er ikke den eneste bruken. Algoritmer laget for å finne en spesifikk piksel i et bilde, bruker vanligvis firtrær, fordi hver piksel i et bilde kan skilles i fire like deler. Dette gjør firtreet unikt for å søke etter piksler.