پاورپوینت درخت 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  تعریف می گردد. llبرای هر گره T در درخت باینری متعادل، BF(T) برابر با 1- و 0 و 1 است.llچرخشها توسط نزدیک ترین جد A یک گره ی درج شده مانند Y که ضریب تعادل آن 2+ و 2- است ، مشخص می گردد.llLL : گره ی جدید Y در زیر درخت چپ مربوط به زیر درخت چپ A درج می شود.lLR: Y در زیر درخت راست مربوط به زیر درخت چپ A درج می شود.lRR: Y در زیر درخت راست مربوط به زیر درخت راست A درج می شود.lRL: Y در زیر درخت چپ مربوط به زیر درخت راست A درج می شود.l LL و RR مانند LR و RL متقارن است .