Hvad er et firetre?
En firtre er en trælignende struktur baseret på kraften fra fire og bruges til at organisere filer i en database. Hver forælder eller startende knude har fire underordnede noder, og hvert barn har en bestemt mængde data. Når datagrænsen spildes over dens grænse, oprettes fire børn fra denne knude. Der er to vigtigste firetræstrukturer: regionen og punkttræet, der hver især er forskellige i design. Mens et firetræ oftest bruges med databaser, kan det også bruges til at finde pixels i todimensionelle (2D) -billeder, fordi pixels i et 2D-billede altid kan opdeles i fire dele.
Alle trælignende strukturer er lavet med forælder eller gren, knudepunkter og barn eller bladknudepunkter. Forælderen er udgangspunktet og indeholder brede kategoribaserede data, mens barnet har filer og dokumenter. I en firetræ skal hver forælder have fire børn. Selvom der skal være fire børn, skal ikke alle børn indeholde data; dem uden er kendt som nulknudepunkter. Disse nulknudepunkter forbliver ofte stillestående og venter på data.
Hver barneknudepunkt i en firtre har en datagrænse. Denne grænse defineres normalt af den samlede databasestørrelse. Når der er så meget information, at det skubber ud over grænsen, bliver barneknudepunktet en forældreknude ved i det væsentlige at føde - skabe fire børneknuder, der optager alle de ekstra data. Der vil normalt være en eller to nulknudepunkter fra denne oprettelse, men dette afhænger helt af, hvor meget data der var i noden.
Der er to vigtigste firetræer: region og punkt. Regionens firetræ bruges til at nedbryde en hel 2D-region i dele baseret på styrken fra fire - såsom fire, otte eller 16 dele - og bruges ofte til repræsentationer. Denne struktur er bedst til billeder eller datafeltgrafer. Punktversionen er som et binært træ og bruges bedst med bestilte point. Denne variant er også et sandt træ, fordi der er et centralt punkt, hvorfra alle knudepunkter springer, i modsætning til den regionversion, hvor knudepunkterne er spredt.
Den mest almindelige brug af firtreet er at adskille og organisere en database, men dette er ikke dens eneste anvendelse. Algoritmer, der er lavet til at finde en bestemt pixel i et billede, bruger ofte firetræer, fordi hver pixel i et billede kan opdeles i fire lige store dele. Dette gør firtreet unikt egnet til at søge efter pixels.