केडी पेड़: पत्तियों और नोड्स में संग्रहीत बनाम पत्तियों में संग्रहीत डेटा

Question

मैं निकटतम पड़ोसी और सी ++ में निकटतम पड़ोसी खोज करने के लिए एक केडी पेड़ को लागू करने की कोशिश कर रहा हूं। अब तक मैं सबसे बुनियादी केडी पेड़ के 2 संस्करणों में आया हूं।

1. एक है, जहां डेटा नोड्स में और पत्तियों में संग्रहीत किया जाता है, जैसे here
2. एक है, जहां डेटा केवल पत्तियों में संग्रहीत किया जाता है, इस तरह के here

के रूप में वे मौलिक रूप से होने लगते हैं वही, एक ही Asymptotic गुण होने के साथ।

मेरा प्रश्न है: क्या कोई कारण है कि एक दूसरे को चुनने का कोई कारण क्यों है?

1. पेड़ जो संग्रहीत करता है नोड्स में डेटा भी 1 स्तर से उथले है:

   मैं दो कारणों से अब तक लगा।

2. पेड़ जो केवल पत्तियों में डेटा संग्रहीत करता के लिए आसान delete data समारोह

लागू है वहाँ कुछ अन्य कारणों से निर्णय लेने से जो एक बनाने के लिए इससे पहले कि मैं पर विचार करना चाहिए रहे हैं?

Answer 1

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

पेड़ को लागू करने के लिए, मैं एक न्यूनतम संरचना का उपयोग करने की सलाह देता हूं। मैं आमतौर पर नोड्स का उपयोग करता हूं। मैं डेटा ऑब्जेक्ट संदर्भों की एक सरणी का उपयोग करता हूं। अक्ष को वर्तमान खोज गहराई द्वारा परिभाषित किया गया है, इसे कहीं भी स्टोर करने की आवश्यकता नहीं है। बाएं और दाएं पड़ोसियों को सरणी के बाइनरी खोज पेड़ द्वारा दिया जाता है। (अन्यथा, आपके द्वारा उपयोग किए गए अक्षों को संग्रहीत करने के लिए, बस अपने डेटासेट का आधा आकार byte) जोड़ें। पेड़ लोड करना एक विशेष क्विकॉर्ट द्वारा किया जाता है। सिद्धांत रूप में यह O(n^2) सबसे खराब मामला है, लेकिन एक अच्छी ह्युरिस्टिक जैसे कि मध्य -5 के रूप में आप O(n log n) काफी भरोसेमंद और न्यूनतम स्थिर ओवरहेड प्राप्त कर सकते हैं।

हालांकि यह सी/सी ++ के लिए ज्यादा नहीं है, कई अन्य भाषाओं में आप बहुत सारी वस्तुओं के प्रबंधन के लिए काफी कीमत चुकानी पड़ेगी। एक type*[] सबसे सस्ता डेटा संरचना है जो आपको मिलेगी, और विशेष रूप से इसे बहुत से प्रबंधन प्रयास की आवश्यकता नहीं है। तत्व को हटाए जाने के रूप में चिह्नित करने के लिए, आप null इसे देख सकते हैं, और null का सामना करते समय दोनों पक्षों को खोज सकते हैं। सम्मिलन के लिए, मैं पहले उन्हें एक बफर में एकत्रित करता था। और जब संशोधन काउंटर एक सीमा तक पहुंच जाता है, पुनर्निर्माण।

और यह उसका पूरा बिंदु है: यदि आपका पेड़ पुनर्निर्माण के लिए वास्तव में सस्ता है (लगभग पूर्व-क्रमबद्ध सरणी का उपयोग करने के रूप में सस्ता है!) तो यह अक्सर पेड़ के पुनर्निर्माण को नुकसान नहीं पहुंचाता है। एक छोटी "प्रविष्टि सूची" पर रैखिक स्कैनिंग बहुत सीपीयू कैश अनुकूल है। null एस छोड़ना बहुत सस्ता है।

यदि आप अधिक गतिशील संरचना चाहते हैं, तो मैं आर * -ट्री को देखने की सलाह देता हूं।वे वास्तव में आवेषण और हटाने पर संतुलन करने के लिए उत्सुक हैं, और डिस्क-उन्मुख ब्लॉक संरचना में डेटा व्यवस्थित करते हैं। लेकिन यहां तक ​​कि आर-पेड़ों के लिए, रिपोर्टें मिली हैं कि संरचनात्मक परिवर्तनों को स्थगित करने के लिए एक सम्मिलन बफर इत्यादि को बनाए रखना प्रदर्शन में सुधार करता है। और कई परिस्थितियों में थोक लोडिंग भी बहुत मदद करता है!