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

موضوع : تحقیق ساختار های درختی

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

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

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

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

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

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

واكنش ركورد

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

كارايي اين ساختار در واكنشيس ركورد وقتي حداكثر است كه ژرفاي حداقل باشد و زماني حداقل است كه ژرفاي درخت حداكثر باشد

ساختارهاي درختي درس بازيابي اطلاعات

فهرست مطالب

ساختارهاي درختي

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

فايل با ساختار درخت جستجوي دودويي نخ كشي شده

فايل با ساختار درخت صفحه بندي شده

فايل با ساختار درخت متعادل

فايل درختي

فايل با ساختار درخت B+

فايل با ساختار درخت k-d

فايل با ساختار توالي