Den ursprungliga beskrivningen av k - d - trädet erkände att ombalanseringsmetoder, sådana som används för att bygga ett AVL - träd eller ett rödsvart träd, inte är tillämpliga på ett k - d - träd. För att bygga ett balanserat k - d - träd är det därför nödvändigt att finna medianen för uppgifterna för varje rekursiv indelning av dessa data. Den typ eller urval som används för att hitta medianen för varje indelning påverkar starkt beräknings komplexiteten i att bygga ett k - d träd. I det här dokumentet diskuteras en alternativ algoritm som bygger ett balanserat k - d- träd genom att försortera data i var och en av k- dimensionerna innan man bygger trädet. Den bevarar sedan ordningen för dessa k-sorter under trädkonstruktionen och undviker därmed kravet på ytterligare sortering. Dessutom är denna algoritm möjlig att utföra parallellt via flera trådar. Jämfört med en algoritm som finner medianvärdet för varje rekursiv indelning har denna försorteringsalgoritm motsvarande prestanda för fyra dimensioner och bättre prestanda för tre eller färre dimensioner.
Ett alternativt tillvägagångssätt är att upprätta ett balanserat k-d-träd, som föreslagits av REF.
Building a Balanced k-d Tree in O(kn log n) Time
{'venue': 'Journal of Computer Graphics Techniques (JCGT), vol. 4, no. 1, 50-68, 2015', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}