تمرین های کتاب - فصل جستجوی بازه ها (درخت های هندسی)

جواب:

الگوریتم:

1- تصویر بازه ها روی محور x را حساب می کنیم و یک درخت بازه روی آن می سازیم. (interval tree)

2- در هر نود درخت بازه ی ساخته شده، یک درخت محدوده (range tree) روی تصویر پاره خطها روی محور y (یک نقطه به ازای هر پاره خط) می سازیم.

3- کوئری را اول روی درخت بازه جواب می دهیم بعد روی درخت محدوده ی آن.

اثبات درستی:

در قدم اول [x,x'] را پیدا می کنیم و در قدم دوم بازه ی y را هم چک می کنیم.

زمان، پیش پردازش، کوئری:

برای درخت بازه ها: تعداد پاره خط ها = تعداد پاره خط های ورودی = n

برای درخت محدوده: تعداد نقاط = تعداد پاره خط های ورودی = n