Interval tree
कंप्यूटर विज्ञान में, एक अंतराल वृक्ष अंतराल रखने के लिए एक वृक्ष डेटा संरचना है। विशेष रूप से, यह किसी भी दिए गए अंतराल या बिंदु के साथ ओवरलैप होने वाले सभी अंतरालों को कुशलता से खोजने की अनुमति देता है। इसका उपयोग अक्सर विंडो प्रश्नों के लिए किया जाता है, उदाहरण के लिए, एक आयताकार व्यूपोर्ट के अंदर एक कम्प्यूटरीकृत मानचित्र पर सभी सड़कों को खोजने के लिए, या एक त्रि-आयामी दृश्य के अंदर सभी दृश्य तत्वों को खोजने के लिए। एक समान डेटा संरचना खंड वृक्ष है। तुच्छ समाधान यह है कि प्रत्येक अंतराल पर जाएँ और जाँच करें कि क्या यह दिए गए बिंदु या अंतराल को काटता है, जिसके लिए समय की आवश्यकता होती है, संग्रह में अंतराल की संख्या कहाँ है। चूँकि एक क्वेरी सभी अंतरालों को वापस कर सकती है, उदाहरण के लिए यदि क्वेरी संग्रह में सभी अंतरालों को काटता हुआ एक बड़ा अंतराल है, तो यह एसिम्प्टोटिक रूप से इष्टतम है; हालाँकि, हम आउटपुट-सेंसिटिव एल्गोरिदम पर विचार करके बेहतर कर सकते हैं, जहाँ रनटाइम को क्वेरी द्वारा उत्पादित अंतरालों की संख्या के संदर्भ में व्यक्त किया जाता है। अंतराल वृक्षों में एक प्रश्न समय और एक प्रारंभिक निर्माण समय होता है, जबकि स्मृति की खपत को सीमित करते हुए। निर्माण के बाद, अंतराल वृक्ष गतिशील हो सकते हैं, जो समय में एक अंतराल को कुशलता से डालने और हटाने की अनुमति देते हैं। यदि अंतरालों के अंतिम बिंदु एक छोटी पूर्णांक सीमा (जैसे, सीमा में) के भीतर हैं, तो दिए गए प्रश्न बिंदु वाले अंतरालों की रिपोर्ट करने के लिए पूर्व-प्रसंस्करण समय और प्रश्न समय के साथ तेज और वास्तव में इष्टतम डेटा संरचनाएं मौजूद हैं (एक बहुत ही सरल के लिए देखें)। सरल दृष्टिकोण एक साधारण मामले में, अंतराल ओवरलैप नहीं होते हैं और उन्हें एक साधारण द्विआधारी खोज वृक्ष में डाला जा सकता है और समय पर पूछताछ की जा सकती है। हालाँकि, मनमाने ढंग से अतिव्यापी अंतरालों के साथ, पेड़ में डालने के लिए दो अंतरालों की तुलना करने का कोई तरीका नहीं है क्योंकि प्रारंभिक बिंदुओं या अंतिम बिंदुओं द्वारा क्रमबद्ध क्रम अलग-अलग हो सकते हैं। एक सरल दृष्टिकोण दो समानांतर पेड़ों का निर्माण करना हो सकता है, एक प्रारंभ बिंदु द्वारा क्रमबद्ध, और एक प्रत्येक अंतराल के अंत बिंदु द्वारा क्रमबद्ध। यह समय पर प्रत्येक पेड़ के आधे हिस्से को फेंकने की अनुमति देता है, लेकिन परिणामों को विलय किया जाना चाहिए, जिसमें समय की आवश्यकता होती है। यह हमें सवाल देता है, जो ब्रूट-फोर्स से बेहतर नहीं है। अंतराल वृक्ष इस समस्या का समाधान करते हैं। यह लेख एक अंतराल वृक्ष के लिए दो वैकल्पिक डिजाइनों का वर्णन करता है, जिन्हें केंद्रित अंतराल वृक्ष और संवर्धित वृक्ष कहा जाता है। केंद्रित अंतराल वृक्ष प्रश्नों के लिए समय की आवश्यकता होती है, जिसमें अंतरालों की कुल संख्या और रिपोर्ट किए गए परिणामों की संख्या होती है। निर्माण में समय लगता है और भंडारण के लिए जगह की आवश्यकता होती है। संख्या रेखा पर अंतरालों के एक समूह को देखते हुए, हम एक डेटा संरचना का निर्माण करना चाहते हैं ताकि हम किसी अन्य अंतराल या बिंदु को ओवरलैप करने वाले सभी अंतरालों को कुशलता से प्राप्त कर सकें। हम सभी अंतरालों की पूरी श्रृंखला को लेकर शुरू करते हैं और इसे आधे में विभाजित करते हैं (व्यवहार में, पेड़ को अपेक्षाकृत संतुलित रखने के लिए चुना जाना चाहिए)। यह अंतराल के तीन सेट देता है, जो पूरी तरह से बाईं ओर हैं जिन्हें हम कॉल करेंगे, जो पूरी तरह से दाईं ओर हैं जिन्हें हम कॉल करेंगे, और जो ओवरलैपिंग हैं जिन्हें हम कॉल करेंगे। अंतराल में और पुनरावर्ती रूप से उसी तरीके से विभाजित होते हैं जब तक कि कोई अंतराल नहीं बचा है। केंद्र बिंदु को ओवरलैप करने वाले अंतराल को अंतराल वृक्ष में नोड से जुड़ी एक अलग डेटा संरचना में संग्रहीत किया जाता है। इस डेटा संरचना में दो सूचियाँ होती हैं, एक में उनके प्रारंभिक बिंदुओं द्वारा क्रमबद्ध सभी अंतराल होते हैं, और दूसरे में उनके अंतिम बिंदुओं द्वारा क्रमबद्ध सभी अंतराल होते हैं। परिणाम प्रत्येक नोड भंडारण के साथ एक द्विआधारी वृक्ष हैः एक केंद्र बिंदु दूसरे नोड के लिए एक सूचक जिसमें केंद्र बिंदु के बाईं ओर पूरी तरह से सभी अंतराल होते हैं एक दूसरे नोड के लिए एक सूचक जिसमें केंद्र बिंदु के दाईं ओर पूरी तरह से सभी अंतराल होते हैं सभी अंतराल केंद्र बिंदु को ओवरलैप करते हैं जो उनके प्रारंभिक बिंदु द्वारा क्रमबद्ध किए जाते हैं सभी अंतराल केंद्र बिंदु को ओवरलैप करते हैं जो उनके अंतिम बिंदु इंटरसेक्टिंग द्वारा क्रमबद्ध किए जाते हैं ऊपर निर्मित डेटा संरचना को देखते हुए, हम श्रेणियों या बिंदुओं से युक्त प्रश्न प्राप्त करते हैं, और इस इनपुट को ओवरलैप करने वाले मूल सेट में सभी श्रेणियों को वापस करते हैं। एक बिंदु के साथ कार्य पेड़ में सभी अंतरालों को खोजना है जो एक दिए गए बिंदु को ओवरलैप करते हैं। पेड़ को एक समान पुनरावर्ती एल्गोरिथ्म के साथ चलाया जाता है जैसा कि एक पारंपरिक द्विआधारी पेड़ को पार करने के लिए उपयोग किया जाता है, लेकिन प्रत्येक नोड पर "केंद्र" बिंदु को ओवरलैप करने वाले अंतरालों को खोजने में सहायता करने के लिए अतिरिक्त तर्क के साथ। प्रत्येक ट्री नोड के लिए, ऊपर नोड निर्माण में उपयोग किए जाने वाले मध्य बिंदु से तुलना की जाती है। यदि इससे कम है, तो अंतरालों के सबसे बाएँ समूह पर विचार किया जाता है। यदि इससे अधिक है, तो अंतरालों का सबसे सही सेट माना जाता है। जैसा कि प्रत्येक नोड को संसाधित किया जाता है जब हम पेड़ को जड़ से एक पत्ते तक पार करते हैं, तो इसकी श्रेणियों को संसाधित किया जाता है। यदि उससे कम है, तो हम जानते हैं कि सभी अंतराल अंत में बाद में, या वे भी ओवरलैप नहीं कर सकते हैं। इसलिए, हमें केवल उन अंतरालों को खोजने की आवश्यकता है जो पहले शुरू होते हैं। हम उन सूचियों को देख सकते हैं जिनका निर्माण पहले ही किया जा चुका है। चूँकि हम इस परिदृश्य में केवल अंतराल की शुरुआत की परवाह करते हैं, हम शुरुआत के अनुसार क्रमबद्ध सूची से परामर्श कर सकते हैं। मान लीजिए कि हम इस सूची में निकटतम संख्या को उससे बड़ी नहीं पाते हैं। सूची की शुरुआत से लेकर पाए गए बिंदु तक सभी श्रेणियां ओवरलैप होती हैं क्योंकि वे पहले शुरू होती हैं और बाद में समाप्त होती हैं (जैसा कि हम जानते हैं क्योंकि वे ओवरलैप होती हैं जो उससे बड़ी होती हैं)। इस प्रकार, हम सूची में अंतरालों की गणना तब तक शुरू कर सकते हैं जब तक कि प्रारंभिक बिंदु मूल्य अधिक न हो जाए। इसी तरह, यदि उससे अधिक है, तो हम जानते हैं कि सभी अंतराल पहले शुरू होने चाहिए, इसलिए हम उन अंतरालों को पाते हैं जो अंतराल अंत द्वारा क्रमबद्ध सूची का उपयोग करने के बाद समाप्त होते हैं। यदि वास्तव में मेल खाता है, तो सभी अंतरालों को आगे की प्रक्रिया के बिना परिणामों में जोड़ा जा सकता है और ट्री ट्रैवर्सल को रोका जा सकता है। एक अंतराल के साथ एक परिणाम अंतराल के लिए हमारे प्रश्न अंतराल को प्रतिच्छेद करने के लिए निम्नलिखित में से एक को धारण करना चाहिएः का प्रारंभ और/या अंत बिंदु है; या पूरी तरह से संलग्न है। हम सबसे पहले एक अलग से निर्मित पेड़ का उपयोग करके अंदर शुरू और/या अंत बिंदुओं के साथ सभी अंतराल पाते हैं। एक-आयामी मामले में, हम एक खोज वृक्ष का उपयोग कर सकते हैं जिसमें अंतराल सेट में सभी प्रारंभ और अंत बिंदु होते हैं, जिनमें से प्रत्येक अपने संबंधित अंतराल के लिए एक सूचक के साथ होता है। शुरुआत और अंत के लिए समय पर द्विआधारी खोज से विचार करने के लिए न्यूनतम और अधिकतम बिंदु प्रकट होते हैं। इस सीमा के भीतर प्रत्येक बिंदु एक अंतराल को संदर्भित करता है जो ओवरलैप होता है और परिणाम सूची में जोड़ा जाता है। दोहराव से बचने के लिए सावधानी बरतनी चाहिए, क्योंकि एक अंतराल शुरू और अंत दोनों हो सकता है। यह प्रत्येक अंतराल पर एक द्विआधारी ध्वज का उपयोग करके किया जा सकता है ताकि यह चिह्नित किया जा सके कि इसे परिणाम सेट में जोड़ा गया है या नहीं। अंत में, हमें ऐसे अंतराल ढूंढने चाहिए जो संलग्न हों। इन्हें खोजने के लिए, हम किसी भी बिंदु को अंदर से चुनते हैं और उस बिंदु को काटते हुए सभी अंतरालों को खोजने के लिए ऊपर दिए गए एल्गोरिदम का उपयोग करते हैं (फिर से, डुप्लिकेट को हटाने के लिए सावधान रहना)। उच्च आयाम अंतराल वृक्ष डेटा संरचना को समान प्रश्न और निर्माण समय और स्थान के साथ उच्च आयाम के लिए सामान्यीकृत किया जा सकता है। सबसे पहले, आयामों में एक रेंज ट्री का निर्माण किया जाता है जो क्वेरी क्षेत्र के अंदर शुरुआत और अंत बिंदुओं के साथ सभी अंतरालों की कुशल पुनर्प्राप्ति की अनुमति देता है। एक बार जब संबंधित श्रेणियाँ मिल जाती हैं, तो केवल वे श्रेणियाँ बची रहती हैं जो इस क्षेत्र को किसी आयाम में घेरती हैं। इन अतिव्याप्तियों को खोजने के लिए, अंतराल वृक्ष बनाए जाते हैं, और प्रत्येक के लिए एक प्रतिच्छेदन अक्ष से पूछताछ की जाती है। उदाहरण के लिए, दो आयामों में, वर्ग के निचले भाग (या किसी अन्य क्षैतिज रेखा को काटते हुए) से क्षैतिज अक्ष के लिए बनाए गए अंतराल वृक्ष के खिलाफ पूछताछ की जाएगी। इसी तरह, बाईं ओर (या प्रतिच्छेदन करने वाली किसी अन्य ऊर्ध्वाधर रेखा) से ऊर्ध्वाधर अक्ष पर निर्मित अंतराल वृक्ष के खिलाफ पूछताछ की जाएगी। प्रत्येक अंतराल वृक्ष को उच्च आयामों के लिए एक जोड़ की भी आवश्यकता होती है। प्रत्येक नोड पर हम पेड़ में पार करते हैं, ओवरलैप खोजने के लिए तुलना की जाती है। एक आयामी मामले में उपयोग की जाने वाली बिंदुओं की दो क्रमबद्ध सूचियों के बजाय, एक रेंज ट्री का निर्माण किया जाता है। यह उस ओवरलैप क्षेत्र में सभी बिंदुओं की कुशल पुनर्प्राप्ति की अनुमति देता है। विलोपन यदि वृक्ष से एक अंतराल को हटाने के बाद, उस अंतराल वाले नोड में कोई और अंतराल नहीं होता है, तो उस नोड को वृक्ष से हटा दिया जा सकता है। यह एक सामान्य द्विआधारी वृक्ष हटाने के ऑपरेशन की तुलना में अधिक जटिल है। एक अंतराल वृक्ष में कई नोड्स के केंद्र बिंदु को ओवरलैप कर सकता है। चूँकि प्रत्येक नोड उन अंतरालों को संग्रहीत करता है जो इसे ओवरलैप करते हैं, सभी अंतरालों के साथ पूरी तरह से बाएं सबट्री में अपने केंद्र बिंदु के बाईं ओर, इसी तरह दाएं सबट्री के लिए, यह इस प्रकार है कि प्रत्येक अंतराल को नोड्स के सेट से रूट के निकटतम नोड में संग्रहीत किया जाता है जिसका केंद्र बिंदु यह ओवरलैप करता है। एक द्विआधारी वृक्ष में सामान्य विलोपन संचालन (उस मामले के लिए जहां नोड को हटाया जा रहा है, दो बच्चे हैं) में पत्ती से आगे नोड को हटाने की स्थिति (आमतौर पर दाएं सबट्री का सबसे बाएँ वाला बच्चा, या बाएँ सबट्री का सबसे दाएँ वाला बच्चा) तक बढ़ावा देना शामिल है। इस पदोन्नति के परिणामस्वरूप, कुछ नोड्स जो प्रचारित नोड के ऊपर थे, वे इसके वंशज बन जाएंगे; इन नोड्स को उन अंतरालों के लिए खोजना आवश्यक है जो प्रचारित नोड को भी ओवरलैप करते हैं, और उन अंतरालों को प्रचारित नोड में स्थानांतरित करते हैं। नतीजतन, इसके परिणामस्वरूप नए खाली नोड्स हो सकते हैं, जिन्हें उसी एल्गोरिथ्म का फिर से पालन करते हुए हटा दिया जाना चाहिए। संतुलन वही मुद्दे जो हटाने को प्रभावित करते हैं, वे भी घूर्णन संचालन को प्रभावित करते हैं; घूर्णन को इस अपरिवर्तनीय को संरक्षित करना चाहिए कि नोड्स को जड़ के जितना संभव हो सके उतना करीब संग्रहीत किया जाता है। संवर्धित वृक्ष अंतराल का प्रतिनिधित्व करने का एक अन्य तरीका इसमें वर्णित है। सम्मिलन और विलोपन दोनों के लिए समय की आवश्यकता होती है, जिसमें सम्मिलन या विलोपन संचालन से पहले पेड़ में अंतराल की कुल संख्या होती है। एक संवर्धित वृक्ष को एक साधारण क्रमबद्ध वृक्ष से बनाया जा सकता है, उदाहरण के लिए एक द्विआधारी खोज वृक्ष या आत्म-संतुलित द्विआधारी खोज वृक्ष, जो अंतराल के 'निम्न' मूल्यों द्वारा क्रमबद्ध किया जाता है। फिर प्रत्येक नोड में एक अतिरिक्त एनोटेशन जोड़ा जाता है, जो इस नोड से नीचे के सभी अंतरालों के बीच अधिकतम ऊपरी मान को रिकॉर्ड करता है। इस विशेषता को बनाए रखने में नोड के सभी पूर्वजों को नीचे से ऊपर तक अपडेट करना शामिल है जब भी कोई नोड जोड़ा या हटाया जाता है। यह प्रति नोड जोड़ या हटाने के लिए केवल ओ (एच) कदम उठाता है, जहां एच पेड़ में जोड़े गए या हटाए गए नोड की ऊंचाई है। यदि सम्मिलन और विलोपन के दौरान कोई वृक्ष आवर्तन होता है, तो प्रभावित नोड्स को भी अद्यतन करने की आवश्यकता हो सकती है। अब, यह ज्ञात है कि दो अंतराल और केवल तभी ओवरलैप होते हैं जब दोनों और। दिए गए अंतराल के साथ ओवरलैपिंग नोड्स के लिए पेड़ों की खोज करते समय, आप तुरंत छोड़ सकते हैंः नोड्स के दाईं ओर सभी नोड्स जिनका कम मूल्य दिए गए अंतराल के अंत से आगे है। सभी नोड्स जिनका अधिकतम उच्च मान दिए गए अंतराल की शुरुआत से नीचे है। सदस्यता प्रश्न कुछ प्रदर्शन प्राप्त किया जा सकता है यदि पेड़ अनावश्यक यात्राओं से बचता है। ये तब हो सकते हैं जब पहले से मौजूद अंतरालों को जोड़ा जाए या उन अंतरालों को हटाया जाए जो मौजूद नहीं हैं। अंतराल पर कुल क्रम को पहले उनकी निचली सीमा से और फिर उनकी ऊपरी सीमा से क्रमबद्ध करके परिभाषित किया जा सकता है। फिर, एक सदस्यता जांच समय पर की जा सकती है, बनाम डुप्लिकेट खोजने के लिए आवश्यक समय यदि अंतराल डालने या हटाने के लिए अंतराल को ओवरलैप करते हैं। इस समाधान में किसी भी अतिरिक्त संरचना की आवश्यकता नहीं होने का लाभ है। परिवर्तन सख्ती से एल्गोरिदमिक है। इसका नुकसान यह है कि सदस्यता संबंधी प्रश्नों में समय लगता है। वैकल्पिक रूप से, स्मृति की दर पर, अपेक्षित निरंतर समय में सदस्यता प्रश्नों को हैश टेबल के साथ लागू किया जा सकता है, जिसे अंतराल वृक्ष के साथ लॉकस्टेप में अद्यतन किया जाता है। यह आवश्यक रूप से कुल स्मृति आवश्यकता को दोगुना नहीं कर सकता है, यदि अंतराल मूल्य के बजाय संदर्भ द्वारा संग्रहीत किए जाते हैं। जावा उदाहरण-वृक्ष में एक नया अंतराल जोड़ना प्रत्येक नोड की कुंजी स्वयं अंतराल होती है, इसलिए नोड्स को पहले कम मूल्य और अंत में उच्च मूल्य द्वारा क्रमबद्ध किया जाता है, और प्रत्येक नोड का मूल्य अंतराल का अंतिम बिंदु होता हैः सार्वजनिक शून्य जोड़ (अंतराल i) {पुट (i, i.getEnd ());} जावा उदाहरण-वृक्ष में एक बिंदु या अंतराल की खोज करना अंतराल की खोज करने के लिए, कोई व्यक्ति वृक्ष पर चलता है, कुंजी (n.getKey ()) और उच्च मूल्य (n.getValue ()) का उपयोग करके किसी भी शाखा को छोड़ देता है जो क्वेरी को ओवरलैप नहीं कर सकती है। सबसे सरल मामला एक बिंदु प्रश्न हैः// "p" वाले सभी अंतरालों के लिए खोज करें, जो// नोड "n" से शुरू होते हैं और सूची "परिणाम" सार्वजनिक शून्य खोज (इंटरवल नोड n, पॉइंट p, लिस्ट <अंतराल> परिणाम) में मिलान अंतराल जोड़ते हैं। यदि (p.compareTo (n.getValue ())> 0) लौटता है;// बाएं बच्चों की खोज करें (n.getLeft (), p, परिणाम);// इस नोड की जाँच करें यदि (n.getKey (). इसमें (p)) result.add (n.getKey ());// यदि p इस अंतराल की शुरुआत के बाईं ओर है,// तो यह किसी भी बच्चे में दाईं ओर नहीं हो सकता है। यदि (p.compareTo (n.getKey (). GetStart ())) <0) लौटता है;// अन्यथा, सही बच्चों की खोज करें (n.getRight (), p, परिणाम);} जहाँ a.compareTo (b) एक नकारात्मक मान देता है यदि a <b a.compareTo (b) शून्य लौटाता है यदि a = b a.compareTo (b) एक सकारात्मक मान देता है यदि a> b अंतराल खोजने के लिए कोड समान है, सिवाय बीच में चेक केः// इस नोड की जाँच करें यदि (n.getKey (). ओवरलैप्स के साथ (i)) result.add (n.getKey (); ओवरलैप्स के साथ () परिभाषित किया गया हैः सार्वजनिक उदाहरण के लिए, दो आयामों के लिए, पेड़ के विषम स्तरों में x-निर्देशांक के लिए सीमाएँ हो सकती हैं, जबकि सम स्तरों में y-निर्देशांक के लिए सीमाएँ होती हैं। यह दृष्टिकोण प्रभावी रूप से डेटा संरचना को एक संवर्धित द्विआधारी वृक्ष से एक संवर्धित केडी-वृक्ष में परिवर्तित करता है, इस प्रकार सम्मिलन और विलोपन के लिए संतुलन एल्गोरिदम को महत्वपूर्ण रूप से जटिल बनाता है। एक सरल समाधान नेस्टेड इंटरवल ट्री का उपयोग करना है। सबसे पहले, y-निर्देशांक के लिए श्रेणियों का उपयोग करके एक वृक्ष बनाएँ। अब, ट्री में प्रत्येक नोड के लिए, एक्स-रेंज पर एक और अंतराल ट्री जोड़ें, उन सभी तत्वों के लिए जिनकी वाई-रेंज उस नोड की वाई-रेंज के समान है। इस समाधान का लाभ यह है कि इसे एक ही कोड आधार का उपयोग करके मनमाने ढंग से कई आयामों तक बढ़ाया जा सकता है। शुरू में, घोंसले वाले पेड़ों की अतिरिक्त लागत निषेधात्मक लग सकती है, लेकिन आमतौर पर ऐसा नहीं होता है। जैसा कि पहले गैर-नेस्टेड समाधान के साथ होता था, प्रति x-निर्देशांक के लिए एक नोड की आवश्यकता होती है, जिससे दोनों समाधानों के लिए समान संख्या में नोड प्राप्त होते हैं। केवल अतिरिक्त उपरिभाग नेस्टेड ट्री संरचनाओं का है, एक प्रति ऊर्ध्वाधर अंतराल। यह संरचना आमतौर पर नगण्य आकार की होती है, जिसमें केवल रूट नोड के लिए एक सूचक होता है, और संभवतः नोड्स की संख्या और पेड़ की गहराई होती है। मध्य-या लंबाई-उन्मुख वृक्ष एक मध्य-या लंबाई-उन्मुख वृक्ष एक संवर्धित वृक्ष के समान होता है, लेकिन सममित होता है, जिसमें द्विआधारी खोज वृक्ष अंतराल के मध्य बिंदु द्वारा क्रमबद्ध होता है। प्रत्येक नोड में एक अधिकतम-उन्मुख द्विआधारी ढेर होता है, जो अंतराल की लंबाई (या लंबाई का आधा) द्वारा क्रमबद्ध होता है। इसके अलावा हम प्रत्येक नोड में सबट्री के न्यूनतम और अधिकतम संभव मूल्य को संग्रहीत करते हैं (इस प्रकार समरूपता)। ओवरलैप परीक्षण केवल दो अंतरालों के प्रारंभ और अंत मूल्यों का उपयोग करके, क्योंकि, ओवरलैप परीक्षण निम्नानुसार किया जा सकता हैः और इसे योग और अंतर का उपयोग करके सरल बनाया जा सकता हैः जो ओवरलैप परीक्षण को कम करता हैः अंतराल जोड़ना ट्री में नए अंतराल जोड़ना एक द्विआधारी खोज ट्री के लिए मध्य मान को कुंजी के रूप में उपयोग करने के समान है। हम नोड से जुड़े द्विआधारी ढेर पर धक्का देते हैं, और सभी उच्च नोड्स से जुड़े न्यूनतम और अधिकतम संभव मूल्यों को अपडेट करते हैं। आइए क्वेरी अंतराल के लिए उपयोग करें, और एक नोड की कुंजी के लिए (अंतराल की तुलना में) रूट नोड से शुरू करते हुए, प्रत्येक नोड में, पहले हम जांच करते हैं कि क्या यह संभव है कि हमारा क्वेरी अंतराल नोड के न्यूनतम और अधिकतम मूल्यों का उपयोग करके नोड सबट्री के साथ ओवरलैप हो (यदि ऐसा नहीं है, तो हम इस नोड के लिए जारी नहीं रखते हैं)। फिर हम इस नोड के अंदर अंतराल की गणना करते हैं (इसके बच्चों के लिए नहीं) क्वेरी अंतराल के साथ ओवरलैप करने के लिए (जानना): और इसके द्विआधारी ढेर पर एक क्वेरी का प्रदर्शन करते हैं। सबसे खराब स्थिति में, हमें द्विआधारी खोज वृक्ष के सभी नोड्स को स्कैन करना पड़ता है, लेकिन चूंकि द्विआधारी हीप क्वेरी इष्टतम है, इसलिए यह स्वीकार्य है (एक 2-आयामी समस्या दोनों आयामों में इष्टतम नहीं हो सकती है) यह एल्गोरिथ्म खोज संचालन के लिए एक पारंपरिक अंतराल वृक्ष (संवर्धित वृक्ष) की तुलना में तेज होने की उम्मीद है। तत्वों को जोड़ना व्यवहार में थोड़ा धीमा है, हालांकि विकास का क्रम समान है। संदर्भ मार्क डी बर्ग, मार्क वैन क्रेवेल्ड, मार्क ओवरमार्स और ओटफ्राइड श्वार्जकोफ। कम्प्यूटेशनल ज्यामिति, दूसरा संशोधित संस्करण। स्प्रिंगर-वेरलैग 2000। खंड 10.1: अंतराल वृक्ष, पृ. 212-217। फ्रेंको पी. प्रिपेराटा और माइकल इयान शामोस। कम्प्यूटेशनल ज्यामितिः एक परिचय। स्प्रिंगर-वेरलैग, 1985 बाहरी लिंक सी. जी. ए. एल.: सी + + में कम्प्यूटेशनल ज्यामिति एल्गोरिदम लाइब्रेरी में रेंज ट्री Boost.Icl का एक मजबूत कार्यान्वयन शामिल है जो अंतराल सेट और मानचित्रों के सी + + कार्यान्वयन प्रदान करता है। इंटरवलट्री (पायथन)-ए. वी. एल. संतुलन के साथ एक केंद्रित अंतराल वृक्ष, टैग किए गए अंतराल इंटरवल ट्री (सी #) के साथ संगत-एक संवर्धित अंतराल वृक्ष, ए. वी. एल. संतुलन इंटरवल ट्री (रूबी) के साथ-एक केंद्रित अंतराल वृक्ष, अपरिवर्तनीय, टैग किए गए अंतराल इंटरवल ट्री (जावा) के साथ संगत-एक संवर्धित अंतराल वृक्ष, जिसमें ए. वी. एल. संतुलन, ओवरलैप का समर्थन, खोज, संग्रह इंटरफेस, आई. डी. से जुड़े अंतराल शामिल हैं। पेड़ों की खोज करें