Payamvdn/NorthPersian_fa_wiki huggingface dataset:
س ما q را در هر یک از چهار لیست پیدا کردیم به وسیلهٔ جستجوی دوتایی در تک لیست M۱ همراه با یک مقایسه در هر لیست متواتر. به طور کلی تر برای هر ساختار داده از این نوع ما یک پرس و جو را به وسیلهٔ انجام یک جستجوی دودویی q در M۱ انجام می دهیم و با استفاده از مقدار نتیجه شده موقعیتq در L۱ را تعیین می کنیم. در مثال ما، لیست های آبشاره سازی جزءبه جزء شده، در مجموع ۲۵ عنصر دارند که مقداری کمتر از دو برابر ورودی اصلی است. به طور کلی سایز Mi در این داده ساختار حداکثر به این اندازه است: Lj| + ½| Li + ۱ | + ¼ | Li + ۲ | + … + ۱/ ۲j | Mi + j | +…. که به سادگی اثبات می شود سایز داده ساختار حد اکثر ۲n است: (Σ|Mi| = Σ|Li|(۱ + ½ + ¼ +…) ≤ ۲n = O(n مسئلهٔ کلی. به طور کلی، آبشاره سازی جزءبه جزء با گراف کاتالوگ آغاز می شود. گراف کاتالوگ گرافی جهت دار است که هر رأس آن با یک لیست مرتب شده برچسب گذاری شده است. هر پرس و جو در این داده ساختار، شامل یک مسیر از این گراف و یک مقدار q است و به ازای این دو، داده ساختار باید مشخص کند q در هر یک از لیست های مرتب شده ای که در رئوس مسیر داده شده قرار دارند، چندمین عنصر است. به عنوان یک مثال ساد
ه، گراف کاتالوگ مسیری است با چهار رأس. با استفاده از روش پویا (داینامیک)، امکان این وجود دارد که پاسخ رئوس بعدی یک مسیر را بر اساس نتایج جستجو در رئوس قبلی مسیر به دست آید. می خواهیم به پرسش هایی از این دست، در گرافی پاسخ دهیم. در این گراف به ازای مقدار ثابت d حداکثر تعداد یال های ورودی از هر رأس d و حد اقل تعداد یال های ورودی به هر رأس نیز d است. لیست های مربوط به هر رأس را، بر اساس همسایه های منتهی به یال های خروجی رأس، گسترش می دهیم. این کسر باید طوری انتخاب شود که کوچکتر از ۱/d باشد. به طوری که مقدار مجموع لیست های گسترش یافته نسبت به سایز ورودی خطی باشد. هر مورد، در هر لیست گسترش یافته، محل قرار گرفتن آن مورد را در لیست های گسترش نایافته ای که در همان رأس و در رأس های همسایهٔ منتهی به یال های خروجی، ذخیره شده اند، ذخیره می کند. به عنوان یک مثال ساده از این توضیحات، d=۱، و ما هر لیست را با ½ از همسایه هایش گسترش داده ایم: یک پرسش در این داده ساختار، شامل یک جستجوی دودویی عادی در لیست گسترش یافتهٔ مربوط به رأس اول از مسیر مورد پرس و جو، و علاوه بر آن، تعدادی جستجوی ساده تر، در هر یک از رئوس بعدی مسیر است.
اگرکسر ۱/r از همسایه های یک رأس در گسترش دادن لیست آن استفاده شود، در آن صورت نتیجهٔ هر پرسش بعدی حداکثر در r مرحله، از روی مکان هایی که در پرسش های قبلی، در رئوس قبلی مسیر ذخیره شده است، به دست خواهد آمد و حتی ممکن است در زمانی ثابت و کوتاه، بدون انجام یک جستجوی دودویی کامل یافته شود. آبشاره سازی جزءبه جزء پویا. در آبشاره سازی جزءبه جزء به صورت پویا، لیستی که در هر گره از گراف کاتالوگ ذخیره شده است، می تواند به صورت پویا تغییر کند. به عبارتی اجزای این لیست می توانند به روز شوند و یک عضو در آن درج شود یا از آن حذف گردد. ایجاد این تغییرات باعث به وجود آمدن مشکلاتی در ساختاربندی داده ها می شود. یکی از مشکلاتی که در این زمینه وجود دارد این است که هنگام اضافه شدن یک عضو به یک گره یا حذف شدن عضوی از آن، تغییراتی در لیست مربوط به آن گره ایجاد می شود. از طرفی تغییر در یک لیست منجر به وجود آمدن تغییرات در سایر لیست ها در سایر گره ها نیز می گردد. برای حل این مشکل، به جای استفاده از یک آرایهٔ مرتب شده برای هر گره، از یک درخت دودویی جستجو استفاده می شود. با این کار دو هدف برآورده خواهد شد. با استفاده از درخت دودویی جستج
و، امکان به روز رسانی سایر گره ها هنگام تغییر یک گره، با تعداد عملیاتی محدود فراهم می شود و همچنین توانایی جستجوی دودویی پابرجا باقی خواهد ماند. همان طور که پیش تر گفته شد، هر گره از گراف کاتالوگ، تعدادی از اعضای لیست همسایهٔ خود را نیز نگه داری می کند. به عبارتی در لیست یک گره، اعضایی که در مکان d از لیست همسایه قرار دارند نیز وجود دارد. در برخی شرایط با توجه به مقدار d و همچنین اعضای یک لیست، این امکان وجود دارد که با هر به روز رسانی و تغییر در یک لیست، لیست های همسایه نیز تغییر کنند. برای حل این مشکل از روشی شبیه به روش ساخت داده ساختار B tree استفاده می شود. با استفاده از این روش، می توان اطمینان حاصل کرد که تعداد داده هایی که انتخاب می شوند، کمتر از کل داده های لیست تقسیم بر d است و همچنین این اعداد در مکان های ثابتی از لیست قرار دارند. این موضوع باعث می شود که انتقال تغییرات هنگام درج یا حذف برای یک لیست از یک گره، تعداد عملیاتی کمتر از یک تقسیم بر d نیاز داشته باشد. یعنی یک تغییر در یک گره، به طور میانگین حداکثر یک تقسیم بر d تغییر برای به روز رسانی سایر گره ها نیاز دارد. با این روش، توزیع داده ها در م
یان گره ها به گونه ای خواهد بود که میانگین تعداد عملیاتی که برای به روز رسانی درخت های جستجوی دودویی صورت می گیرد، عددی ثابت است. مسئلهٔ اصلی در مبحث پویا کردن آبشاره سازی جزءبه جزء، نگه داری اندیس ها می باشد. همان طور که پیش تر گفته شد، هر عضو از لیست موجود در یک گره، دو اندیس را نگه می دارد. یکی اندیس مربوط به جستجوی خودش در همان لیست و یکی اندیس مربوط به جستجوی آن عضو در لیست همسایه. نگه داری این اندیس ها به صورت پویا هزینه بر است، چراکه با تغییر یک عضو، تعداد اندیس هایی که در تمام لیست ها باید تغییر کند، عدد بسیار بزرگی خواهد بود. برای همین، در این مدل، داده ساختارهای دیگری برای ذخیره شدن در هر گره، در نظر گرفته می شود که به شرح زیر می باشند: این داده ساختارها باعث می شوند که آبشاره سازی پویا در مرتبهٔ زمانی (O(log n برای هر درج و حذف عمل کند. همچنین یک زنجیره از k عمل جستجوی دودویی که در یک مسیر به طول k در گراف کاتالوگ صورت می گیرد، در مرتبهٔ زمانی (O(log n + k log log n انجام پذیرد. کاربردها. یکی از کاربردهایی که آبشاره سازی جزءبه جزء دارد، در داده ساختارهای جستجوی محدوده Range search که در هندسهٔ محاس
باتی مورد استفاده قرار می گیرد، می باشد. به طور مثال، در مسئلهٔ half-plane range reporting باید تعداد n نقطهٔ ثابت را تقسیم بندی کرد. یکی از ساختارهایی که در این زمینه مورد استفاده قرار می گیرد، لایه های محدب convex layers می باشد. آبشاره سازی جزءبه جزء به این مسئله کمک می کند تا عملیات جستجو برای شیب های مربوط به هر لایه در حافظهٔ مرتبهٔ (O(n و زمان (O(log n + h صورت گیرد که در آن h اندازهٔ زیرمجموعه هایی از نقاط است که مورد سؤال قرار می گیرد. با استفاده از الگوریتم Chazelle داده ساختاری که از مرتبهٔ زمانی (O(n log n ساخته می شود، این مسئله حل می شود. با توجه به این مثال، کاربرد آبشاره سازی جزءبه جزء شامل تعدادی جستجوی دودویی در یک سری خطی از لیست ها (سری های تودرتو از لایه های محدب) می باشد؛ بنابراین گراف کاتالوگ در این حالت، فقط یک مسیر ساده خواهد بود. یکی دیگر از کاربردهای آبشاره سازی جزءبه جزء در داده ساختارهای هندسی در رابطه با مکان یابی نقاط در نواحی یکنواخت monotone subdividions می باشد. ناحیهٔ یکنواخت، بخشی از صفحه شامل تعدادی چندضلعی است که هر خط هرکدام از چندضلعی ها را در حداکثر دو نقطه قطع کند. Ed
elsbrunne, Guibas و Stolfi در سال ۱۹۸۶ نشان دادند که برای حل این مسئله، کافیست دسته ای از مسیرهای به شکل چندضلعی را یافت که از چپ تا راست ناحیهٔ مورد نظر کشیده شده اند. سپس یک جستجوی دودویی بر روی این مسیرها باید زد تا مسیری را که در پایین ترین سطح قرار دارد و همچنین بالاتر از نقطهٔ مورد جستجو واقع شده است پیدا کرد. این موضوع که یک نقطه بالای یک مسیر قرار دارد یا پایین آن، با جستجوی دودویی قابل بررسی است. به عبارتی باید جستجویی بر روی مختصهٔ اول از هرکدام از نقاط مسیر داشت تا مقایسه کرد که نقطهٔ مورد بررسی زیر مسیر قرار دارد یا بالای آن؛ بنابراین برای جستجوهای دودویی که صورت می گیرد، می توان از آبشاره سازی جزءبه جزء استفاده کرد و سرعت را افزایش داد. با استفاده از این روش، مرتبهٔ زمانی انجام جستجو (O(log n خواهد بود و فضای (O(n از حافظه درگیر خواهد شد. در این حالت، گراف کاتالوگ یک گراف درخت خواهد بود که ترتیب های ممکن را برای جستجوی دودویی خارجی را می نمایاند. کاربرد آبشاره سازی جزءبه جزء تنها در محدودهٔ هندسهٔ محاسباتی نیست. Lakshamn و Stiliadis و همچنین Buddhikot, Suri و Waldvogel از این مدل برای طراحی داده
ساختارهایی در حوزهٔ فیلتر کردن بسته های ارتباطی در مسیریاب های Routers اینترنتی استفاده کرده اند. Gao et al نیز از آن به عنوان مدلی برای توزیع و بازیابی داده در حسگرهای شبکه ای استفاده کرده است.
مسئله پوشش بیشینه (به انگلیسی: maximum coverage problem)، یک سؤال کلاسیک در علوم رایانه و نظریه پیچیدگی محاسباتی است. این مسئله به طور گسترده در الگوریتم های تقریبی آموزش داده می شود. برای ورودی تعدادی مجموعه و یک عدد formula_1 داده می شود. مجموعه ها می توانند عضو مشترک داشته باشند. شما باید به تعداد حداکثر formula_1 تا از این مجموعه ها را انتخاب کنید به طوری که حداکثر تعداد اعضا پوشش داده شود؛ برای مثال اجتماع مجموعه های انتخاب شده، بیشینه تعداد اعضا را دارد. به عبارت دیگر، پوشش بیشینه (بدون وزن) نمونه: عدد formula_1 و مجموعه ای از مجموعه ها formula_4. هدف: یافتن یک زیرمجموعهٔ formula_5 ، به طوری که formula_6 و تعداد اعضای پوشانده شده formula_7 حداکثر باشد. مسئله پوشش بیشینه یک ان پی سخت (به انگلیسی: NP-hard) و نمی تواند تحت مفروضات استاندارد با formula_8 تقریب زده شود. این نتیجه در اصل با نسبت تقریبی الگوریتم حریصانه عمومی که برای بیشینه سازی توابع زیرپیمان های با محدودیت کاردینالیتی (به انگلیسی: maximization of submodular functions with a cardinality constraint) به کار می رود، مطابقت دارد. صورتبندی به شکل
برنامه خطی عدد صحیح. مسئله پوشش بیشینه می تواند به شکل زیر در قالب برنامه ریزی خطی عدد صحیح (به انگلیسی: Integer Linear Program) فرمول بندی شود. الگوریتم حریصانه. الگوریتم حریصانه برای پوشش بیشینه، مجموعه ها را بر اساس یک قاعده انتخاب می کند: در هر مرحله، مجموعه ای را انتخاب کن که شامل بیشترین تعداد اعضای پوشش داده نشده باشد. می توان نشان داد که این الگوریتم به نسبت تقریب formula_20 می رسد. نتایج نشان می دهد که الگوریتم حریصانه، بهترین الگوریتم تقریب زمانی چند جمله ای ممکن برای پوشش بیشینه است. تعمیم های شناخته شده. نتایج غیرتقریبی به همهٔ تعمیم های مسئله پوشش بیشینه اعمال می شود زیرا آنها مسئله پوشش بیشینه را به عنوان یک حالت خاص دارند. حالت وزن دار. در مدل وزن دار هر عضو formula_21 وزنی برابر formula_22 دارد. هدف یافتن یک پوشش بیشینه است به طوری که بیشترین وزن را داشته باشد. حالت پایه، حالت خاصی است که همه وزن ها برابر formula_23 است. الگوریتم حریصانه برای پوشش بیشینه وزندار در هر مرحله مجموعه ای را انتخاب می کند که دارای بیشترین وزن اعضای پوشش داده نشده باشد. این الگوریتم به نسبت تقریب formula_20 می رسد. پ
وشش بیشینه بودجه ای. در حالت پوشش بیشینه بودجه ای (به انگلیسی: Budgeted maximum coverage)، نه تنها هر عضو formula_21 وزنی برابر formula_22 دارد، بلکه هر مجموعه formula_19 قیمتی برابر formula_40 دارد. به جای formula_1 که تعداد مجموعه ها در پوشش را محدود می کند، بودجهٔ formula_42 داده می شود. بودجهی formula_42 وزن پوششی که می تواند انتخاب شود را محدود می کند. الگوریتم حریصانه دیگر راه حل هایی با تضمین کارایی ارائه نخواهد کرد. یعنی ممکن است رفتار این الگوریتم در بدترین حالت با راه حل بهینه بسیار متفاوت باشد. الگوریتم تقریب به روش زیر بدست می آید. ابتدا، پس از یافتن راه حلی که از الگوریتم حریصانه استفاده می کند، راه حل بهتر الگوریتم حریصانه و مجموعه با بیشترین وزن را بازمی گردانیم. این روش را، الگوریتم حریصانه اصلاح شده می نامیم. در مرحله دوم، با شروع از همهٔ خانواده های ممکن مجموعه های اندازه ها از یک تا (حداقل) سه، این راه حل ها را با الگوریتم حریصانه اصلاح شده تقویت می کنیم. در مرحله سوم، بهترین راه حل تقویت شده را بازمی گردانیم. این الگوریتم به نسبت تقریب formula_55 می رسد. این بهترین نسبت تقریب ممکن است مگر
formula_56. پوشش بیشینه تعمیم یافته. در تعمیم یافتهٔ پوشش بیشینه هر مجموعهٔ formula_19 قیمت formula_40 دارد، عضو formula_21 دارای وزنی متفاوت و هزینه ای بسته به مجموعه ای که آن را پوشش می دهد، دارد. یعنی اگر formula_21 توسط مجموعهٔ formula_19 پوشش داده شده باشد، وزن formula_21 برابر formula_63 و هزینهٔ آن برابر formula_64 خواهد بود. بودجه formula_65 برای هزینهٔ کل راه حل داده شده است. الگوریتم پوشش بیشینه تعمیم یافته. این الگوریتم از مفهوم باقیماندهٔ وزن/هزینه استفاده می کند. باقیماندهٔ وزن/هزینه در مقابل یک راه حل آزمایشی اندازه گیری می شود و این تفاوت بین وزن/هزینه و وزن/هزینه بدست آمده با یک راه حل آزمایشی است. این الگوریتم چندین مرحله دارد. اول، یافتن راه حلی که از الگوریتم حریصانه استفاده می کند. در هر تکرار الگوریتم حریصانه، راه حل آزمایشی مجموعه ای را که شامل بیشترین مقدار وزن اعضای باقیمانده تقسیم بر هزینهٔ این اعضا همراه با هزینه اعضای باقیمانده دارد، اضافه می کند. دوم، مقایسهٔ راه حل بدست آمده در قدم اول با راه حل بهینه که از تعداد کمی از مجموعه ها استفاده می کند. سوم، بازگرداندن بهترین راه حل از بی
ن راه حل های بررسی شده. این الگوریتم به نسبت تقریب formula_81 می رسد.
الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان formula_1 و حافظه formula_2 است. این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقاله "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد. توضیح الگوریتم. این الگوریتم هم از خط جارویی و هم از "خط ساحلی" استفاده می کند که هردوی این خطوط در حین پیشرفت الگوریتم روی صفحه حرکت می کنند. خط جارویی خط مستقیمی است که ما به صورت توافقی می توانیم فرض کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت می کند. در هر لحظه در طی الگوریتم نقاط ورودی سمت چپ خط جارویی با نمودار ورونی یکپارچه خواهند شد درحالی که نقاط سمت راست خط هنوز در نظر گرفته نشده اند. خط ساحلی یک خط نیست، بلکه یک منحنی مرکب در سمت چپ خط جارویی است که از تکه های سهمیها تشکیل شده است؛ این خط صفحه را به گونه ای تقسیم می کند که در آن نمودار ورونی، بدون توجه به وجود نقاط ممکن در سمت راست خط جارویی، از بقیه صفحه قابل تشخیص است. برای هر نقطه در سمت چپ خط جارویی، میتوان یک سهمی از نقاط هم فاصله از آن نقطه و خط جارویی تعریف کرد. خط ساحلی مرز مجموعه این
سهمی ها است. هر چه خط جارویی پیشروی می کند رئوس خط ساحلی، که محل تلاقی دو سهمی است، یال های نمودار ورونی را رسم می کنند. خط ساحلی طوری پیشرفت می کند که رأس هر سهمی دقیقأ در وسط نقاط اولیه خط جارویی و جایگاه جدید خط جارویی قرار بگیرد. این الگوریتم از داده ساختارها استفاده می کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می کند و یک صف اولویت دار که رخدادهای بالقوه بعدی را که می توانند ساختار خط ساحلی را تغییر دهند لیست می کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطه ورودی دیگری عبور می کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایره عبورکننده از سه نقطه، که سهمی هایشان بخش های متوالی خط ساحلی را تشکیل می دهند، مماس می شود). هر رخداد می تواند توسط محور xهای خط جارویی در محل وقوع رخداد، اولویت بندی شود. الگوریتم از برداشتن مکرر رخداد بعدی از صف اولویت دار، یافتن تغییراتی که آن رخداد در خط ساحلی ایجاد می کند و بهنگام سازی داده ساختارها، تشکیل می شود. از آنجا که formula_2 رخداد وجود دارند تا پردازش شوند (که هرکدام با برخی ویژگی های دیاگر
ام ورونی مرتبط هستند) و زمان formula_4 برای پردازش یک رخداد (که هرکدام شامل تعداد ثابتی از اعمال درخت جستجوی دودویی و صف اولویت دار هستند) زمان کلی الگوریتم formula_1 است. شبه کد. شبه کد توضیحات الگوریتم. let formula_6 be the transformation formula_7, where formula_8 is the Euclidean distance between formula_9 and the nearest site let formula_10 be the "beach line" let formula_11 be the region covered by site formula_12. let formula_13 be the boundary ray between sites formula_12 and formula_15. let formula_16 be the sites with minimal formula_17-coordinate, ordered by formula_18-coordinate formula_19 create initial vertical boundary rays formula_20 formula_21 while not IsEmpty(formula_22) do formula_12 ← DeleteMin(formula_22) case formula_12 of formula_12 is a site in formula_27: find the occurrence of a region formula_28 in formula_10 containing formula_12, bracketed by formula_31 on the left and formula_32 on the right create new boundary rays formula_33 and formula_34 with bases formula_12 replace formula
_28 with formula_37 in formula_10 delete from formula_22 any intersection between formula_31 and formula_32 insert into formula_22 any intersection between formula_31 and formula_33 insert into formula_22 any intersection between formula_34 and formula_32 formula_12 is a Voronoi vertex in formula_27: let formula_12 be the intersection of formula_51 on the left and formula_52 on the right let formula_53 be the left neighbor of formula_51 and let formula_55 be the right neighbor of formula_52 in formula_10 create a new boundary ray formula_58 if formula_59, or create formula_60 if formula_12 is right of the higher of formula_15 and formula_63, otherwise create formula_64 replace formula_65 with newly created formula_32 in formula_10 delete from formula_22 any intersection between formula_53 and formula_51 delete from formula_22 any intersection between formula_52 and formula_55 insert into formula_22 any intersection between formula_53 and formula_32 insert into formula_22 any intersection between formula_32 an
d formula_55 record formula_12 as the summit of formula_51 and formula_52 and the base of formula_32 output the boundary segments formula_51 and formula_52 endcase endwhile output the remaining boundary rays in formula_10 بخش ها و دیسک های وزن دار. همان طور که فورچون در توضیح داده است، یک نوع الگوریتم توسعه یافته خط جارویی می تواند برای ساخت نمودار ورونی وزن دارافزایشی استفاده شود، که در آن فاصله هر بخش با وزن آن تعیین می شود؛ که این می تواند برابر با نمودار ورونی مجموعه ای از دیسک های هم مرکز بخش ها و به شعاع وزن آن ها باشد. زمانی که از نمودار ورونی برای ساخت treemapها استفاده می شود، می توان از بخش های وزن دار برای کنترل مکان های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن دار افزایشی، نیم ساز بین بخش ها به طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن دار و نمودار پاور دیسک ها نیم ساز یک خط مستقیم است.
در علوم کامپیوتر، درخت بازه ای یک داده ساختار مرتب درختی برای نگهداری و ذخیره سازی بازه ها می باشد. می توان گفت این از درخت این امکان را فراهم می سازد تا همه بازه هایی را که با یک بازه یا نقطه خاص اشتراک دارند پیدا کنیم. درخت بازه ای به طور معمول برای پنجره دار کردن پرس و جوها به کار می رود. برای مثال، یافتن تمام راه های موجود بر روی یک نقشه کامپیوتری درون یک دید مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این داده ساختار، از درخت بخشی است. راه حل بدیهی این است که تمام بازه ها را ملاقات کرده و امتحان کنیم که آیا با نقطه یا بازه داده شده اشتراک دارند یا نه، که به theta(n) زمان نیاز دارد. (که n همان تعداد بازه های موجود در مجموعه است) از آنجایی که یک پرسش ممکن است تمام بازه ها را برگرداند، به طور مثال، اگر پرسش مورد نظر یک بازه بزرگ باشد که با همه بازه های موجود در مجموعه اشتراک داشته باشد، این به صورت مجانبی بهینه است؛ اگر که ما از الگوریتم های حساس به خروجی که در آن ها زمان اجرا بر اساس m (که همان تعداد بازه های تولید شده توسط پرس و جوست) بیان می شود استفاده کنیم می تو
انیم این فرایند را بهبود ببخشیم. درخت های بازه ای پویا هستند. آن ها اجازه درج و حذف بازه ها را می دهند. آن ها پرس و جو را در زمان O(logn) انجام می دهند. این در حالی است که زمان پیش پردازش برای ساخت این داده ساختار از O(nlogn) است (ولی فضای مصرف شده از O(n) است). اگر انتهای بازه ها در محدوده کوچکی قرار داشته باشند (مثلاً محدوده [1...,O(n)])، داده ساختارهای سریع تری با زمان پیش پردازش O(n) و زمان پرس و جوی O(1+m) وجود دارند که m بازه (شامل یک نقطه پرس و جو) را گزارش می کنند. عملکرد ساده. در یک حالت ساده، بازه ها با هم هیچ گونه اشتراکی ندارند و می توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان O(logn) پرس و جو شوند. این در حالی است که با وجود اشتراک های دلخواه میان بازه ها، به هیچ عنوان امکان مقایسه دو بازه برای درج در درخت وجود ندارد. زیرا مرتب سازی ها بر حسب نقاط شروع یا پایان ممکن است متفاوت باشد. یک عملکرد ساده این خواهد بود که دو درخت موازی بسازیم. یکی مرتب شده بر حسب نقاط شروع و دیگری مرتب شده بر حسب نقاط انتهای هر بازه. این کار اجازه رها کردن نصف درخت را در O(logn) می دهد ولی نتیجه ها باید ادغام ش
وند که به O(n) زمان نیاز دارد. این راه حل به ما پرس و جوهایی در زمان O(n) = O(n + logn) می دهد که بهتر از راه حل بدیهی نیست. درخت بازه ای مرکزی. پرس و جوها به زمان o(m + log(n)) نیاز دارند که در آن n تعداد کل بازه ها و m تعداد نتایج گزارش شده است. ساخت داده ساختار نیز به o(nlogn) زمان و O(n) فضا نیاز دارد. ساختار. به ما یک مجموعه n تایی از بازه ها در خط اعداد داده می شود و ما می خواهیم یک داده ساختار بسازیم که بتواند به صورت مؤثری همه بازه هایی را که با یک نقطه یا بازه اشتراک دارند بازیابی کند. ما با مشخص کردن محدوده کل بازه ها و تقسیم کردن آن در x_center (در عمل، x_center باید مشخص شود تا درخت را نسبتاً متعادل نگه داریم) شروع می کنیم. این فرایند سه مجموعه از بازه ها را تولید می کند: 1. بازه هایی که کاملاً در سمت چپ x_center قرار می گیرند که ما آن ها را S_left نام گذاری می کنیم. 2. بازه هایی که کاملاً در سمت راست x_center قرار می گیرند که ما آن ها را S_right نام گذاری می کنیم. 3. آنهایی که با x_center اشتراک دارند که ما آن ها را S_center می نامیم. بازه های S_left و S_rightنیز به طریق مشابه به صورت بازگشتی تقس
یم می شوند تا زمانی که هیچ بازه ای باقی نماند. بازه هایی از S_center که با نقطه مرکزی تلاقی دارند در یک داده ساختار جداگانه مرتب می شوند که به گره های درخت بازه ای پیوند داده شده است. این داده ساختار از دو لیست تشکیل شده است: یکی شامل همه بازه هایی که بر حسب نقاط شروع شان مرتب شده اند و دیگری شامل همه بازه هایی که برحسب نقاط پایانشان مرتب شده اند. نتیجه، یک درخت ثالث است که هر گره شامل موارد زیر است: 1. یک نقطه مرکزی 2. یک اشاره گر به یک گره دیگر شامل همه بازه هایی که به طور کامل در سمت چپ نقطه مرکزی قرار می گیرند. 3. یک اشاره گر به یک گره دیگر شامل همه بازه هایی که به طور کامل در سمت راست نقطه مرکزی قرار می گیرند. 4. همه بازه های شامل نقطه مرکزی که بر اساس نقطه شروع شان مرتب شده اند. 5. همه بازه های شامل نقطه مرکزی که بر اساس نقطه پایان شان مرتب شده اند. اشتراکی. به ما داده ساختار ساخته شده در بالا داده می شود. ما پرس و جوهایی را شامل بازه ها یا نقاط داده شده دریافت می کنیم و تمام بازه های موجود در بازه های اصلی و تمام بازه های موجود در مجموعه اصلی را که با این ورودی اشتراک دارند برمی گردانیم. با یک بازه. او
ل می توانیم حالتی را که یک بازه R به عنوان ورودی داده می شود به حالت ساده تر که در آن یک نقطه به عنوان ورودی داده شده است کاهش دهیم. در ابتدا همه بازه هایی را که نقطه شروع یا پایان شان در درون بازه ورودی R قرار دارد، با استفاده از یک درخت جداگانه می یابیم. در حالت یک بعدی می توانیم از یک درخت ساده شامل همه نقاط شروع و پایان در مجموعه بازه ها استفاده کنیم که هرکدام شامل یک نشانه گر به بازه مربوط به آن است. یک جستجوی دودویی در زمان O(logn) برای شروع و پایان R، کمینه و بیشینه نقاطی را که باید در نظر گرفته شوند مشخص می کند. هر نقطه با این محدوده به تمام بازه هایی که با محدوده مورد نظر ما تلاقی دارند ارجاع می دهد و به لیست نتیجه اضافه می شود. باید توجه شود که از ایجاد تکرار جلوگیری شود، زیرا ممکن است هم شروع و هم پایان یک بازه با R باشد. این کار را می توان با استفاده از یک پرچم دودویی بر روی هر بازه برای مشخص کردن اینکه این بازه به مجموعه نتیجه اضافه شده است یا نه، انجام داد. تنها بازه هایی که هنوز در نظر گرفته نشده اند بازه هایی هستند که با R تلاقی دارند ولی نقاط پایان شان درون R نیست، به عبارت دیگر، بازه هایی که
آن را در بر می گیرند. برای پیدا کردن آن ها ما هر نقطه در درون را در نظر می گیریم و از الگوریتم زیر استفاده می کنیم تا همه بازه هایی را که با آن نقطه اشتراک دارند بیابیم. (دوباره مواظب باشید که تکرارها را حذف کنید) با یک نقطه. این فرایند در واقع یافتن همه بازه های موجود در درخت است که با یک نقطه x داده شده اشتراک دارند. درخت به همان شیوه پیمایش یک درخت مرسوم دودویی پیمایش می شود، ولی با کارآیی بیشتر برای بازه هایی که با نقطه مرکزی در هر گره تلاقی دارند. برای هر گره درخت، x با x_center مقایسه می شود، یعنی همان نقطه میانی که برای ساخت گره در بالا استفاده شده است. اگر x از x_center کوچک تر باشد، چپ ترین مجموعه از بازه ها S_left در نظر گرفته می شود. اگر x از x_center بزرگ تر باشد، راست ترین مجموعه از بازه ها S_right در نظر گرفته می شود. همین طور که هر گره پردازش می شود، وقتی ما درخت را از ریشه به یک برگ می پیماییم، محدوده های موجود در S_center آن پردازش می شوند. اگر x از x_center کوچک تر باشد، ما می دانیم که تمام بازه های موجود s_center بعد x تمام می شوند یا اینکه اصلاً با x_center برخورد ندارند. بنابراین ما تنها
به یافتن بازه هایی از s_centerنیاز داریم که قبل از x شروع می شود. ما توانیم در مورد لیست های s_center که تاکنون ساخته شده اند بحث کنیم. از آنجایی که ما در این سناریو تنها به شروع بازه ها اهمیت می دهیم، می توانیم در مورد لیست مرتب شده بر اساس شروع بازه ها بحث کنیم. فرض کنید ما در لیست نزدیک ترین عددی که بزرگ تر از x نیست را بیابیم. تمام محدوده ها از شروع لیست تا آن نقطه یافته شده با x تلاقی دارند، چون قبل از x شروع شده و بعد از x تمام می شوند. (همان طور که می دانیم به علت این است که با x_center که بزرگ تر از x است تلاقی دارند) بنابراین می توانیم شروع به شماره گذاری بازه های موجود در لیست کنیم تا زمانی که مقدار نقطه پایانی از x بیشتر شود. همچنین اگر x از x_center بزرگ تر باشد، ما می دانیم که همه بازه های موجود در s_center باید قبل از x شروع شوند پس ما بازه هایی را که بعد از x پایان می یابند به وسیله لیستی که بر اساس پایان بازه ها مرتب شده است می یابیم. اگر x دقیقاً منطبق بر x_center باشد، تمام فواصل را می توان بدون پردازش بیشتر به نتایج اضافه کرد و پیمایش درخت می تواند متوقف شود. ابعاد بالاتر. ساختمان داده درخ