درخت محدوده

درعلوم کامپیوتر، درخت محدوده یک ساختمان داده از نوع درخت مرتب است که لیستی از نقاط را نگه می‌دارد. این درخت تمامی نقاط داخل یک بازه را به‌صورت بهینه گزارش می‌دهد و معمولا در دو بعد یا بیشتر استفاده می‌شود. درختهای محدوده توسط جان لوئیس بنتلی در سال ۱۹۷۹ معرفی شدند. ساختمان داده‌های مشابه نیز به‌صورت مستقل توسط لوکر ، لی و وانگ و ویللرد معرفی شدند. درخت محدوده یک جایگزین برای درخت کی‌دی است. در مقایسه با درختهای کی‌دی، درختهای محدوده زمان جستجو سریعتری از مرتبه (O(log d n + k دارند ولی حافظه بیشتری از مرتبه (O(n log d−۱ n استفاده می‌کنند که n تعداد نقاط ذخیره شده در درخت، d بعد هر نقطه و k تعداد نقاط به دست آمده از جستجوی مورد نظر است.
تعریف
مثالی از یک درخت محدوده یک بعدی.
درخت محدوده روی مجموعهای از نقاط یک بعدی، یک درخت جستجوی دودویی متوازن روی آن نقاط است. نقاط در برگ‌های درخت ذخیره می‌شوند. هر گره داخلی، بیشترین مقدار ذخیره‌شده در زیر درخت چپ خود را نگه می‌دارد. یک درخت محدوده روی مجموعه‌ای از نقاط d بعدی، یک درخت جستجوی دودویی بازگشتی در چندین سطح است. هر سطح از این ساختمان داده یک درخت جستجوی دودویی روی یکی از d بعد است. اولین سطح درخت محدوده یک درخت جستجوی دودویی روی اولین مولفه است. هر راس v از این درخت، یک درخت محدوده (d-1) بعدی روی (d-1) مولفه آخر نقاط ذخیره‌شده در زیر درخت v است.
عملیات
ساختمان
درخت محدوده یک بعدی روی مجموعه‌ای از n نقطه، یک درخت جستجو دودویی است که می‌تواند در زمان (O(n log n ساخته شود. درختهای محدوده در ابعاد بالاتر را به صورت بازگشتی این گونه می‌سازیم: ابتدا یک درخت جستجوی دودویی متوازن روی مولفه اول نقاط می‌سازیم. سپس، برای هر راس v در این درخت، یک درخت محدوده (d-1) بعدی روی نقاط زیر درخت v می‌سازیم. ساختن درخت محدوده با این روش به زمان (O(n log d n نیاز دارد.
با توجه به اینکه یک درخت محدوده روی مجموعهای از نقاط دو بعدی می‌تواند در زمان (O(n log n ساخته شود، می‌توانیم روش فوق را ارتقا دهیم. فرض کنید S مجموعه‌ای n تایی از نقاط دو بعدی است. اگر S فقط یک نقطه داشته باشد، برگ شامل آن نقطه را بر گردانید. در غیر این صورت، ساختار مرتبط با S؛ یک درخت محدوده یک بعدی روی مختصات y نقاط S را بسازید. x m را میانه مولفه‌های x نقاط در نظر بگیرید. S L مجموعه نقاطی است که مختصات x شان کمتر یا مساوی x m و S R مجموعه نقاطی است که مختصات x شان بیشتر از x m است. به صورت بازگشتی v L ، یک درخت محدوده دو بعدی روی S L و v R ، یک درخت محدوده دو بعدی روی S R ، را بسازید. راس v را با فرزند چپ v L و فرزند راست v R بسازید. اگر در ابتدای الگوریتم این نقاط را برحسب مختصات y شان مرتب کنیم و این ترتیب هنگام جدا کردن نقاط برحسب x شان تغییر نکند، می‌توانیم ساختارهای مرتبط با هریک از درخت‌ها را در زمان خطی بسازیم. این راه، زمان ساخته‌شدن درخت محدوده دوبعدی را به (O(n logn کاهش می‌دهد، که همچنین زمان ساخت درخت محدوده d بعدی نیز به مرتبه (O(n log d−۱ n کاهش می‌یابد.
جستجوهای بازه‌ای
thumb
درختهای محدوده می‌توانند برای پیدا کردن مجموعه نقاط داخل یک بازه استفاده شوند. برای پیدا کردن نقاطی که در بازه هستند، با جستجو x ۱ و x ۲ شروع می‌کنیم. در یکی از راس‌های درخت، مسیر جستجوی x ۱ و x ۲ جدا می‌شوند. v split را آخرین راسی که در دو مسیر جستجو مشترک است در نظر می‌گیریم. به جستجوی x ۱ در درخت ادامه می‌دهیم. برای هر راس v در مسیر جستجو از v split تا x ۱ ، اگر مقدار ذخیره‌شده در v بیشتر از x ۱ باشد، همه نقاط زیر درخت راست v را اعلام می‌کنیم. اگر v یک برگ باشد، مقدار ذخیره‌شده در v را درصورتی‌که داخل بازه جستجو باشد اعلام می‌کنیم. به طور مشابه، در مسیر جستجو از v split تا x ۲ . تمامی نقاط ذخیره‌شده را در زیر درخت‌های چپ راس‌هایی که مقدارشان کمتر از x ۲ است و برگ این مسیر را درصورتی‌که مقدارش در بازه جستجو وجود داشت اعلام می‌کنیم.
از آنجایی که درخت محدوده، یک درخت جستجوی دودویی متوازن است، طول مسیر جستجو x ۱ و x ۲ از مرتبه (O(log n است. اعلام کردن تمامی نقاط ذخیره‌شده در زیر درخت یک راس، می‌تواند با استفاده از هر الگوریتم پیمایش درخت، در زمان خطی انجام شود. در نتیجه زمان اجرای یک جستجو بازهای از مرتبه (O(log n + k است که k، تعداد نقاط داخل بازه جستجو است.
بازه‌های جستجو در d بعد نیز مشابه هستند. بجای اعلام تمامی نقاط ذخیره‌شده در زیر درخت‌های مسیرهای جستجو، یک جستجو بازهای (d-1) بعدی روی ساختار مربوط به هر زیر درخت انجام می‌دهیم. سرانجام، جستجو بازهای یک بعدی انجام خواهد شد و نقاط درست اعلام خواهند شد. از آنجایی که یک جستجو d بعدی شامل (O(log n جستجو بازه‌ای (d-1) بعدی می‌شود، زمان لازم برای اجرای یک جستجو بازهای d بعدی از مرتبه (O(log d n + k است، که k تعداد نقاط در بازه جستجو است. این زمان می‌تواند با استفاده از روش fractional cascading به (O(log d−۱ n + k کاهش یابد.
درخت کی‌دی
درخت بازه‌ها