ساختارهای درختی (درس بازیابی اطلاعات)

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

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

2- اگرki كلید یك ركورد باشد كلید تمام ركوردهای موجود در گره های زیردرخت سمت چپ ازki كوچكتر و كلید تمام ركوردهای موجود در گره های زیر درخت سمت راست، از ki بزرگترند،

عملیات در فایل

واكنش ركورد

الگوریتم واكنشی خیلی ساده است سیستم ابتدا به گره ریشه دستیابی پیدا می كند عمل مقایسه بین كلید ركورد مورد نظر و كلید ركورد موجود در گره ریشه انجام می شود، اگر تساوی برقرار باشد، ركورد پیدا شده است وگرنه، یكی از دو گره سمت راست یا سمت چپ گره ریشه مورد دستیابی قرار می گیرد و عمل مقایسه انجام می شود، این عملیات تا پایان یافتن ركورد مورد نظر یا برخورد به نشانه روی تهی تكرار می شود اگر ركورد مورد نظر در سطحk باشد در حافظه اصلی ذخیره شود برای واكنش ركوردk+1 بار دستیابی مستقیم لازم است.