डेटा संरचना रेंज

Question

किसी को भी डेटा संरचना जो कुशलता से निम्नलिखित स्थिति से निपटने के हैं की जानता है मैं सोच रहा हूँ:

डेटा संरचना, कई संभवतः अतिव्यापी, चर लंबाई संग्रहीत करना चाहिए कुछ निरंतर timescale पर बीच है।

• उदाहरण के लिए, आप a:[0,3], b:[4,7], c:[0,9] श्रेणियां जोड़ सकते हैं।

• सम्मिलन समय को विशेष रूप से कुशल होने की आवश्यकता नहीं है।

retrievals एक पैरामीटर के रूप एक सीमा ले जाएगा, और सेट है कि सीमा के साथ ओवरलैप में सभी सीमाओं, उदाहरण के लिए:

• Get(1,2) एक और ग लौट आते हैं। Get(6,7) बी और सी वापस आ जाएगा। Get(2,6) तीनों को वापस कर देगा।

• पुनर्प्राप्तियां यथासंभव कुशल होने की आवश्यकता है।

Answer 1

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

देखने के लिए, आप छोड़ दिया और शीर्ष नोड के सही subranges, और लोगों को जो ओवरलैप में गोता के खिलाफ अपने इनपुट रेंज का परीक्षण दोहरा जब तक आप वास्तविक पर्वतमाला है कि आप को बचाने के लिए पहुंच गए हैं।

इस तरह, पुनर्प्राप्ति में एक लॉगरिदमिक जटिलता है। आपको अभी भी अपने पुनर्प्राप्ति में डुप्लीकेट प्रबंधित करने की आवश्यकता होगी, क्योंकि कुछ श्रेणियां कई नोड्स से संबंधित हैं।

Answer 2

एक डेटा संरचना जिसका आप उपयोग कर सकते हैं वह एक आयामी R-tree है। ये श्रेणियों से निपटने और कुशल पुनर्प्राप्ति प्रदान करने के लिए डिज़ाइन किए गए हैं। आप Allen's Operators के बारे में भी जानेंगे; केवल 'ओवरलैप' की तुलना में समय अंतराल के बीच एक दर्जन अन्य संबंध हैं।

• SO 325933
• SO 210729

:

सहित कि इस क्षेत्र पर टकराना इतने पर अन्य प्रश्न, कर रहे हैं