Vad är ett fyrhjulsträd?
Ett fyrträd, ibland fyrtår, Q-träd eller QT, är datavetenskapligt benämning 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 poster. Denna typ av organisationsstruktur fungerar särskilt bra för att hitta en viss bit eller pixel i en tvådimensionell bild.
Fyrträdet följer något träddatastrukturen som vanligtvis används inom datavetenskap. Den normala träddatastrukturen ser ut som ett upp och ned träd, där en överordnad nod på toppen av 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 fyrhjärtstruktur att varje intern nod har exakt fyra barnnoder. När du illustrerar de flesta fyrhjärtstrukturer ser du en nod som har fyra barnnoder hängande från den med linjer som förbinder överordnad nod med sina barnnoder. Illustrationen kan fortsätta, med ytterligare fyra barnnoder hängande från var och en av de ursprungliga fyra barnnoderna.
Andra gånger kommer illustrationen av ett fyrhjulsträd att vara en region eller kvadrat. Närhelst regionen når sin maximala kapacitet för lagring av data, är den indelad i fyra kvadranter. Normalt är regionerna och kvadranten kvadrater, även om de också kan vara rektanglar eller andra former.
Ett fyrhjulsträd är en bra datastruktur för att organisera pixlar i 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 dock ingen anledning att ytterligare dela upp kvadranten.
Även om data lagrade i en fyrhjärtstruktur kan kräva mycket lagringsutrymme jämfört med andra metoder för att organisera data för datorgrafik, har fyrhjärtstrukturen 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 foto genom att helt enkelt rensa den slutliga nivån för 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 med fyrhjärtstrukturen.
Fyrhjulsträd används också i några andra situationer, inklusive rumslig indexering. Även om fyrträd är begränsade till tvådimensionella bilder, kan representera en tredimensionell bild följa en liknande struktur, kallad en oktre, som är en uppdelning av en kub i åtta barn.