پروژه ساختارهای درختی

ساختار های درختی

فایل با ساختار درخت جستجوی دودویی

در فایل با ساختار ترتیبی لازمه استفاده از الگوریتم جستجوی دودویی این است که بلاک های داده ای به طور پیوسته ذخیره شده اند اگر بلاک ها به طور ناپیوسته ذخیره و به هم پیوند شده باشند یافتن آدرس بلاک میانی ناممکن است.

فایل با ساختار درخت جستجوی دودویی باn رکورد و کلید اصلیi=1,2,…,n,ki گونه‌ای از درخت دودویی است که دو خاصیت زیر را دارد.

1- هر گره درخت، بسته به طرز پیاده سازی، حداقل سه یا چهار فیلد در هر دو حالت دو تا از فیلدها حاوی نشانه رو به گره های سمت چپ و سمت راست هستندRPTR, LPTR در حالت وجود سه فیلد، فیلد سوم حاوی خود رکورد است. در غیر این صورت در فیلد سوم کلید رکورد قرار دارد و فیلد چهارم حاوی نشانه روی به بلاک داده ای حاوی رکورد است.

2- اگر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 کاهش می یابد و در نتیجه متوسط زمان جستجو کاهش می پذیرد، اما این ساختار مشکلاتی دارد، از جمله:

بروز حافظه هرز در صفحه ها، شکل9 سه صفحه (بلاک با سه گره) کاملاً استفاده شده اند. در بقیه صفحه ها، فضای هرز پدید آمده است به علاوه با افزایش فاکتور بلاک بندی، فضای هرز نیز زیاد می شود.

بروز فزونکاری در سیستم به ویژه در عملیات درج و حذف (زیرا محتوای صفحه‌ها باید متناسباً تنظیم شوند).

فایل با ساختار درخت متعادل(B-TREE)

معرفی ساختار

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

منظور از2M+1 راهه این است که در هر گره2M+1 فیلد نشانه رو وجود دارد.

اگر بخواهیم فایلی با ساختارB-TREE ایجاد کنیم باید هر گره درختBM را به صورتی طراحی کنیم که هر گره درخت6M+2 فیلد دارد. فیلداول، فیلدC حاوی یک عدد صحیح است نشان دهنده تعداد کلیدهای موجود در گره، پس یک شمارنده است.

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

بالاخره یک فیلد نشانه رو در انتهای گره داریم.P2M+1 که به گره ای در سطح پایین اشاره می کند که در آن مقادیر کلید ازK2M بزرگترند.

با توجه به ساختمان یک گره می بینیم که تعداد نشانه روهای ساختاری یعنیPi در هر گره بایدC+1 باشند. بنابراین، هر گره، غیر از گره ریشه حداقلM+1 گره فرزند دارد در حالی که گره ریشه حداقل دو گره فرزند دارد.

بنابر آنچه گفته شد خصوصیات فایل با ساختارB-TREE از رتبه M را می توان چنین برشمرد:

یک درخت جستجوی2M+1 راهه است.