Kvadträd

Kvadträd, eller quadtree, är en datastruktur som används för att partitionera tvådimensionell rymd genom att rekursivt dela upp den i fyra kvadranter. Varje intern nod representerar ett visst område och har normalt fyra barn. Rotnoden täcker hela det området som ska hanteras. Namnet kommer av att varje uppdelning delar upp rymden i fyra delar: nordväst, nordöst, sydväst och sydost.

Strukturen kan vara flexibel: i vissa varianter innehåller varje löv endast en specifik punkt (punktkvadträd), medan andra versioner lagrar information om ett helt regionområde inom varje nod (regionskvadträd). En vanlig konstruktion är att varje nod kan vara en löv med en punkt eller en inre nod med fyra barn, och uppdelningen sker när antalet punkter i ett område överstiger en gräns.

Vanliga operationer inkluderar insättning av punkter, borttagning, sökningar och regionssökningar (range queries). Kvadträd används ofta för rumslig indexering, kollisionsdetektering i spel, bildkomprimering och geografiska informationssystem (GIS).

Prestanda varierar med fördelningen av datapunkter. Höjden på trädet är O(log n) i ett välbalanserat fall, men i värsta fall kan den bli O(n). Tidskomplexiteten för sökningar beror på antalet löv som måste traverseras och området som efterfrågas; i genomsnitt ger rangfrågor ofta nära O(log n + k) där k är antalet träffar.

Historiskt introducerades kvadträd inom datorgrafik och GIS under 1970- och 1980-talen. Det finns flera varianter, bland annat punktkvadträd, regionskvadträd, adaptiva kvadträd och komprimerade kvadträd. Likt andra rumsliga datastrukturer används kvadträd för effektiv hantering av tvådimensionell data och för att balansera prestanda och minne.