इंटरवलट्री डिलीट नोड जावा कार्यान्वयन

Question

मुझे जावा में IntervalTree या रेंज ट्री कार्यान्वयन की आवश्यकता है, और मुझे काम हटाने के समर्थन के साथ एक को खोजने में परेशानी हो रही है।

वहाँ एक अंतर्निहित sun.jvm.hotspot.utilities.IntervalTree में एक है, लेकिन RBTree सुपर क्लास राज्यों में deleteNode विधि है:

/** 
* FIXME: this does not work properly yet for augmented red-black 
* trees since it doesn't update nodes. Need to figure out exactly 
* from which points we need to propagate updates upwards. 
*/ 

से एक पेड़ अपवाद फेंक समाप्त होता है नोड्स को हटाने के लिए कोशिश कर रहा है:

नोड के अधिकतम एंडपॉइंट अपडेट नहीं किया गया ठीक से

यह कितना मुश्किल होगा sun.jvm.hotspot.utilities.IntervalTree के उप-वर्ग में delete कार्यक्षमता को लागू करें। या क्या एक और अंतराल वृक्ष कार्यान्वयन है जो पहले से ही इसे सही ढंग से लागू करता है?

वर्तमान में मैं सिर्फ पेड़ को मिटा रहा हूं और इसे हटाने के हर बार फिर से पॉप्युलेट कर रहा हूं, जो आदर्श से बहुत दूर है (नोट: आरबीटीरी में झूठी चीजों को झुकाव)।

Answer 1

मैंने हटाए गए नोड्स के सेट को बनाए रखने के लिए sun.jvm.hotspot.utilities.IntervalTree को संशोधित करना समाप्त कर दिया। खोज करते समय, मैं इस सेट में किसी भी आइटम को बाहर कर देता हूं। आदर्श नहीं है, लेकिन यह "असली" हटाना काम करने से बहुत आसान था। एक बार हटाए गए सेट को बहुत बड़ा हो जाता है, तो मैंने पेड़ का पुनर्निर्माण किया।

Answer 2

This project में एक श्रेणी ट्री कार्यान्वयन है जो आपके लिए अधिक उपयोग हो सकता है। सूरज पैकेज त्वरित और गंदे उपयोग के लिए ठीक हो सकते हैं, लेकिन मैं उन पर निर्भर महत्वपूर्ण कुछ भी बनाने की सिफारिश नहीं करता। सूर्य उन्हें स्थिर नहीं रख सकता है।

Answer 3

मुझे आपकी सटीक आवश्यकताओं को नहीं पता है लेकिन एक गैर स्थैतिक सेगमेंट ट्री आपके लिए काम कर सकती है। यदि ऐसा है, तो Layout Management SW पर विशेष रूप से देखें, विशेष रूप से SegmentTree package। इसमें आपकी आवश्यक सुविधा है।

यदि आप अपना खुद का रोल करने का निर्णय लेते हैं, तो क्या मैं इसे खुले सोर्सिंग का सुझाव दे सकता हूं? मुझे आश्चर्य है कि पहले से ही एक खुला और आसान अंतराल ट्री उपलब्ध नहीं है।

Answer 4

एक उन्नत एवीएल पेड़ @http://code.google.com/p/intervaltree/ के आधार पर एक सी # कार्यान्वयन है। जावा का अनुवाद बहुत मुश्किल नहीं होना चाहिए।

Answer 5

मुझे हटाने के साथ एक खुला स्रोत कार्यान्वयन मिला, लेकिन यह इसे पूरी तरह कार्यात्मक बनाने के लिए कुछ प्रयासों को पूरा करता है।

यह बड़ी खुली स्रोत परियोजना Gephi का एक मॉड्यूल है, लेकिन यहां sources और javadoc हैं। आप एक जार आप Gephi स्थापित कर सकते हैं चाहते हैं, और उस में बताया गया है:

/gephi/modules/org-gephi-data-attributes-api.jar 

हटाने विधि वहाँ, इनपुट अंतराल (के बजाय सिर्फ इनपुट एक) के साथ अतिव्यापी सभी अंतराल को हटा। हालांकि मुझे सॉर्सेस में पाया गया कि निजी विधियां हैं जो एक विशिष्ट नोड को हटाती हैं (जो एक अंतराल को स्टोर करती है)। निजी खोज विधियां नोड्स लौटती हैं।

तो मुझे लगता है कि कुछ छोटे प्रयासों के साथ कोड को दोबारा शुरू करना संभव है - यह 'विशिष्ट अंतराल को हटाएं' सुविधा है। सबसे तेज़ और सबसे गंदे तरीके से निजी विधियों/नोड वर्ग को सार्वजनिक बनाना होगा। लेकिन चूंकि यह एक ओपन सोर्स प्रोजेक्ट है, शायद यह भविष्य में अंतराल के पेड़ के कुछ अच्छे मानक कार्यान्वयन में विकसित हो सकता है।