پاورپوینت درخت AVL

اختصاصی از یارا فایل پاورپوینت درخت AVL دانلود با لینک مستقیم و پرسرعت .

29 اسلاید

lدر درخت متعادل BST متوسط تعداد مقایسه پایینتر خواهد بود؟

lبرای اینکه درخت را متعادل نماییم:

–باید درخت را از نو بازسازی کنیم. صرف وقت

–درخت را متوازن نگه داریم.

lاگرT یک درخت دودویی غیر تهی با زیر درختان سمت چپ و راست TLوTRباشد، آنگاه Tیک درخت متعادل از نظر ارتفاع است اگر و فقط اگر

–TL و TR از نظر ارتفاع متعادل بوده و

–1<= |hL-hR| باشد که در آن hL و hR به ترتیب ارتفاع TRو TL هستند.

lضریب تعادل یک گره مانند T ، (BF(T ، در یک درخت دودویی به صورتhL-hR  تعریف می گردد.

l

lبرای هر گره T در درخت باینری متعادل، BF(T) برابر با 1- و 0 و 1 است.

l

lچرخشها توسط نزدیک ترین جد A یک گره ی درج شده مانند Y که ضریب تعادل آن 2+ و 2- است ، مشخص می گردد.

l

lLL : گره ی جدید Y در زیر درخت چپ مربوط به زیر درخت چپ A درج می شود.

lLR: Y در زیر درخت راست مربوط به زیر درخت چپ A درج می شود.

lRR: Y در زیر درخت راست مربوط به زیر درخت راست A درج می شود.

lRL: Y در زیر درخت چپ مربوط به زیر درخت راست A درج می شود.

l LL و RR مانند LR و RL متقارن است .