نام فایل : درخت AVl (2)

فرمت : .ppt

تعداد صفحه/اسلاید : 29

حجم : 206 کیلوبایت

درخت AVL
انواع مختلف درخت BST
ميانگين تعداد مقايسه ها 3.5است.

انواع مختلف درخت 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 است.
....