Wat is een quadtree?

Een quadtree is een boomachtige structuur op basis van de kracht van vier en wordt gebruikt om bestanden in een database te ordenen. Elke ouder of beginnend knooppunt heeft vier onderliggende knooppunten en elk kind heeft een bepaalde hoeveelheid gegevens. Wanneer de datalimiet de grens overschrijdt, worden vier kinderen uit dat knooppunt gemaakt. Er zijn twee hoofdkwadrantenstructuren: de regio en de puntboom, elk iets anders qua ontwerp. Hoewel een quadtree meestal wordt gebruikt met databases, kan deze ook worden gebruikt om pixels in tweedimensionale (2D) afbeeldingen te vinden, omdat de pixels in een 2D-afbeelding altijd in vier delen kunnen worden gescheiden.

Alle boomachtige structuren zijn gemaakt met ouder, of tak, knopen en kind, of blad, knopen. De ouder is het startpunt en bevat brede op categorieën gebaseerde gegevens, terwijl het kind bestanden en documenten heeft. In een quadtree moet elke ouder vier kinderen hebben. Hoewel er vier kinderen moeten zijn, hoeven niet alle kinderen gegevens te bevatten; die zonder staan ​​bekend als nulknooppunten. Deze nulknooppunten blijven vaak stilstaan ​​en wachten op gegevens.

Elk kindknooppunt in een quadtree heeft een gegevenslimiet. Deze limiet wordt meestal bepaald door de totale databasegrootte. Wanneer er zoveel informatie is dat het de limiet overschrijdt, wordt het onderliggende knooppunt een ouderknooppunt door in wezen te bevallen - het creëren van vier onderliggende knooppunten die alle extra gegevens opnemen. Er zijn meestal een of twee nulknooppunten van deze creatie, maar dit hangt volledig af van hoeveel gegevens er in de knoop waren.

Er zijn twee hoofdkwadranten: regio en punt. De regio quadtree wordt gebruikt om een ​​volledig 2D-gebied op te delen in delen op basis van de kracht van vier - zoals vier, acht of 16 delen - en vaak gebruikt voor representaties. Deze structuur is het beste voor afbeeldingen of gegevensveldgrafieken. De puntversie is als een binaire boom en kan het best worden gebruikt met geordende punten. Deze variant is ook een echte boom, omdat er een centraal punt is waaruit alle knooppunten springen, in tegenstelling tot de regioversie waarin de knooppunten zijn verspreid.

Het meest voorkomende gebruik van de quadtree is het scheiden en organiseren van een database, maar dit is niet het enige gebruik. Algoritmen die worden gemaakt om een ​​specifieke pixel in een afbeelding te vinden, maken meestal gebruik van viertallen, omdat elke pixel in een afbeelding in vier gelijke delen kan worden gescheiden. Dit maakt quadtrees uniek geschikt voor het zoeken naar pixels.