درخت سگمنت
می خواهیم پاره خط هایی که با یک مستطیل ورودی تقاطع دارند را پیدا کنیم.
- اول فرض کنید خط ها موازی محورها باشند:
اگر تصویر این خطها را روی محورها در نظر بگیریم، به سادگی می توانیم تشخیص بدهیم با تصویر مستطیل روی محورها تقاطع دارد یا نه.
- اگر پاره خط ها در هر راستای دلخواهی باشند: (نه الزاما موازی محورها: افقی و عمودی)
روش لوکاس:
به ناحیه هایی تقسیم کنیم که جواب در آنها یکی است.
یک بعدی:
ناحیه های سر پاره خط ها و ناحیه های شامل پاره خط های یکسان.
به جای اینکه درخت را روی نقطه های دو سر پاره خط ها بسازیم، روی این بازه ها می سازیم. خود بازه ها در برگ ها نگه داری می شوند و گره های میانی اجتماع بازه های فرزندانشان هستند.
کوئری: پیدا کردن پاره خط هایی که شامل یک x خاص هستند.
در هر گره ی میانی، لیست پاره خط هایی نگهداری می شود که گره ی پدر این گره دیگر شامل آنها نمی شود. یعنی هر پاره خط در بالاترین جای درخت (نزدیک تر به ریشه) نگه داری می شود که کامل شامل آن است.
نحوه ی کوئری زدن:
از ریشه درخت به سمت برگی که شامل نقطه ی کوئری است حرکت کن و همه ی لیست های پاره خط های گره های میانی را به عنوان جواب برگردان!
زمان کوئری: O(logn+k)
تحلیل فضا:
برگ ها: هر پاره خط حداکثر دو سر دارد، پس بازه های ساخته شده O(n) می شود.
گره های میانی: هر پاره خط حداکثر در لیست دو گره وجود دارد. (اثبات: برهان خلف: اگر سه گره باشند، شرط بودن در بالاترین گره به هم می خورد؛ چون بالاترین گره ای که شامل پاره خط است (پدر سه گره) و گره ای که فرزند آن است و همان پاره خط را دارد (پدر دو گره از گره های مساله))
کلا: O(nlogn)
نکته: ساختار درخت شبیه درخت بازه ی دوبعدی است! (در حالت یک بعدی)
امیر محمد دهقان