Ett quad tree, ibland quadtree, Q-tree eller QT, är datavetenskaplig term som hänvisar till en metod för att organisera data i fyra kvadranter. Databaser använder ibland quad trees 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.
Quad-trädet följer till viss del den träddatastruktur som vanligtvis används inom datavetenskap. Den normala träddatastrukturen ser ut som ett upp och nervänt träd, där en föräldernod i toppen av trädet har en eller flera barnnoder kopplade till sig. Varannan nod i trädet har en föräldernod 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 quad-trädstrukturer ser du en nod som har fyra barnnoder som hänger från sig, med linjer som förbinder föräldernoden med dess 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 quad-träd att vara en region eller kvadrat. Närhelst regionen når sin maximala kapacitet för att lagra data delas den in i fyra kvadranter. Normalt är regionerna och kvadranterna kvadrater, även om de också kan vara rektanglar eller andra former.
Ett quad-träd är en bra datastruktur för att organisera pixlar i ett foto och för att organisera datorgrafik. Bilden kan delas in i kvadranter och varje kvadrant kan delas in 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 dela upp kvadranten ytterligare.
Även om data som lagras i en quad tree-struktur kan kräva mycket lagringsutrymme jämfört med andra metoder för att organisera data för datorgrafik, har quad tree-strukturen 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 dess undernoder. För det andra kan du snabbt minska upplösningen i ett fotografi genom att helt enkelt rensa den slutliga nivån av barnnoder. Detta kommer därmed att minska mängden lagringsutrymme som krävs. Slutligen är det lättare att hitta en viss del av fotografiet för bildmanipulation med fyrkantig trädstruktur.
Quad trees används också i några andra situationer, inklusive rumslig indexering. Även om quad trees är begränsade till tvådimensionella bilder, kan representerande en tredimensionell bild följa en liknande struktur, kallad en okträd, som är uppdelningen av en kub i åtta barn.