Vad är ett fyrhjulingsträd?

Ett fyrhjulingsträd, ibland quadtree, q-tree eller qt, är datavetenskap term som hänvisar till en metod för att organisera data i fyra kvadranter.Databaser använder ibland fyrträd för att lagra och hitta sina skivor.Denna typ av organisationsstruktur fungerar särskilt bra för att hitta en viss bit eller pixel i en tvådimensionell bild.

Kvadträdet följer något träddatastrukturen som vanligtvis används i datavetenskap.Den normala träddatastrukturen ser ut som ett upp och ner träd, där en överordnad nod högst upp i trädet har en eller flera barnnoder anslutna till den.Varje annan nod på trädet har en överordnad nod och kan ha valfritt antal barnnoder, inklusive noll.

Till skillnad från en normal träddatastruktur, kräver en quad trädstruktur att varje intern nod har exakt fyra barnnoder.När du illustrerar de flesta fyrhjulingstrukturer ser du en nod som har fyra barnnoder som hänger från den, med linjer som förbinder modernoden med sina barnnoder.Illustrationen kan fortsätta, med ytterligare fyra barnnoder som hänger från var och en av de ursprungliga fyra barnnoderna.

Andra gånger kommer illustrationen av ett fyrdubblat träd en region eller en fyrkant.När regionen når sin maximala kapacitet för lagring av data är den uppdelad i fyra kvadranter.Normalt är regionerna och kvadranterna rutor, även om de också kan vara rektanglar eller andra former.

Ett fyrhjulingsträd är en bra datastruktur för att organisera pixlar på ett foto och för att organisera datorgrafik.Bilden kan delas upp i kvadranter och varje kvadrant kan delas upp i fyra till.Detta kan upprepas om och om igen tills du når nivån för enskilda pixlar.Om en kvadrant innehåller pixlar som alla har samma färg, finns det emellertid ingen anledning att ytterligare dela kvadranten.

Även om data lagrade i en quadträdstruktur kan kräva mycket lagringsutrymme jämfört med andra metoder för att organisera data för datorgrafik, Quad Tree -strukturen har flera fördelar.Först kan du ta bort hela fotografiet eller grafiken i ett enda steg genom att rensa rotnoden, som också rensar alla sina barnnoder.För det andra kan du snabbt minska upplösningen på ett fotografi genom att helt enkelt rensa den slutliga nivån på barnnoder.Detta kommer därmed att minska mängden lagringsutrymme det kräver.Slutligen är det lättare att hitta ett visst område på fotografiet för bildmanipulation.Även om fyrträd är begränsade till tvådimensionella bilder, kan en tredimensionell bild följa en liknande struktur, kallad en oktree, som är underavdelningen av en kub i åtta barn.