मूल अवधारणा (Basic Concept)
बहुआयामी बाइनरी सर्च ट्री (संक्षिप्त k-d ट्री) को मल्टी-कुंजी रिकॉर्ड (Multi-key Records) स्टोर करने के लिए एक डेटा स्ट्रक्चर के रूप में परिभाषित किया जाता है। इस संरचना को सांख्यिकी और डेटा विश्लेषण में कई "ज्यामितीय" समस्याओं (Geometric Problems) को हल करने के लिए लागू किया गया है।
k-d ट्री (k-dimensional tree का संक्षिप्त) को k-आयामी स्थान (k-dimensional Space) में बिंदुओं को व्यवस्थित करने के लिए एक स्पेस-पार्टीशनिंग डेटा स्ट्रक्चर (Space-partitioning Data Structure) के रूप में परिभाषित किया जाता है। डेटा स्ट्रक्चर k-d ट्रीज़ कई अनुप्रयोगों के लिए लागू होते हैं, उदाहरण के लिए, बहुआयामी खोज कुंजी (Multidimensional Search Key) शामिल खोजें (जैसे रेंज खोज और निकटतम पड़ोसी खोज)। k-d ट्रीज़ को बाइनरी स्पेस पार्टीशनिंग ट्रीज़ (Binary Space Partitioning Trees) का एक विशेष मामला माना जाता है।
अनौपचारिक विवरण (Informal Description)
k-d ट्री एक बाइनरी ट्री है जिसमें हर लीफ नोड (Leaf Node) को k-आयामी बिंदु माना जाता है। हर नॉन-लीफ नोड को एक स्प्लिटिंग हाइपरप्लेन (Splitting Hyperplane) (मेडियन के रूप में उपयोग किया जाता है) को निहित रूप से उत्पन्न करने के रूप में कल्पना किया जा सकता है जो स्पेस को दो भागों में विभाजित करता है, जिन्हें हाफ-स्पेस (Half-spaces) कहा जाता है। इस हाइपरप्लेन के बाईं ओर के बिंदुओं को उस नोड के लेफ्ट सबट्री द्वारा दर्शाया जाता है और हाइपरप्लेन के दाईं ओर के बिंदुओं को राइट सबट्री द्वारा दर्शाया जाता है। हम निम्न तरीके से हाइपरप्लेन दिशा का चयन कर सकते हैं: ट्री में प्रत्येक नोड k आयामों में से एक से जुड़ा होता है, साथ ही उस आयाम के अक्ष के लंबवत हाइपरप्लेन के साथ। इसलिए, उदाहरण के लिए, यदि किसी विशेष विभाजन के लिए "x" अक्ष चुना जाता है, तो नोड से कम "x" मान वाले सबट्री में सभी बिंदु लेफ्ट सबट्री में दिखाई देंगे और उच्च "x" मान वाले सभी बिंदु राइट सबट्री में होंगे। ऐसे मामले में, हाइपरप्लेन बिंदु के x-मान द्वारा सेट किया जाएगा, और इसका सामान्य (Normal) यूनिट x-अक्ष को इंगित करेगा। एक लोकप्रिय अभ्यास यादृच्छिक रूप से चुने गए बिंदुओं की एक निश्चित संख्या को सॉर्ट करना है, और उन बिंदुओं के मेडियन (Median) को स्प्लिटिंग प्लेन के रूप में सेवा करने के लिए उपयोग करना है।
n बिंदुओं की सूची दी गई है, निम्न एल्गोरिदम उन बिंदुओं को समाहित करने वाला एक संतुलित k-d ट्री बनाने के लिए मेडियन-फाइंडिंग सॉर्ट (Median-finding Sort) का उपयोग करता है।
function KDtree (points की सूची PointList, int Depth) {
// Depth के आधार पर अक्ष चुनें ताकि अक्ष सभी मान्य मानों के माध्यम से चक्रित हो
var int axis := Depth mod k;
// पॉइंट सूची को सॉर्ट करें और अक्ष द्वारा मेडियन को पिवट एलिमेंट के रूप में चुनें
axis से PointList द्वारा मेडियन चुनें;
// नोड को node1 के रूप में बनाएं और सबट्री का निर्माण करें
node1.location := median;
node1.leftChild := KDtree(मेडियन से पहले PointList में बिंदु, Depth+1);
node1.rightChild := KDtree(मेडियन के बाद PointList में बिंदु, Depth+1);
return node1;
}
