جلسه هشتم: جستجوی بازه‌ای

4-sided

Base tree درخت weight-balanced b-tree با درجه log_B N و تعداد عناصر برگ B روی مولفه x

ارتفاع: log_{log_B N} N

نقاط زیرمجموعه‌ی هر گره را در چهار ساختار ذخیره می‌کنیم: درخت اولویت راست، درخت اولویت چپ، B-tree on y، درخت بازه (priority search)

زمان: O(N/B log_B N / log_B log_B N)

داده‌ساختار ثانویه: (بعد دوم)

نقطه‌های هر slab را به ترتیب y به هم وصل کنید. آنها را روی محور y تصویر کنید.

بازه‌های به دست آمده را در درخت بازه نگه دارید بر حسب y. برای خود نقطه (مثلاً x) یک B-tree بسازید.

درخت kd:

(ادامه دارد.)