بخشی از پاورپوینت
اسلاید 1 :
درخت BST متعادل
lدر درخت متعادل BST متوسط تعداد مقايسه پايينتر خواهد بود؟
lبراي اينكه درخت را متعادل نماييم:
–بايد درخت را از نو بازسازي كنيم. صرف وقت
–درخت را متوازن نگه داريم.
اسلاید 2 :
تعريف بازگشتي درخت متعادل دودويي
lاگرT يك درخت دودويي غير تهي با زير درختان سمت چپ و راست TLوTRباشد، آنگاه Tيك درخت متعادل از نظر ارتفاع است اگر و فقط اگر
–TL و TR از نظر ارتفاع متعادل بوده و
–1<= |hL-hR| باشد كه در آن hL و hR به ترتيب ارتفاع TRو TL هستند.
اسلاید 3 :
ضريب تعادل
lضريب تعادل يك گره مانند T ، (BF(T ، در يك درخت دودويي به صورتhL-hR تعريف مي گردد.
l
lبراي هر گره T در درخت باينري متعادل، BF(T) برابر با 1- و 0 و 1 است.
l
اسلاید 4 :
انواع چرخش
lچرخشها توسط نزديك ترين جد A يك گره ي درج شده مانند Y كه ضريب تعادل آن 2+ و 2- است ، مشخص مي گردد.
l
lLL : گره ي جديد Y در زير درخت چپ مربوط به زير درخت چپ A درج مي شود.
lLR: Y در زير درخت راست مربوط به زير درخت چپ A درج مي شود.
lRR: Y در زير درخت راست مربوط به زير درخت راست A درج مي شود.
lRL: Y در زير درخت چپ مربوط به زير درخت راست A درج مي شود.
l LL و RR مانند LR و RL متقارن است .
اسلاید 5 :
انواع چرخش
lهميشه ارتفاع زير درختي كه در چرخش شركت مي كند ، بدون تغيير باقي مي ماند.
lبراي انجام چرخش لازم است كه مكان گره A كه قرار است چرخش حول آن انجام گيرد تعيين شود.
اسلاید 6 :
نكات انواع چرخش
lضريب تعادل يك گره نمي تواند به ميزان 2+ و 2- تغيير كند، مگر انكه ضريب تعادل آن قبل از جايگذاري 1+ و1- باشد.
l بنابراين مي توان گفت كه گره A نزديكترين جد گره جديد است كه ضريب تعادل آن قبل از درج 1+ و1- مي باشد.
اسلاید 7 :
نكات انواع چرخش
lزماني كه درج يك گره منجر به يك درخت نامتعادل نگردد، چه مساله اي رخ خواهد داد؟
lاگر در پي يك درج درخت حالت نامتعادل پيدا نكند ، در اينصورت حتما مقدار جديد ضريب تعادل A برابر 0 خواهد بود.
lاگر جد A با ضريب توازن 1+و يا 1- وجود نداشته باشد، A را ريشه اختيار كنيد.
lضريب هاي توازن گره ها از A به پدر گره ي جديد ، به 1+ و1- تغيير مي كند.
اسلاید 8 :
ارتفاع درخت AVL
lاگر h ارتفاع درخت قبل از جايگذاري باشد ، آنگاه زمان لازم براي درج يك شناسه جديد برابر O(h) خواهد بود.
كه همان زمان درختهاي جستجوي دودويي نامتوازن است.
اگرجه اكنون سربار آن بصورت قابل توجهي بيشتر است.
lدر مورد درخت AVL ،h حداكثر مي تواند O(log n) باشد.از ابن رو زمان عمل درج در بد ترين حالت برابر O(log n) است.
