***4
درخت BST متعادل
در درخت متعادل BST متوسط تعداد مقایسه پایینتر خواهد بود؟
برای اینکه درخت را متعادل نماییم:
–باید درخت را از نو بازسازی کنیم. صرف وقت
–درخت را متوازن نگه داریم.
***5
تعریف بازگشتی درخت متعادل دودویی
اگرT یک درخت دودویی غیر تهی با زیر درختان سمت چپ و راست TLوTRباشد، آنگاه Tیک درخت متعادل از نظر ارتفاع است اگر و فقط اگر
–TL و TR از نظر ارتفاع متعادل بوده و
–1<= |hL-hR| باشد که در آن hL و hR به ترتیب ارتفاع TRو TL هستند.
***6
ضریب تعادل
ضریب تعادل یک گره مانند T ، (BF(T ، در یک درخت دودویی به صورتhL-hR تعریف می گردد.
برای هر گره T در درخت باینری متعادل، BF(T) برابر با 1- و 0 و 1 است.