बहुआयामी बाइनरी सर्च ट्री

मूल अवधारणा

बहुआयामी बाइनरी सर्च ट्री (संक्षिप्त के-डी ट्री) को मल्टीकी रिकॉर्ड्स को स्टोर करने के लिए डेटा संरचना के रूप में परिभाषित किया गया है। इस संरचना को सांख्यिकी और डेटा विश्लेषण में कई "ज्यामितीय" समस्याओं को हल करने के लिए लागू किया गया है।

एक के-डी पेड़ (के-आयामी पेड़ के लिए छोटा) को के-आयामी अंतरिक्ष में बिंदुओं को व्यवस्थित करने के लिए अंतरिक्ष-विभाजन डेटा संरचना के रूप में परिभाषित किया जाता है। डेटा संरचना k-d ट्री कई अनुप्रयोगों के लिए कार्यान्वित किए जाते हैं, उदाहरण के लिए, एक बहुआयामी खोज कुंजी (उदा. श्रेणी खोज और निकटतम पड़ोसी खोजें) वाली खोजें। k-d ट्री को बाइनरी स्पेस पार्टिशनिंग ट्री के विशेष मामले के रूप में माना जाता है।

अनौपचारिक विवरण

k-d ट्री एक बाइनरी ट्री है जिसमें प्रत्येक पत्ती नोड को k-आयामी बिंदु के रूप में माना जाता है। प्रत्येक गैर-पत्ती नोड की कल्पना की जा सकती है कि एक विभाजन हाइपरप्लेन (माध्यिका के रूप में प्रयुक्त) उत्पन्न होता है जो अंतरिक्ष को दो भागों में विभाजित करता है, जिसे आधा-रिक्त स्थान कहा जाता है। इस हाइपरप्लेन के बायीं ओर के पॉइंट्स को उस नोड के लेफ्ट सबट्री द्वारा ट्रीट किया जाता है और हाइपरप्लेन के दायीं ओर के पॉइंट्स को राइट सबट्री द्वारा ट्रीट किया जाता है। हम निम्न तरीके से हाइपरप्लेन दिशा का चयन कर सकते हैं:पेड़ में प्रत्येक नोड k आयामों में से एक के साथ जुड़ा हुआ है, साथ ही उस आयाम के अक्ष के लंबवत हाइपरप्लेन के साथ। इसलिए, उदाहरण के लिए, यदि किसी विशेष विभाजन के लिए "x" अक्ष का चयन किया जाता है, तो नोड से कम "x" मान वाले उपट्री में सभी बिंदु बाएं उपट्री में दिखाई देंगे और उच्च "x" मान वाले सभी बिंदु होंगे सही उपट्री में। ऐसी स्थिति में, हाइपरप्लेन को बिंदु के x-मान द्वारा सेट किया जाएगा, और इसका अभिलंब इकाई x-अक्ष को इंगित करता है। एक लोकप्रिय अभ्यास यादृच्छिक रूप से चयनित बिंदुओं की एक निश्चित संख्या को क्रमबद्ध करना है, और उन बिंदुओं के मध्य को विभाजित विमान के रूप में कार्य करने के लिए लागू करना है।

n बिंदुओं की सूची को देखते हुए, निम्न एल्गोरिथम उन बिंदुओं वाले संतुलित k-d ट्री बनाने के लिए माध्यिका-खोज प्रकार का उपयोग करता है।

function KDtree (list of points PointList, int Depth) {
   // Choose axis based on Depth so that axis cycles through all valid values
   var int axis := Depth mod k;
   // Sort point list and select median as pivot element
   choose median by axis from PointList;
   // Node is created as node1 and construct subtree
   node1.location := median;
   node1.leftChild := KDtree(points in PointList before median, Depth+1);
   node1.rightChild := KDtree(points in PointList after median, Depth+1);
   return node1;
}