Wat is een quad -boom?

Een quad tree, soms quadtree, q-tree of qt, is informatica-term die verwijst naar een methode voor het organiseren van gegevens in vier kwadranten.Databases gebruiken soms quadbomen om op te slaan en hun records te vinden.Dit type organisatiestructuur werkt vooral goed om een bepaald bit of pixel te vinden in een tweedimensionaal beeld.

De quad tree volgt enigszins de boomgegevensstructuur die vaak wordt gebruikt in de informatica.De normale boomgegevensstructuur ziet eruit als een ondersteboven boom, waarbij een bovenliggende knooppunt bovenaan de boom een of meer kinderknooppunten heeft aangesloten.Elke andere knooppunt in de boom heeft één bovenliggende knooppunt en kan een willekeurig aantal kinderknooppunten hebben, waaronder nul.

In tegenstelling tot een normale boomgegevensstructuur, vereist een quad tree -structuur dat elk interne knooppunt precies vier kinderknooppunten heeft.Bij het illustreren van de meeste quad tree -structuren ziet u een knooppunt met vier kinderknooppunten die eraan hangen, met lijnen die het bovenliggende knooppunt verbinden met zijn kinderknooppunten.De illustratie kan doorgaan, met nog vier kinderknooppunten die aan elk van de oorspronkelijke vier kinderknooppunten hangen.

Andere keren zal de illustratie van een quad -boom een regio of vierkant zijn.Wanneer de regio zijn maximale capaciteit bereikt om gegevens op te slaan, is deze verdeeld in vier kwadranten.Normaal gesproken zijn de gebieden en de kwadranten vierkanten, hoewel ze ook rechthoeken of andere vormen kunnen zijn.

Een quad -boom is een goede gegevensstructuur voor het organiseren van pixels in een foto en voor het organiseren van computerafbeeldingen.De foto kan worden verdeeld in kwadranten en elk kwadrant kan worden verdeeld in vier meer.Dit kan steeds opnieuw worden herhaald totdat u het niveau van individuele pixels bereikt.Als een kwadrant pixels bevat die allemaal dezelfde kleur hebben, is er echter geen reden om het kwadrant verder te verdelen.

Hoewel gegevens die zijn opgeslagen in een quad tree -structuur veel opslagruimte kunnen vereisen in vergelijking met andere methoden voor het organiseren van gegevens voor computerafbeeldingen, de quad tree -structuur heeft verschillende voordelen.Eerst kunt u de hele foto of afbeelding in een enkele stap verwijderen door het rootknooppunt te wissen, dat ook alle kinderknooppunten wist.Ten tweede kunt u snel de resolutie in een foto verminderen door eenvoudig het uiteindelijke niveau van kinderknooppunten te wissen.Dit zal daardoor de hoeveelheid opslagruimte verminderen die het vereist.Ten slotte is het vinden van een bepaald deel van de foto voor beeldmanipulatie eenvoudiger met de quad -boomstructuur.

Quadbomen worden ook in een paar andere situaties gebruikt, waaronder ruimtelijke indexering.Hoewel quadbomen beperkt zijn tot tweedimensionale beelden, kan het vertegenwoordigen van een driedimensionaal beeld een vergelijkbare structuur volgen, een octree genoemd, die de onderverdeling is van een kubus in acht kinderen.