Uravnoteženo binarno drevo je znano tudi kot višinsko uravnoteženo drevo. Definirano je kot binarno drevo, ko razlika med višino levega poddrevesa in desnega poddrevesa ni večja od m, kjer je m običajno enak 1. Višina drevesa je število robov na najdaljši poti med korensko vozlišče in listno vozlišče.
Zgornje drevo je a binarno iskalno drevo . Binarno iskalno drevo je drevo, v katerem ima vsako vozlišče na levi strani nižjo vrednost od svojega nadrejenega vozlišča, vozlišče na desni strani pa ima višjo vrednost od svojega nadrejenega vozlišča. V zgornjem drevesu je n1 korensko vozlišče, n4, n6, n7 pa so listna vozlišča. Vozlišče n7 je najbolj oddaljeno vozlišče od korenskega vozlišča. N4 in n6 vsebujeta 2 robova, med korenskim vozliščem in vozliščem n7 pa obstajajo trije robovi. Ker je n7 najbolj oddaljen od korenskega vozlišča; torej je višina zgornjega drevesa 3.
Zdaj bomo videli, ali je zgornje drevo uravnoteženo ali ne. Levo poddrevo vsebuje vozlišča n2, n4, n5 in n7, medtem ko desno poddrevo vsebuje vozlišči n3 in n6. Levo poddrevo ima dve vozlišči listov, tj. n4 in n7. Med vozliščema n2 in n4 je samo en rob, med vozliščema n7 in n2 pa dva robova; zato je vozlišče n7 najbolj oddaljeno od korenskega vozlišča. Višina levega poddrevesa je 2. Desno poddrevo vsebuje samo eno listno vozlišče, tj. n6, in ima samo en rob; zato je višina desnega poddrevesa 1. Razlika med višinama levega in desnega poddrevesa je 1. Ker smo dobili vrednost 1, lahko rečemo, da je zgornje drevo višinsko uravnoteženo drevo. Ta postopek izračuna razlike med višinami je treba izvesti za vsako vozlišče, kot je n2, n3, n4, n5, n6 in n7. Ko obdelamo vsako vozlišče, bomo ugotovili, da vrednost k ni večja od 1, tako da lahko rečemo, da je zgornje drevo uravnoteženo binarno drevo .
V zgornjem drevesu so n6, n4 in n3 listna vozlišča, kjer je n6 najbolj oddaljeno vozlišče od korenskega vozlišča. Med korenskim in listnim vozliščem obstajajo trije robovi; zato je višina zgornjega drevesa 3. Če upoštevamo n1 kot korensko vozlišče, potem levo poddrevo vsebuje vozlišča n2, n4, n5 in n6, medtem ko poddrevo vsebuje vozlišče n3. V levem poddrevesu je n2 korensko vozlišče, n4 in n6 pa listna vozlišča. Med vozlišči n4 in n6 je n6 najbolj oddaljeno vozlišče od svojega korenskega vozlišča, n6 pa ima dva robova; zato je višina levega poddrevesa 2. Desno poddrevo ima katerega koli otroka na svoji levi in desni; zato je višina desnega poddrevesa 0. Ker je višina levega poddrevesa 2 in desnega poddrevesa 0, je razlika med višino levega in desnega poddrevesa 2. Po definiciji je razlika med višino levega in desnega poddrevesa ne sme biti večja od 1. V tem primeru je razlika 2, kar je večje od 1; zato je zgornje binarno drevo neuravnoteženo binarno iskalno drevo.
Zakaj potrebujemo uravnoteženo binarno drevo?
Razumejmo potrebo po uravnoteženem binarnem drevesu na primeru.
Zgornje drevo je binarno iskalno drevo, ker so vsa leva vozlišča poddrevesa manjša od njegovega nadrejenega vozlišča in vsa desna vozlišča poddrevesa so večja od njegovega nadrejenega vozlišča. Recimo, da želimo najti vrednost 79 v zgornjem drevesu. Najprej primerjamo vrednost vozlišča n1 s 79; ker vrednost 79 ni enaka 35 in je večja od 35, se premaknemo na vozlišče n3, tj. 48. Ker vrednost 79 ni enaka 48 in je 79 večje od 48, se premaknemo v desno otrok od 48. Vrednost desnega podrejenega vozlišča 48 je 79, kar je enako vrednosti, ki jo je treba iskati. Število skokov, potrebnih za iskanje elementa 79, je 2 in največje število skokov, potrebnih za iskanje katerega koli elementa, je 2. Povprečni primer iskanja elementa je O(logn).
Zgornje drevo je tudi binarno iskalno drevo, ker so vsa leva vozlišča poddrevesa manjša od nadrejenega vozlišča in vsa desna vozlišča poddrevesa so večja od nadrejenega vozlišča. Recimo, da želimo najti vrednost 79 v zgornjem drevesu. Najprej primerjamo vrednost 79 z vozliščem n4, tj. 13. Ker je vrednost 79 večja od 13, se pomaknemo k desnemu podrejenemu vozlišču 13, tj. n2 (21). Vrednost vozlišča n2 je 21, kar je manjše od 79, zato se ponovno premaknemo desno od vozlišča 21. Vrednost desnega podrejenega vozlišča 21 je 29. Ker je vrednost 79 večja od 29, se premaknemo v desno. podrejenega vozlišča 29. Vrednost desnega podrejenega vozlišča 29 je 35, kar je manjše od 79, zato se premaknemo na desni podrejeni vozlišča 35, tj. 48. Vrednost 79 je večja od 48, zato se premaknemo na desnega podrejenega vozlišča 29. vozlišča 48. Vrednost desnega podrejenega vozlišča 48 je 79, kar je enako vrednosti za iskanje. V tem primeru je število skokov, potrebnih za iskanje elementa, 5. V tem primeru je najslabši primer O(n).
Če se število vozlišč poveča, je formula, uporabljena v drevesnem diagramu1, učinkovitejša od formule, uporabljene v drevesnem diagramu2. Recimo, da je število vozlišč, ki so na voljo v obeh zgornjih drevesih, 100.000. Za iskanje katerega koli elementa v drevesnem diagramu2 je potreben čas 100.000 µs, medtem ko je čas, potreben za iskanje elementa v drevesnem diagramu, log(100.000), kar je enako 16,6 µs. Opazimo lahko ogromno časovno razliko med zgornjima dvema drevesoma. Zato sklepamo, da uravnoteženo binarno drevo omogoča iskanje hitreje kot linearna drevesna struktura podatkov.