فهرست

فايل با ساختار جستجوي دودويي
فايل با ساختار درخت جستجوي دودويي نخ كشي شده
فايل با ساختار درخت صفحه بندي شده
فايل با ساختار درخت متعادل
فايل درختي
فايل با ساختار درختB+
فايل با ساختار درختk-d
فايل با ساختار توالي

بسمه تعالي
امتحان ميان ترم درس آمار و احتمال۲
دانشگاه پيام نور رضوانشهر
سؤال ۱) فرض كنيدX1, X2,…,Xn متغيرهاي تصادفي مستقل و هم توزيع از يك توزيع يكنواخت وY1,Y2,…,Yn آماره هاي ترتيبي مربوط به اين نمونهn تايي باشند در اين صورت توزيع توام را به دست آوريد. (۲نمره)
سؤال۲) طول عمر قطعات توليدي يك كارخانه داراي ميانگين ۵ با واريانس۱مي باشد. اين كارخانه محصولات خود را در بسته هاي ۳۶ تايي به مشتريان خود عرضه مي كند. يكي از مشتريان كارخانه محصولات را در صورتي قبول مي كند كه حداقل ۲۵ درصد از بسته هاي ارسالي ميانگين طول عمري بيشتر از۲۱/۵ داشته باشند. احتمال آن را به دست آوريد كه يك محموله ۱۲ تايي ارسال شده براي اين مشتري پذيرفته شود. (۲ نمره)
سؤال۳) اگرY,X متغيرهاي تصادفي با تابع چگالي توام زير باشند، توزيعZ=X-Y را به دست آوريد. (۲ نمره)

استفاده از جدول آماري آزاد است
سربلند و پيروز باشيد.

ساختارهاي درختي
فايل با ساختار درخت جستجوي دودويي
در فايل با ساختار ترتيبي لازمه استفاده از الگوريتم جستجوي دودويي اين است كه بلاك هاي داده اي به طور پيوسته ذخيره شده اند اگر بلاك ها به طور ناپيوسته ذخيره و به هم پيوند شده باشند يافتن آدرس بلاك مياني ناممكن است.
فايل با ساختار درخت جستجوي دودويي باn ركورد و كليد اصليi=1,2,…,n,ki گونه‌اي از درخت دودويي است كه دو خاصيت زير را دارد.
۱- هر گره درخت، بسته به طرز پياده سازي، حداقل سه يا چهار فيلد در هر دو حالت دو تا از فيلدها حاوي نشانه رو به گره هاي سمت چپ و سمت راست هستندRPTR, LPTR در حالت وجود سه فيلد، فيلد سوم حاوي خود ركورد است. در غير اين صورت در فيلد سوم كليد ركورد قرار دارد و فيلد چهارم حاوي نشانه روي به بلاك داده اي حاوي ركورد است.

۲- اگرki كليد يك ركورد باشد كليد تمام ركوردهاي موجود در گره هاي زيردرخت سمت چپ ازki كوچكتر و كليد تمام ركوردهاي موجود در گره هاي زير درخت سمت راست، از ki بزرگترند،
عمليات در فايل
واكنش ركورد
الگوريتم واكنشي خيلي ساده است سيستم ابتدا به گره ريشه دستيابي پيدا مي كند عمل مقايسه بين كليد ركورد مورد نظر و كليد ركورد موجود در گره ريشه انجام مي شود، اگر تساوي برقرار باشد، ركورد پيدا شده است وگرنه، يكي از دو گره سمت راست يا سمت چپ گره ريشه مورد دستيابي قرار مي گيرد و عمل مقايسه انجام مي شود، اين عمليات تا پايان يافتن ركورد مورد نظر يا برخورد به نشانه روي تهي تكرار مي شود اگر ركورد مورد نظر در سطحk باشد در حافظه اصلي ذخيره شود براي واكنش ركوردk+1 بار دستيابي مستقيم لازم است.
كارايي اين ساختار در واكنشيس ركورد وقتي حداكثر است كه ژرفاي حداقل باشد و زماني حداقل است كه ژرفاي درخت حداكثر باشد.
ژرفاي درخت زماني حداكثر است كه در هر سطح تنها يك گره وجود داشته باشد در اين حالت ژرفاي درختN است و متوسط دستيابي (ANA) مستقيم براي واكنشي ركورد برابر است با:

از طرف ديگر ژرفاي درخت زماني در حداقل است كه در هر سطح مثلاً سطحk ام، غير از سطح ريشه دقيقاًk2 گروه وجود داشته باشد. اگر ژرفاي درخت راx فرض كنيم با فرض پربودن تمام درخت داريم:
n=2x-1
و متوسط زمان دستيابي لازم براي واكنشي ركورد برابر است با:

مي توان نشان داد كه عبارت بالا برابر است با:

عمل درج
اگر درخت خالي باشد، ركورد درج شدني به آساني درج مي شود. اگر درخت خالي نباشد و كليد ركورد كوچكتر ازكليد ركورد و ريشه باشد، ركورد در سمت چپ ريشه درجه مي شود و اگر كليد ركورد از كليد ريشه بزرگتر باشد ركورد در سمت راست ريشه درج مي شود. اين مقايسه كليدها در هر سطح ديگر هم تكرار مي شود تا نقطه منطقي درج ركورد پيدا شود و عمل جايابي زماني متوقف مي شود كه با نشانه روي تهي برخورد شود. بدين ترتيب با درج هر ركورد جديد، يك گره در انتهاي يكي از مسيرها ايجاد مي شود.
عمليات لازم براي درج ركورد چنين است:
يافتن نقطه منطقي درج
خواندن بلاكي كه ركورد بايد در آن درج شود (يك بلاك از فضاي آزاد)
بازنويسي همين بلاك
بنابراين داريم:
T1=TF+r+s+btt+TRW

حذف ركورد
با حذف ركورد، بايد وضعيت ساختاري يك فايل به گونه اي تنظيم شود كه ماهيت آن محفوظ بماند، يعني كماكان يك درخت در جستجوي دودويي باشد. در هر حال گره مربوطه بايد حذف شود سه حالت متصور است:
حالت اول: تعداد گره هاي فرزند گره حذف شدني صفر باشد (گره فرزند نداشته باشد) در اين حالت گره را مي توان حذف كرد و درخت كماكان ماهيت خود را حفظ مي كند.
حالت دوم: گره حذف شدني فقط يك گره فرزند داشته باشد.
در اين حالت درخت فقط در صورتي ماهيت خود را حفظ مي كند كه فرزند گره حذف شده، جايگزين آن بشود براي اين منظور، فيلد نشانه رو در گره پدر گره حذف شده بايد متناسباً تنظيم شود.

حالت سوم: گره حذف شدني دو فرزند داشته باشد. در اين الت، پس از حذف گره مربوطه، ركورد بعد آن، طبق نظم، بايد جايگزين آن شود. ركورد بعدي طبق نظم، ركورد سمت چپ در زير درخت سمت راست گره حذف شدني است. بدين ترتيب، ديگر نيازي به جستجو در درخت، طبق نظم، براي يافتن ركورد بعدي نيست و به علاوه با حذف ركورد بعدي موضع درخت چنان مي شود كه يكي از دو حالت اول يا دوم پيش مي آيد.
خواندن تمام فايل
خواندن سريال ركوردها عملاً بسيار زمانگير است، اولين ركوردي كه بايد خوانده شود، ركورد موجود در گره انتهايي سمت چپ ترين شاخه درخت است و بديهي است كه براي خواندن آن ركوردهاي پيشين آن بايد مورد دستيابي قرار گيرند و به علاوه آدرس اين ركوردها نيز بايد نگهداري شود تا بتوان آنها را به طور سريال خواند. بنابراين عمليات خواندن سريال علاوه بر زمانگير بودن به حافظه نسبتاً زيادي نيز نياز دارد.

براي خواندن پي در پي ركوردها مي توان فايل را از ابتدا تا انتها خواند اما با اين روش ركوردهاي پيشتر حذف شده نيز خوانده مي شود. روش بهتري وجود دارد كه در آن باn بار دستيابي مستقيم همه ركوردها خوانده مي شوند. در اين روش ابتدا همه گره هاي سمت چپ ترين شاخه خوانده مي شوند، اگر هر گره اي در اين شاخه، نشانه روي راست داشته باشد، آدرس ريشه زير درخت منشعب از آن گره در يك پشته نگهداري مي شود. پس از آنكه همه گره هاي سمت چپ ترين شاخه خوانده شدند، سمت چپ ترين شاخه از زير درختي كه آدرس ريشه آن، رأس پشته است، پيمايش شده گره هايش خوانده مي شوند. عمل خواندن زماني به پايان مي رسد كه پشته خالي باشد.

فايل با ساختار درخت جستجوي دودويي نخ كشي شده (TBST)
مي توان براي تسريع پردازش سريال ركورد ها (بر اساس نظم صعودي يا نزولي مقادير كليد) درخت جستجوي دودويي را كامل تر كرد به اين ترتيب كه به جاي نشانه روي تهي در هر گره، نشانه رو به ركورد پيشين و بعدي ايجاد كنيم. انگار گره ها را نخ كشي كرده باشيم با اين تغيير، فيلد نشانه روي چپ به گره پيشين و فيلد نشانه روي راست به گره بعدي نشانه مي رود.
نخ كشي گره ها سبب تسريع عمليات بازيابي بعدي و بازيابي قبلي مي شود، مشخص است كه پردازش سريال ركوردها با انجام يك سلسله عمليات بازيابي بعدي امكان پذير مي شود، در عوض عمليات درج و حذف ركورد زمانگير تر مي شود.

فايل با ساختار درخت صفحه بندي شده
مي توان گره هاي درخت را بلاك بندي كرد در اين صورت مي گوييم درخت صفحه بندي شده داريم.
بلاك بندي هاي گره هاي درخت، امكان مي دهد تا مثلاً ريشه درخت و احياناً گره فرزند چپ يا راست يا هر دو با يك بار دستيابي به دست آيند .
مي توان فاكتور بلاك بندي را چنان انتخاب كرد كه هر بلاك حاوي يك گره ريشه و دو زير درخت هر يك به عمقh=xsubtree باشد، به سهولت مي توان دريافت كه:

مزيت اصلي درخت صفحه بندي شده اين است كه عمق درخت به نسبتh-1 كاهش مي يابد و در نتيجه متوسط زمان جستجو كاهش مي پذيرد، اما اين ساختار مشكلاتي دارد، از جمله:

• بروز حافظه هرز در صفحه ها، شكل۹ سه صفحه (بلاك با سه گره) كاملاً استفاده شده اند. در بقيه صفحه ها، فضاي هرز پديد آمده است به علاوه با افزايش فاكتور بلاك بندي، فضاي هرز نيز زياد مي شود.
• بروز فزونكاري در سيستم به ويژه در عمليات درج و حذف (زيرا محتواي صفحه‌ها بايد متناسباً تنظيم شوند).

فايل با ساختار درخت متعادل(B-TREE)
معرفي ساختار
ساختار B-TREE، با رتبهm كه آن را باBm نمايش مي دهيم يك درخت جستجوي ۲M+1 راهه است كه در آن همه گره ها (غير از گره ريشه) حداقل نيمه پر بود و عمق تمام شاخه هاي آن يكسان است.

منظور از۲M+1 راهه اين است كه در هر گره۲M+1 فيلد نشانه رو وجود دارد.
اگر بخواهيم فايلي با ساختارB-TREE ايجاد كنيم بايد هر گره درختBM را به صورتي طراحي كنيم كه هر گره درخت۶M+2 فيلد دارد. فيلداول، فيلدC حاوي يك عدد صحيح است نشان دهنده تعداد كليدهاي موجود در گره، پس يك شمارنده است.

هر گره غير از گره ريشه حداقل نيمه پر است بنابراين مقدار فيلدC يعني C بين۲M,M است. مقادير كليدKi ها دو فيلد دردو طرف دارد: فيلدPi و فيلدri (I=1,2,…,۲M) جفت فيلدهاي (Pi,Ki) در واقع مدخلي را تشكيل مي دهند كه به گره اي در سطح پايين تر اشاره مي كند كه مقادير كليد موجود در آن ازki كوچكتر است. فيلدri حاوي نشانه رويي است به بلاك داده اي حاوي ركورد.

بالاخره يك فيلد نشانه رو در انتهاي گره داريم.P2M+1 كه به گره اي در سطح پايين اشاره مي كند كه در آن مقادير كليد ازK2M بزرگترند.
با توجه به ساختمان يك گره مي بينيم كه تعداد نشانه روهاي ساختاري يعنيPi در هر گره بايدC+1 باشند. بنابراين، هر گره، غير از گره ريشه حداقلM+1 گره فرزند دارد در حالي كه گره ريشه حداقل دو گره فرزند دارد.
بنابر آنچه گفته شد خصوصيات فايل با ساختارB-TREE از رتبه M را مي توان چنين برشمرد:
• يك درخت جستجوي۲M+1 راهه است.
• ژرفاي تمام شاخه ها يكسان است.
• گره ريشه حداقل دو گره فرزند دارد.
• گره هاي غير ريشه حداقلM+1 گره فرزند دارد و حداكثر فرزندان۲M+1 است.
• تعداد كليدها در هر گره يكي كمتر از تعداد فرزندان آن گره است.
جهت سادگي در نمايش، گره ها را چنين نشان مي دهيم.
عمليات در ساختار
فرض مي كنيم كه فايل با ساختار درختBM است. ركوردها بلاك بندي نشده اند. براي تسريع پردازش سريال ركوردها بهتر است كه ركوردها طبق نظم مورد نظر به يكديگر پيوند شوند.

واكنش ركورد
پس از يافتن گره مربوط به ركورد با استفاده از نشانه روri ركورد مورد دستيابي قرار مي‌گيرد. جستجوي گره مربوط به ركورد تا زماني ادامه مي يابد كه گره مورد نظر يافت شود و يا به نشانه روي تهي برخورد شود كه حالت عدم موفقيت است.
تعداد دفعاتI/O براي يافتن ركورد بستگي دارد به عمق درخت و يا به سطحي كه گره ناظر به ركورد قرار دارد. اگر عمق درخت راX فرض كنيم، تعداد دستيابي مستقيم لازم براي واكنشي ركورد چنين است.
بنابراينTf بستگي دارد به سطحي كه گره ناظر ركورد در آن قرار دارد و حداكثر برابر است با:
Tf=(x+1)(r+s+btt)

خواندن سريال تمام فايل
چون ركوردها را ترتيبي پيوندي در نظر گرفتيم. براي خواندن سريال تمام فايل، بهn بار دستيابي مستقيم نياز است. (ركورد بلاك بندي شده اند) بديهي است ايجاد و مديريت اين ليست پيوندي براي سيستم فزونكاري دارد.
عمل درج
عمل حذف
براي بررسي عمل حذف درختB2 شكل قبل را در نظر مي گيريم و تعدادي ركورد را حذف مي كنيم و طي اين عمليات، حالات مختلف عمل حذف را نشان مي دهيم.
• حذف ركورد با كليد۴۰
اين حذف ساده ترين حالت از حالات حذف است در بلاك حاوي اين ركورد، بيش از دو ركورد ذخيره شده است. بنابراين با حذف اين ركورد، هنوز سه ركورد در اين بلاك جاي دارد عمل ادغام يا توزيع مجدد كليدها پيش نمي آيد پس از حذف اين ركورد، درخت به صورت زير در مي آيد.