ساختارهای درختی (درس بازیابی اطلاعات)
ساختارهای درختی فایل با ساختار درخت جستجوی دودویی در فایل با ساختار ترتیبی لازمه استفاده از الگوریتم جستجوی دودویی این است كه بلاك های داده ای به طور پیوسته ذخیره شده اند اگر بلاك ها به طور ناپیوسته ذخیره و به هم پیوند شده باشند یافتن آدرس بلاك میانی ناممكن است |
دسته بندی | کامپیوتر |
فرمت فایل | doc |
حجم فایل | 27 کیلو بایت |
تعداد صفحات فایل | 37 |
فایل با ساختار درخت جستجوی دودویی باn ركورد و كلید اصلیi=1,2,…,n,ki گونهای از درخت دودویی است كه دو خاصیت زیر را دارد.
1- هر گره درخت، بسته به طرز پیاده سازی، حداقل سه یا چهار فیلد در هر دو حالت دو تا از فیلدها حاوی نشانه رو به گره های سمت چپ و سمت راست هستندRPTR, LPTR در حالت وجود سه فیلد، فیلد سوم حاوی خود ركورد است. در غیر این صورت در فیلد سوم كلید ركورد قرار دارد و فیلد چهارم حاوی نشانه روی به بلاك داده ای حاوی ركورد است.
2- اگرki كلید یك ركورد باشد كلید تمام ركوردهای موجود در گره های زیردرخت سمت چپ ازki كوچكتر و كلید تمام ركوردهای موجود در گره های زیر درخت سمت راست، از ki بزرگترند،
عملیات در فایل
واكنش ركورد
الگوریتم واكنشی خیلی ساده است سیستم ابتدا به گره ریشه دستیابی پیدا می كند عمل مقایسه بین كلید ركورد مورد نظر و كلید ركورد موجود در گره ریشه انجام می شود، اگر تساوی برقرار باشد، ركورد پیدا شده است وگرنه، یكی از دو گره سمت راست یا سمت چپ گره ریشه مورد دستیابی قرار می گیرد و عمل مقایسه انجام می شود، این عملیات تا پایان یافتن ركورد مورد نظر یا برخورد به نشانه روی تهی تكرار می شود اگر ركورد مورد نظر در سطحk باشد در حافظه اصلی ذخیره شود برای واكنش ركوردk+1 بار دستیابی مستقیم لازم است.