دانلود پاورپوینت درخت AVl با فرمت PPT ودر 29 اسلاید قابل ویرایش
قسمتی از متن پاورپوینت درخت AVl
انواع مختلف درخت BST ...
در اين درخت متوازن ميانگين مقايسه ها برابر 3.1است.
درخت BST متعادل
در درخت متعادل BST متوسط تعداد مقايسه پايينتر خواهد بود؟
براي اينكه درخت را متعادل نماييم:
–بايد درخت را از نو بازسازي كنيم. صرف وقت
–درخت را متوازن نگه داريم.
تعريف بازگشتي درخت متعادل دودويي
اگرT يك درخت دودويي غير تهي با زير درختان سمت چپ و راست TLوTRباشد، آنگاه Tيك درخت متعادل از نظر ارتفاع است اگر و فقط اگر
–TL و TR از نظر ارتفاع متعادل بوده و
–1<= |hL-hR| باشد كه در آن hL و hR به ترتيب ارتفاع TRو TL هستند.
ضريب تعادل
ضريب تعادل يك گره مانند T ، (BF(T ، در يك درخت دودويي به صورتhL-hR تعريف مي گردد.
براي هر گره T در درخت باينري متعادل، BF(T) برابر با 1- و 0 و 1 است.
انواع چرخش
چرخشها توسط نزديك ترين جد A يك گره ي درج شده مانند Y كه ضريب تعادل آن 2+ و 2- است ، مشخص مي گردد.
LL : گره ي جديد Y در زير درخت چپ مربوط به زير درخت چپ A درج مي شود.
LR: Y در زير درخت راست مربوط به زير درخت چپ A درج مي شود.
RR: Y در زير درخت راست مربوط به زير درخت راست A درج مي شود.
RL: Y در زير درخت چپ مربوط به زير درخت راست A درج مي شود.
LL و RR مانند LR و RL متقارن است .
هميشه ارتفاع زير درختي كه در چرخش شركت مي كند ، بدون تغيير باقي مي ماند.
براي انجام چرخش لازم است كه مكان گره A كه قرار است چرخش حول آن انجام گيرد تعيين شود.
نكات انواع چرخش
ضريب تعادل يك گره نمي تواند به ميزان 2+ و 2- تغيير كند، مگر انكه ضريب تعادل آن قبل از جايگذاري 1+ و1- باشد.
بنابراين مي توان گفت كه گره A نزديكترين جد گره جديد است كه ضريب تعادل آن قبل از درج 1+ و1- مي باشد.
زماني كه درج يك گره منجر به يك درخت نامتعادل نگردد، چه مساله اي رخ خواهد داد؟
اگر در پي يك درج درخت حالت نامتعادل پيدا نكند ، در اينصورت حتما مقدار جديد ضريب تعادل A برابر 0 خواهد بود.
اگر جد A با ضريب توازن 1+و يا 1- وجود نداشته باشد، A را ريشه اختيار كنيد.
ضريب هاي توازن گره ها از A به پدر گره ي جديد ، به 1+ و1- تغيير مي كند.
