डेटा स्ट्रक्चर में रेंज ट्रीज़

रेंज ट्री (Range Tree) को बिंदुओं की सूची रखने के लिए एक क्रमबद्ध ट्री डेटा स्ट्रक्चर (Ordered Tree Data Structure) के रूप में परिभाषित किया जाता है। यह दिए गए रेंज के भीतर सभी बिंदुओं को कुशलतापूर्वक पुनः प्राप्त करने की अनुमति देता है, और आमतौर पर दो या अधिक आयामों में लागू किया जाता है। यह kd-ट्री के समान है सिवाय तेज़ क्वेरी समय (Faster Query Times) O(logᵈ n + k) के लेकिन बदतर स्टोरेज (Worse Storage) O(n logᵈ⁻¹ n) के साथ, जहां d स्पेस के आयाम (Dimension) को इंगित करता है, n ट्री में बिंदुओं की संख्या को इंगित करता है, और k दिए गए क्वेरी के लिए पुनः प्राप्त बिंदुओं की संख्या को इंगित करता है। रेंज ट्रीज़ को इंटरवल ट्रीज़ (Interval Trees) से अलग किया जा सकता है: बिंदुओं को स्टोर करने और दिए गए रेंज में बिंदुओं को कुशलतापूर्वक पुनः प्राप्त करने की अनुमति देने के बजाय, एक इंटरवल ट्री इंटरवल्स स्टोर करती है और दिए गए बिंदु को समाहित करने वाले इंटरवल्स को कुशलतापूर्वक पुनः प्राप्त करने की अनुमति देती है।

डेटा स्ट्रक्चर (Data Structure)

1-आयामी रेंज ट्री का एक उदाहरण। लीफ के अलावा प्रत्येक नोड अपने बाएं सबट्री में उच्चतम मान स्टोर करता है।

बिंदुओं के एक सेट पर 1-आयामी रेंज ट्री उन बिंदुओं पर एक संतुलित बाइनरी सर्च ट्री (Balanced Binary Search Tree) के रूप में माना जाता है। ट्री में स्टोर किए गए बिंदुओं को ट्री के लीफ्स (Leaves) में स्टोर किया जाता है; प्रत्येक आंतरिक नोड (Internal Node) अपने बाएं सबट्री में समाहित अधिकतम मान स्टोर करता है। d-आयामों में बिंदुओं के एक सेट पर एक रेंज ट्री एक पुनरावर्ती रूप से परिभाषित बहु-स्तरीय बाइनरी सर्च ट्री (Multi-level Binary Search Tree) है। डेटा स्ट्रक्चर का प्रत्येक स्तर d-आयामों में से एक पर बाइनरी सर्च ट्री के रूप में माना जाता है। पहला स्तर d-निर्देशांकों में से पहले पर एक बाइनरी सर्च ट्री है। इस ट्री के प्रत्येक वर्टेक्स v में एक संबद्ध संरचना होती है जो v के सबट्री में स्टोर किए गए बिंदुओं के अंतिम (d-1)-निर्देशांकों पर (d-1)-आयामी रेंज ट्री है।

ऑपरेशन्स (Operations)

निर्माण (Construction)

n बिंदुओं के सेट पर 1-आयामी रेंज ट्री एक बाइनरी सर्च ट्री है, जिसे O(n log n) समय में बनाया जा सकता है। उच्च आयामों में रेंज ट्रीज़ को पुनरावर्ती रूप से बिंदुओं के पहले निर्देशांक पर एक संतुलित बाइनरी सर्च ट्री बनाकर बनाया जाता है, और फिर इस ट्री में प्रत्येक वर्टेक्स v के लिए, v के सबट्री में समाहित बिंदुओं पर (d-1)-आयामी रेंज ट्री बनाकर। इस तरह रेंज ट्री बनाने में O(n logᵈ n) समय लगेगा।