دانلود بررسی ساختار های درختی در pdf

مقدمه

در فایل با ساختار ترتیبی لازمه استفاده از الگوریتم جستجوی دودویی این است كه بلاك های داده ای به طور پیوسته ذخیره شده اند اگر بلاك ها به طور ناپیوسته ذخیره و به هم پیوند شده باشند یافتن آدرس بلاك میانی ناممكن است.
فایل با ساختار درخت جستجوی دودویی باn ركورد و كلید اصلیi=1,2,…,n,ki گونه‌ای از درخت دودویی است كه دو خاصیت زیر را دارد.
1- هر گره درخت، بسته به طرز پیاده سازی، حداقل سه یا چهار فیلد در هر دو حالت دو تا از فیلدها حاوی نشانه رو به گره های سمت چپ و سمت راست هستندRPTR, LPTR در حالت وجود سه فیلد، فیلد سوم حاوی خود ركورد است. در غیر این صورت در فیلد سوم كلید ركورد قرار دارد و فیلد چهارم حاوی نشانه روی به بلاك داده ای حاوی ركورد است.
2- اگرki كلید یك ركورد باشد كلید تمام ركوردهای موجود در گره های زیردرخت سمت چپ ازki كوچكتر و كلید تمام ركوردهای موجود در گره های زیر درخت سمت راست، از ki بزرگترند،
عملیات در فایل
واكنش ركورد
الگوریتم واكنشی خیلی ساده است سیستم ابتدا به گره ریشه دستیابی پیدا می كند عمل مقایسه بین كلید ركورد مورد نظر و كلید ركورد موجود در گره ریشه انجام می شود، اگر تساوی برقرار باشد، ركورد پیدا شده است وگرنه، یكی از دو گره سمت راست یا سمت چپ گره ریشه مورد دستیابی قرار می گیرد و عمل مقایسه انجام می شود، این عملیات تا پایان یافتن ركورد مورد نظر یا برخورد به نشانه روی تهی تكرار می شود اگر ركورد مورد نظر در سطحk باشد در حافظه اصلی ذخیره شود برای واكنش ركوردk+1 بار دستیابی مستقیم لازم است.
كارایی این ساختار در واكنشیس ركورد وقتی حداكثر است كه ژرفای حداقل باشد و زمانی حداقل است كه ژرفای درخت حداكثر باشد.
ژرفای درخت زمانی حداكثر است كه در هر سطح تنها یك گره وجود داشته باشد در این حالت ژرفای درختN است و متوسط دستیابی (ANA) مستقیم برای واكنشی ركورد برابر است با:
               
از طرف دیگر ژرفای درخت زمانی در حداقل است كه در هر سطح مثلاً سطحk ام، غیر از سطح ریشه دقیقاًk2 گروه وجود داشته باشد.