Uravnoteženo binarno stablo također je poznato kao stablo uravnoteženo po visini. Definira se kao binarno stablo kada razlika između visine lijevog podstabla i desnog podstabla nije veća od m, gdje je m obično jednako 1. Visina stabla je broj bridova na najdužoj stazi između korijenski čvor i listni čvor.
Gornje stablo je a binarno stablo pretraživanja . Binarno stablo pretraživanja je stablo u kojem svaki čvor s lijeve strane ima nižu vrijednost od svog nadređenog čvora, a čvor s desne strane ima višu vrijednost od svog nadređenog čvora. U gornjem stablu, n1 je korijenski čvor, a n4, n6, n7 su lisnati čvorovi. Čvor n7 je najudaljeniji čvor od korijenskog čvora. n4 i n6 sadrže 2 ruba i postoje tri ruba između korijenskog čvora i n7 čvora. Budući da je n7 najudaljeniji od korijenskog čvora; dakle, visina gornjeg stabla je 3.
Sada ćemo vidjeti je li gornje stablo uravnoteženo ili ne. Lijevo podstablo sadrži čvorove n2, n4, n5 i n7, dok desno podstablo sadrži čvorove n3 i n6. Lijevo podstablo ima dva lisna čvora, tj. n4 i n7. Postoji samo jedan brid između čvorova n2 i n4 i dva brida između čvorova n7 i n2; stoga je čvor n7 najudaljeniji od korijenskog čvora. Visina lijevog podstabla je 2. Desno podstablo sadrži samo jedan čvor lista, tj. n6, i ima samo jedan rub; dakle, visina desnog podstabla je 1. Razlika između visina lijevog podstabla i desnog podstabla je 1. Budući da smo dobili vrijednost 1, možemo reći da je gornje stablo visinski uravnoteženo stablo. Ovaj postupak izračuna razlike između visina treba izvesti za svaki čvor kao što su n2, n3, n4, n5, n6 i n7. Kada obradimo svaki čvor, otkrit ćemo da vrijednost k nije veća od 1, tako da možemo reći da je gornje stablo uravnoteženo binarno stablo .
U gornjem stablu, n6, n4 i n3 su čvorovi lista, gdje je n6 najudaljeniji čvor od korijenskog čvora. Tri ruba postoje između korijenskog čvora i lisnog čvora; stoga je visina gornjeg stabla 3. Kada n1 smatramo korijenskim čvorom, tada lijevo podstablo sadrži čvorove n2, n4, n5 i n6, dok podstablo sadrži čvor n3. U lijevom podstablu, n2 je korijenski čvor, a n4 i n6 su lisni čvorovi. Među n4 i n6 čvorovima, n6 je najudaljeniji čvor od svog korijenskog čvora, a n6 ima dva ruba; prema tome, visina lijevog podstabla je 2. Desno podstablo ima dijete sa svoje lijeve i desne strane; prema tome, visina desnog podstabla je 0. Budući da je visina lijevog podstabla 2, a desnog podstabla 0, razlika između visine lijevog podstabla i desnog podstabla je 2. Prema definiciji, razlika između visine lijevog podstabla i desnog podstabla ne smije biti veća od 1. U ovom slučaju dolazi do razlike 2, što je veće od 1; prema tome, gornje binarno stablo je neuravnoteženo binarno stablo pretraživanja.
Zašto nam je potrebno uravnoteženo binarno stablo?
Shvatimo potrebu za uravnoteženim binarnim stablom kroz primjer.
Gornje stablo je binarno stablo pretraživanja jer su svi lijevi čvorovi podstabla manji od njegovog nadređenog čvora, a svi desni čvorovi podstabla su veći od njegovog nadređenog čvora. Pretpostavimo da želimo pronaći vrijednost 79 u gornjem stablu. Prvo, uspoređujemo vrijednost čvora n1 sa 79; budući da vrijednost 79 nije jednaka 35, a veća je od 35, pomičemo se u čvor n3, tj. 48. Budući da vrijednost 79 nije jednaka 48, a 79 je veća od 48, pomičemo se udesno. dijete od 48. Vrijednost desnog djeteta od čvora 48 je 79 što je jednako vrijednosti koju treba pretražiti. Broj skokova potrebnih za pretraživanje elementa 79 je 2, a maksimalan broj skokova potrebnih za pretraživanje bilo kojeg elementa je 2. Prosječan slučaj pretraživanja elementa je O(logn).
Gornje stablo također je binarno stablo pretraživanja jer su svi lijevi čvorovi podstabla manji od njegovog nadređenog čvora, a svi desni čvorovi podstabla su veći od njegovog nadređenog čvora. Pretpostavimo da želimo pronaći vrijednost 79 u gornjem stablu. Prvo uspoređujemo vrijednost 79 s čvorom n4, tj. 13. Budući da je vrijednost 79 veća od 13, pomičemo se na desno dijete čvora 13, tj. n2 (21). Vrijednost čvora n2 je 21 što je manje od 79, pa se ponovno pomičemo udesno od čvora 21. Vrijednost desnog djeteta čvora 21 je 29. Budući da je vrijednost 79 veća od 29, pomičemo se udesno. dijete čvora 29. Vrijednost desnog djeteta čvora 29 je 35 što je manje od 79 pa se pomičemo na desno dijete čvora 35, tj. 48. Vrijednost 79 je veće od 48, pa se pomičemo na desno dijete od čvora 48. Vrijednost desnog podređenog čvora od 48 je 79 što je jednako vrijednosti koju treba pretražiti. U ovom slučaju, broj skokova potrebnih za pretraživanje elementa je 5. U ovom slučaju, najgori slučaj je O(n).
Ako se broj čvorova poveća, formula koja se koristi u dijagramu stabla1 učinkovitija je od formule koja se koristi u dijagramu stabla2. Pretpostavimo da je broj dostupnih čvorova u oba gornja stabla 100 000. Za pretraživanje bilo kojeg elementa u dijagramu stabla2, potrebno je vrijeme 100 000 µs, dok je vrijeme potrebno za pretraživanje elementa u dijagramu stabla log(100 000) što je jednako 16,6 µs. Možemo uočiti ogromnu razliku u vremenu između dva stabla. Stoga zaključujemo da ravnotežno binarno stablo omogućuje pretraživanje brže od strukture podataka linearnog stabla.