Hvad er en quadtree?

En quadtree er en trælignende struktur baseret på kraften i fire og bruges til at organisere filer i en database.Hver forælder eller start, knudepunkt har fire børnesknudepunkter, og hvert barn har en vis mængde data.Når databegrænsen spildes over dens grænse, vil der blive lavet fire børn fra denne knude.Der er to vigtigste quadtree -strukturer: regionen og punkttræet, hver lidt anderledes i design.Mens en quadtree oftest bruges med databaser, kan den også bruges til at finde pixels i to-dimensionelle (2D) billeder, fordi pixels i et 2D-billede altid kan adskilles i fire dele.

Alle trælignende strukturer erLavet med forælder eller gren, knudepunkter og barn eller blad, knudepunkter.Forælderen er udgangspunktet og indeholder brede kategoribaserede data, mens barnet har filer og dokumenter.I en quadtree skal enhver forælder have fire børn.Selvom der skal være fire børn, skal ikke alle børn indeholde data;De uden er kendt som nullknudepunkter.Disse nulknudepunkter forbliver ofte stillestående og venter på data.

Hver barneknude i en quadtree har en datagrænse.Denne grænse defineres normalt af den samlede databasestørrelse.Når der er så meget information, at den skubber ud over grænsen, bliver barnetknudepunktet en forældreknudepunkt ved i det væsentlige fødsel mdash;Oprettelse af fire børnesknudepunkter, 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 hovedkantkager: region og punkt.Regionen Quadtree bruges til at nedbryde en hel 2D -region til dele baseret på kraften i fire mdash;såsom fire, otte eller 16 dele mdash;og ofte brugt 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 knudepunkterne er, i modsætning til den regionversion, hvor knudepunkterne er spredt.

Den mest almindelige anvendelse af quadtree er at adskille og organisere en database, menDette er ikke dets eneste anvendelse.Algoritmer, der er lavet til at finde en specifik pixel i et billede, bruger ofte quadtrees, fordi hver pixel i et billede kan adskilles i fire lige store dele.Dette gør quadtrees unikt egnet til at søge pixels.