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 متقارن است .
پاورپوینت درخت AVL