پاورپوینت اثبات (pptx) 56 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 56 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
- بسیاری از انواع پرسش هایی که روی یک پایگاه داده پرسیده میشود قابل تفسیر به صورت هندسی است.
برای این منظور رکوردهای پایگاه داده را به نقاطی در فضای چند بعدی انتقال می دهیم و پرسش ها را روی این نقاط اجرا میکنیم.
در هر مسیری که به چپ حرکت میکنیم برگهای زیر درخت راست را گزارش میکنیم و در حرکت به سمت راست برگ های زیر درخت چپ را.
لم 5-1: الگوریتم دقیقا نقاطی را که در بازه قرار دارد گزارش میکند.
اثبات:
1- هر نقطه ای که گزارش شده در بازه بوده
2- هر نقطه ای که در بازه هست گزارش میشود.
Complexities: Query Time O( K + log n) T ,[x,x’] output Construction Time O(n log n) P T Space O(n) store T
فرض های اولیه: هیچ دو نقطه ای مختصات x,y یکسان ندارند
- یک فضای 2 بعدی را می‌توان ترکیبی از 2 تا فضای 1 بعدی در نظر گرفت.
ساختمان داده ی مناسب : bstمتوازن؟
با توجه به تعریف بازگشتی bst متوازن قابل تعمیم به فضای با بعد بالاتر هست.
تعریف بازگشتی: مجموعه ای از نقاط که به دو زیرمجموعه ی تقریبا مساوی تقسیم میشوند یک زیر مجموعه شامل نقاط کوچکتر یا مساوی با راس جداساز و دیگری شامل نقاط بزرگتر از راس جداساز