Hvad er et firhjulstræ?

Et firhjulstræ, undertiden firetræ, Q-træ eller QT, er datalogisk udtryk, der henviser til en metode til organisering af data i fire kvadranter. Databaser bruger undertiden firetræer til at gemme og finde deres poster. Denne type organisationsstruktur fungerer især godt til at finde en bestemt bit eller pixel i et to-dimensionelt billede.

Firhjulstræet følger lidt trædatastrukturen, der ofte bruges i datalogi. Den normale trædatastruktur ser ud som et hovedet træ, hvor en overordnet knude øverst på træet har en eller flere børneknuder, der er forbundet til det. Hver anden knude på træet har en overordnet knude og kan have et hvilket som helst antal børnknudepunkter, inklusive nul.

I modsætning til en normal trædatastruktur kræver en firhjulstræstruktur, at hver indre knude har nøjagtigt fire børneknuder. Når du illustrerer de fleste firhjulstræstrukturer, ser du en knude, der har fire børneknuder, der hænger fra den, med linjer, der forbinder overordnernoden med dets børneknuder. Illustrationen kan fortsætte, med fire flere børneknuder hængende fra hver af de originale fire børneknuder.

Andre gange vil illustrationen af ​​et firhjulstræ være en region eller firkant. Hver gang regionen når sin maksimale kapacitet til lagring af data, er den opdelt i fire kvadranter. Normalt er regionerne og kvadranterne firkanter, selvom de også kan være rektangler eller andre former.

Et firhjulstræ er en god datastruktur til at organisere pixels i et foto og til at organisere computergrafik. Billedet kan opdeles i kvadranter, og hver kvadrant kan opdeles i fire mere. Dette kan gentages igen og igen, indtil du når niveauet for de enkelte pixels. Hvis en kvadrant indeholder pixels, der alle er i samme farve, er der dog ingen grund til at opdele kvadranten yderligere.

Selvom data, der er gemt i en quad-træstruktur, kan kræve en masse lagerplads sammenlignet med andre metoder til organisering af data til computergrafik, har quad-træstrukturen flere fordele. Først kan du slette hele fotografiet eller grafikken i et enkelt trin ved at rydde rodnoden, som også rydder alle dens børneknuder. For det andet kan du hurtigt reducere opløsningen på et fotografi ved blot at rydde det endelige niveau for børneknuder. Dette vil derved reducere den mængde lagerplads, den kræver. Endelig er det lettere at finde et bestemt område på fotografiet til billedmanipulation med quad træstrukturen.

Firhjulstræer bruges også i et par andre situationer, inklusive rumlig indeksering. Selvom firhjulstræer er begrænset til todimensionelle billeder, kan det, der repræsenterer et tredimensionelt billede, følge en lignende struktur, kaldet en octree, som er en underinddeling af en terning i otte børn.