Уравнотежено бинарно стабло познато је и као стабло уравнотежене висине. Дефинише се као бинарно стабло када разлика између висине левог и десног подстабла није већа од м, где је м обично једнако 1. Висина дрвета је број ивица на најдужој путањи између коренски чвор и лисни чвор.
Горње дрво је а бинарно стабло претраге . Бинарно стабло претраге је стабло у коме сваки чвор на левој страни има нижу вредност од свог родитељског чвора, а чвор на десној страни има већу вредност од свог родитељског чвора. У горњем стаблу, н1 је коренски чвор, а н4, н6, н7 су чворови листа. Чвор н7 је најудаљенији чвор од коренског чвора. н4 и н6 садрже 2 ивице и постоје три ивице између коренског чвора и н7 чвора. Пошто је н7 најудаљенији од коренског чвора; дакле, висина горњег дрвета је 3.
креирање табеле пророчишта
Сада ћемо видети да ли је горе наведено стабло уравнотежено или не. Лево подстабло садржи чворове н2, н4, н5 и н7, док десно подстабло садржи чворове н3 и н6. Лево подстабло има два лисна чвора, тј. н4 и н7. Постоји само једна ивица између чворова н2 и н4 и две ивице између чворова н7 и н2; стога је чвор н7 најудаљенији од коренског чвора. Висина левог подстабла је 2. Десно подстабло садржи само један листни чвор, тј., н6, и има само једну ивицу; према томе, висина десног подстабла је 1. Разлика између висина левог подстабла и десног подстабла је 1. Пошто смо добили вредност 1 тако да можемо рећи да је горе наведено стабло висинско избалансирано дрво. Овај процес израчунавања разлике између висина треба извршити за сваки чвор као што је н2, н3, н4, н5, н6 и н7. Када обрадимо сваки чвор, тада ћемо наћи да вредност к није већа од 1, тако да можемо рећи да је горе наведено стабло уравнотежено бинарно дрво .
У горњем стаблу, н6, н4 и н3 су чворови листа, где је н6 најудаљенији чвор од коренског чвора. Између коренског чвора и лисног чвора постоје три ивице; дакле, висина горњег стабла је 3. Када сматрамо н1 као коренски чвор, онда лево подстабло садржи чворове н2, н4, н5 и н6, док подстабло садржи чвор н3. У левом подстаблу, н2 је коренски чвор, а н4 и н6 су листови. Међу н4 и н6 чворовима, н6 је најудаљенији чвор од свог коренског чвора, а н6 има две ивице; према томе, висина левог подстабла је 2. Десно подстабло има било које дете са леве и десне стране; дакле, висина десног подстабла је 0. Пошто је висина левог подстабла 2, а десног подстабла 0, па је разлика између висине левог подстабла и десног подстабла 2. Према дефиницији, разлика између висине левог подстабла и десног подстабла не сме бити већа од 1. У овом случају разлика постаје 2, што је веће од 1; стога је горенаведено бинарно стабло неуравнотежено бинарно стабло претраге.
Зашто нам је потребно уравнотежено бинарно стабло?
Хајде да разумемо потребу за уравнотеженим бинарним стаблом кроз пример.
Горње стабло је бинарно стабло претраге јер су сви леви чворови подстабла мањи од његовог родитељског чвора, а сви десни чворови подстабла су већи од његовог родитељског чвора. Претпоставимо да желимо да пронађемо вредност 79 у горњем стаблу. Прво, упоредимо вредност чвора н1 са 79; пошто вредност 79 није једнака 35 и већа је од 35 па прелазимо на чвор н3, тј. 48. Пошто вредност 79 није једнака 48 и 79 је већа од 48, па се померамо удесно дете од 48. Вредност десног детета чвора 48 је 79 што је једнако вредности која се тражи. Број скокова потребних за претраживање елемента 79 је 2, а максимални број скокова потребан за претраживање било ког елемента је 2. Просечан случај за претрагу елемента је О(логн).
Горње стабло је такође бинарно стабло претраге јер су сви леви чворови подстабла мањи од његовог родитељског чвора, а сви десни чворови подстабла су већи од његовог родитељског чвора. Претпоставимо да желимо да пронађемо вредност 79 у горњем стаблу. Прво, упоредимо вредност 79 са чвором н4, тј. 13. Пошто је вредност 79 већа од 13, прелазимо на десно дете чвора 13, тј. н2 (21). Вредност чвора н2 је 21 што је мање од 79, па се поново померамо удесно од чвора 21. Вредност десног детета чвора 21 је 29. Пошто је вредност 79 већа од 29 па се померамо удесно дете чвора 29. Вредност десног детета чвора 29 је 35 што је мање од 79 тако да прелазимо на десно дете чвора 35, тј. 48. Вредност 79 је већа од 48, тако да прелазимо на десно дете чвора 48. Вредност десног подређеног чвора од 48 је 79 што је једнако вредности која се тражи. У овом случају, број скокова потребних за претрагу елемента је 5. У овом случају, најгори случај је О(н).
колико је градова у Сједињеним Америчким Државама
Ако се број чворова повећава, формула која се користи у дијаграму стабла1 је ефикаснија од формуле која се користи у дијаграму стабла2. Претпоставимо да је број доступних чворова у оба горња стабла 100.000. За претрагу било ког елемента у дијаграму стабла2, потребно је време од 100.000 µс, док је време потребно за претрагу елемента у дијаграму стабла лог(100.000) што је једнако 16.6 µс. Можемо приметити огромну разлику у времену између два дрвета. Стога закључујемо да бинарно стабло баланса омогућава брже претраживање од структуре података линеарног стабла.