Līdzsvarots binārais koks ir pazīstams arī kā augstuma līdzsvarots koks. Tas tiek definēts kā binārs koks, ja starpība starp kreisā apakškoka un labā apakškoka augstumu nav lielāka par m, kur m parasti ir vienāds ar 1. Koka augstums ir malu skaits garākajā ceļā starp saknes mezgls un lapas mezgls.
Iepriekš minētais koks ir a binārā meklēšanas koks . Binārais meklēšanas koks ir koks, kurā katram mezglam kreisajā pusē ir zemāka vērtība nekā tā vecākmezglam, bet labajā pusē esošajam mezglam ir lielāka vērtība nekā tā vecākmezglam. Iepriekš minētajā kokā n1 ir saknes mezgls, un n4, n6, n7 ir lapu mezgli. N7 mezgls ir vistālāk no saknes mezgla. N4 un n6 satur 2 malas, un starp saknes mezglu un n7 mezglu ir trīs malas. Tā kā n7 ir vistālāk no saknes mezgla; tāpēc iepriekš minētā koka augstums ir 3.
Tagad mēs redzēsim, vai iepriekš minētais koks ir līdzsvarots vai nē. Kreisajā apakškokā ir mezgli n2, n4, n5 un n7, bet labajā apakškokā ir mezgli n3 un n6. Kreisajā apakškokā ir divi lapu mezgli, t.i., n4 un n7. Ir tikai viena mala starp mezglu n2 un n4 un divas malas starp mezgliem n7 un n2; tāpēc mezgls n7 atrodas vistālāk no saknes mezgla. Kreisā apakškoka augstums ir 2. Labajā apakškokā ir tikai viens lapas mezgls, t.i., n6, un tam ir tikai viena mala; tāpēc labā apakškoka augstums ir 1. Atšķirība starp kreisā apakškoka un labā apakškoka augstumiem ir 1. Tā kā mēs ieguvām vērtību 1, mēs varam teikt, ka augstāk minētais koks ir augstuma līdzsvarots koks. Šis augstumu starpības aprēķināšanas process jāveic katram mezglam, piemēram, n2, n3, n4, n5, n6 un n7. Apstrādājot katru mezglu, mēs atklāsim, ka k vērtība nav lielāka par 1, tāpēc mēs varam teikt, ka iepriekš minētais koks ir līdzsvarots binārais koks .
Iepriekš minētajā kokā n6, n4 un n3 ir lapu mezgli, kur n6 ir tālākais mezgls no saknes mezgla. Starp saknes mezglu un lapas mezglu pastāv trīs malas; Tāpēc augstāk minētā koka augstums ir 3. Ja par saknes mezglu uzskatām n1, tad kreisajā apakškokā ir mezgli n2, n4, n5 un n6, savukārt apakškokā ir mezgls n3. Kreisajā apakškokā n2 ir saknes mezgls, un n4 un n6 ir lapu mezgli. Starp n4 un n6 mezgliem n6 ir vistālāk no tā saknes mezgla, un n6 ir divas malas; tāpēc kreisā apakškoka augstums ir 2. Labā apakškoka kreisajā un labajā pusē ir jebkurš bērns; tāpēc labā apakškoka augstums ir 0. Tā kā kreisā apakškoka augstums ir 2 un labā apakškoka augstums ir 0, tad starpība starp kreisā apakškoka un labā apakškoka augstumu ir 2. Saskaņā ar definīciju starpība starp kreisā apakškoka un labā apakškoka augstumu nedrīkst būt lielāks par 1. Šajā gadījumā starpība ir 2, kas ir lielāka par 1; tāpēc iepriekš minētais binārais koks ir nelīdzsvarots binārais meklēšanas koks.
Kāpēc mums ir nepieciešams līdzsvarots binārais koks?
Izpratīsim vajadzību pēc līdzsvarota bināra koka, izmantojot piemēru.
Iepriekš minētais koks ir binārs meklēšanas koks, jo visi kreisie apakškoka mezgli ir mazāki par tā vecākmezglu un visi labie apakškoka mezgli ir lielāki par tā vecākmezglu. Pieņemsim, ka mēs vēlamies iepriekš minētajā kokā atrast vērtību 79. Pirmkārt, mēs salīdzinām mezgla n1 vērtību ar 79; tā kā vērtība 79 nav vienāda ar 35 un tā ir lielāka par 35, mēs pārejam uz mezglu n3, t.i., 48. Tā kā vērtība 79 nav vienāda ar 48 un 79 ir lielāka par 48, mēs pārejam pa labi 48. mazbērns. 48. mezgla labās atvases vērtība ir 79, kas ir vienāda ar meklējamo vērtību. Apiņu skaits, kas nepieciešams, lai meklētu elementu 79, ir 2, un maksimālais apiņu skaits, kas nepieciešams, lai meklētu jebkuru elementu, ir 2. Vidējais gadījums elementa meklēšanai ir O(logn).
Iepriekš minētais koks ir arī binārs meklēšanas koks, jo visi kreisie apakškoka mezgli ir mazāki par tā vecākmezglu un visi labie apakškoka mezgli ir lielāki par tā vecākmezglu. Pieņemsim, ka mēs vēlamies atrast vērtību 79 iepriekš minētajā kokā. Pirmkārt, mēs salīdzinām vērtību 79 ar mezglu n4, t.i., 13. Tā kā vērtība 79 ir lielāka par 13, mēs pārejam uz 13. mezgla labo atvasinājumu, t.i., n2 (21). Mezgla n2 vērtība ir 21, kas ir mazāka par 79, tāpēc mēs atkal virzāmies pa labi no mezgla 21. Mezgla 21 labā atvasinātā vērtība ir 29. Tā kā vērtība 79 ir lielāka par 29, mēs virzāmies pa labi. 29. mezgla bērns. 29. mezgla labā bērna vērtība ir 35, kas ir mazāka par 79, tāpēc mēs pārejam uz 35. mezgla labo atvasināto vērtību, t.i., 48. Vērtība 79 ir lielāka par 48, tāpēc mēs pārejam uz labo bērnu. 48. mezgla labā pakārtotā mezgla vērtība ir 79, kas ir vienāda ar meklējamo vērtību. Šajā gadījumā elementa meklēšanai nepieciešamais apiņu skaits ir 5. Šajā gadījumā sliktākais gadījums ir O(n).
Ja mezglu skaits palielinās, koka diagrammā1 izmantotā formula ir efektīvāka nekā koka diagrammā2 izmantotā formula. Pieņemsim, ka abos augšējos kokos pieejamo mezglu skaits ir 100 000. Lai meklētu jebkuru elementu koka diagrammā2, laiks ir nepieciešams 100 000 µs, bet laiks, kas nepieciešams, lai meklētu elementu koka diagrammā, ir log(100 000), kas ir vienāds ar 16,6 µs. Mēs varam novērot milzīgo laika atšķirību starp diviem iepriekšminētajiem kokiem. Līdz ar to secinām, ka bilances binārais koks nodrošina ātrāku meklēšanu nekā lineārā koka datu struktūra.