دسته | مهندسی نرم افزار |
---|---|
حجم | 22/91 کیلوبایت |
صفحه | 29 |
فرمت | pptx |
قیمت | 36000 تومان |
دانلود پاورپوينت درخت AVL اسلاید 29
در درخت متعادل BST متوسط تعداد مقايسه پايينتر خواهد بود؟
براي اينكه درخت را متعادل نماييم:
بايد درخت را از نو بازسازي كنيم. صرف وقت
درخت را متوازن نگه داريم.
اگرT يك درخت دودويي غير تهي با زير درختان سمت چپ و راست TLوTRباشد، آنگاه Tيك درخت متعادل از نظر ارتفاع است اگر و فقط اگر
TL و TR از نظر ارتفاع متعادل بوده و
1<= |hL-hR| باشد كه در آن hL و hR به ترتيب ارتفاع TRو TL هستند.
چرخشها توسط نزديك ترين جد A يك گره ي درج شده مانند Y كه ضريب تعادل آن 2+ و 2- است ، مشخص مي گردد.
LL : گره ي جديد Y در زير درخت چپ مربوط به زير درخت چپ A درج مي شود.
LR:Y در زير درخت راست مربوط به زير درخت چپ A درج مي شود.
RR:Y در زير درخت راست مربوط به زير درخت راست A درج مي شود.
RL:Y در زير درخت چپ مربوط به زير درخت راست A درج مي شود.
LL و RR مانند LR و RL متقارن است .
فهرست مطالب
انواع مختلف درخت BST
درخت BST متعادل
تعريف بازگشتي درخت متعادل دودويي
ضريب تعادل
ضريب توازن در ساخت يك درخت BST
متوازن سازي-RR
ادامه مثال
متوازن سازي-LL
اضافه سازي و متوازن سازي-LR
مثال
اضافه سازي و متوازن سازي-RL
اضافه سازي و متوازن سازي-LR
انواع چرخش
نكات انواع چرخش
اضافه سازي و متوازن سازي-RR
اضافه سازي
نكات انواع چرخش
بررسی زمان الگوريتم