درخت بازه

دانشنامه عمومی

در علوم کامپیوتر، درخت بازه ای یک داده ساختار مرتب درختی برای نگهداری و ذخیره سازی بازه ها می باشد. می توان گفت این از درخت این امکان را فراهم می سازد تا همۀ بازه هایی را که با یک بازه یا نقطۀ خاص اشتراک دارند پیدا کنیم. درخت بازه ای به طور معمول برای پنجره دار کردن پرس و جوها به کار می رود. برای مثال، یافتن تمام راه های موجود بر روی یک نقشۀ کامپیوتری درون یک دید مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این داده ساختار، از درخت بخشی است. راه حل بدیهی این است که تمام بازه ها را ملاقات کرده و امتحان کنیم که آیا با نقطه یا بازه داده شده اشتراک دارند یا نه، که به theta ( n ) زمان نیاز دارد. ( که n همان تعداد بازه های موجود در مجموعه است ) از آنجایی که یک پرسش ممکن است تمام بازه ها را برگرداند، به طور مثال، اگر پرسش مورد نظر یک بازۀ بزرگ باشد که با همۀ بازه های موجود در مجموعه اشتراک داشته باشد، این به صورت مجانبی بهینه است؛ اگر که ما از الگوریتم های حساس به خروجی که در آن ها زمان اجرا بر اساس m ( که همان تعداد بازه های تولید شده توسط پرس و جوست ) بیان می شود استفاده کنیم می توانیم این فرایند را بهبود ببخشیم. درخت های بازه ای پویا هستند. آن ها اجازه درج و حذف بازه ها را می دهند. آن ها پرس و جو را در زمان O ( logn ) انجام می دهند. این در حالی است که زمان پیش پردازش برای ساخت این داده ساختار از O ( nlogn ) است ( ولی فضای مصرف شده از O ( n ) است ) . اگر انتهای بازه ها در محدودۀ کوچکی قرار داشته باشند ( مثلاً محدوده ) ، داده ساختارهای سریع تری با زمان پیش پردازش O ( n ) و زمان پرس و جوی O ( 1+m ) وجود دارند که m بازه ( شامل یک نقطه پرس و جو ) را گزارش می کنند.
در یک حالت ساده، بازه ها با هم هیچ گونه اشتراکی ندارند و می توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان O ( logn ) پرس و جو شوند. این در حالی است که با وجود اشتراک های دلخواه میان بازه ها، به هیچ عنوان امکان مقایسه دو بازه برای درج در درخت وجود ندارد. زیرا مرتب سازی ها بر حسب نقاط شروع یا پایان ممکن است متفاوت باشد. یک عملکرد ساده این خواهد بود که دو درخت موازی بسازیم. یکی مرتب شده بر حسب نقاط شروع و دیگری مرتب شده بر حسب نقاط انتهای هر بازه. این کار اجازۀ رها کردن نصف درخت را در O ( logn ) می دهد ولی نتیجه ها باید ادغام شوند که به O ( n ) زمان نیاز دارد. این راه حل به ما پرس و جوهایی در زمان O ( n ) = O ( n + logn ) می دهد که بهتر از راه حل بدیهی نیست.
عکس درخت بازهعکس درخت بازهعکس درخت بازهعکس درخت بازهعکس درخت بازهعکس درخت بازه
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس