একটি রেঞ্জ ট্রি হলো একটি অর্ডারড ট্রি ডেটা স্ট্রাকচার যা একটি লিস্ট অফ পয়েন্ট ধরে রাখে। এটি দক্ষতার সাথে একটি দেওয়া রেঞ্জের মধ্যে সকল পয়েন্ট রিট্রিভ করতে পারে, এবং সাধারণত দুই বা উচ্চতর ডাইমেনশনে বাস্তবায়িত হয়। এটি kd-ট্রির মতো কিন্তু ফাস্টার কোয়েরি টাইম O(logd n + k) কিন্তু ওয়ার্স স্টোরেজ O(n logd-1 n), যেখানে d ইঙ্গিত করে স্পেসের ডাইমেনশন, n ইঙ্গিত করে ট্রিতে পয়েন্টের সংখ্যা, এবং k ইঙ্গিত করে একটি দেওয়া কোয়েরির জন্য রিট্রিভড পয়েন্টের সংখ্যা। রেঞ্জ ট্রি ডিফারেনশিয়েট করা যেতে পারে ইন্টারভাল ট্রি থেকে: পয়েন্ট স্টোর করে এবং একটি দেওয়া রেঞ্জের পয়েন্ট দক্ষতার সাথে রিট্রিভ করার বদলে, একটি ইন্টারভাল ট্রি ইন্টারভাল স্টোর করে এবং একটি দেওয়া পয়েন্ট কন্টেইন করার ইন্টারভালগুলো দক্ষতার সাথে রিট্রিভ করতে দেয়।
ডেটা স্ট্রাকচার
একটি ১-ডাইমেনশনাল রেঞ্জ ট্রির উদাহরণ। লিফ ছাড়া প্রতিটি নোড তার লেফট সাবট্রির সর্বোচ্চ মান স্টোর করে।
এক সেট ১-ডাইমেনশনাল পয়েন্টের ওপর একটি রেঞ্জ ট্রি বিবেচিত হয় একটি ব্যালেন্সড বাইনারি সার্চ ট্রি সেসব পয়েন্টের ওপর। ট্রিতে স্টোর করা পয়েন্টগুলো ট্রির লিফে স্টোর করা থাকে; প্রতিটি ইন্টারন্যাল নোড তার লেফট সাবট্রিতে থাকা সর্বোচ্চ মান স্টোর করে। d-ডাইমেনশনে পয়েন্টের একটি সেটের ওপর একটি রেঞ্জ ট্রি হলো একটি রিকার্সিভলি ডিফাইনড মাল্টি-লেভেল বাইনারি সার্চ ট্রি। ডেটা স্ট্রাকচারের প্রতিটি লেভেল বিবেচিত হয় একটি বাইনারি সার্চ ট্রি d-ডাইমেনশনের একটিতে। ফার্স্ট লেভেল হলো ফার্স্ট d-কোঅর্ডিনেটের ওপর একটি বাইনারি সার্চ ট্রি। এই ট্রির প্রতিটি ভার্টেক্স v একটি অ্যাসোসিয়েটেড স্ট্রাকচার নিয়ে গঠিত যা একটি (d−১)-ডাইমেনশনাল রেঞ্জ ট্রি v-র সাবট্রিতে স্টোর করা পয়েন্টের লাস্ট (d−১)-কোঅর্ডিনেটের ওপর।
অপারেশন (Operations)
কনস্ট্রাকশন (Construction)
n পয়েন্টের একটি সেটের ওপর ১-ডাইমেনশনাল রেঞ্জ ট্রি হলো একটি বাইনারি সার্চ ট্রি, যা O(n log n) টাইমে বিল্ট করা যায়। উচ্চতর ডাইমেনশনের রেঞ্জ ট্রি রিকার্সিভলি বিল্ট করা হয় একটি ব্যালেন্সড বাইনারি সার্চ ট্রি কনস্ট্রাক্ট করে পয়েন্টের ফার্স্ট কোঅর্ডিনেটের ওপর, এবং তারপর, এই ট্রির প্রতিটি ভার্টেক্স v-র জন্য, একটি (d−১)-ডাইমেনশনাল রেঞ্জ ট্রি বিল্ড করা হয় v-র সাবট্রিতে কন্টেইনড পয়েন্টের ওপর। এইভাবে একটি রেঞ্জ ট্রি বিল্ড করলে O(n logdn) টাইম লাগবে।
