Tasapainoinen binääripuu tunnetaan myös korkeudeltaan tasapainoisena puuna. Se määritellään binääripuuksi, kun vasemman alipuun ja oikean alipuun korkeusero on enintään m, missä m on yleensä yhtä suuri kuin 1. Puun korkeus on reunojen lukumäärä pisimmällä polulla alipuun välillä. juurisolmu ja lehtisolmu.
Yllä oleva puu on a binäärihakupuu . Binäärihakupuu on puu, jossa jokaisella vasemmanpuoleisella solmulla on pienempi arvo kuin sen pääsolmulla ja oikeanpuoleisella solmulla on suurempi arvo kuin sen pääsolmulla. Yllä olevassa puussa n1 on juurisolmu ja n4, n6, n7 ovat lehtisolmuja. N7-solmu on kauimpana juurisolmusta. N4 ja n6 sisältävät 2 reunaa ja juurisolmun ja n7-solmun välillä on kolme reunaa. Koska n7 on kauimpana juurisolmusta; siksi yllä olevan puun korkeus on 3.
Nyt näemme, onko yllä oleva puu tasapainossa vai ei. Vasen alipuu sisältää solmut n2, n4, n5 ja n7, kun taas oikea alipuu sisältää solmut n3 ja n6. Vasemmassa alipuussa on kaksi lehtisolmua, eli n4 ja n7. Solmujen n2 ja n4 välillä on vain yksi reuna ja solmujen n7 ja n2 välillä kaksi reunaa; siksi solmu n7 on kauimpana juurisolmusta. Vasemman alipuun korkeus on 2. Oikeassa alipuussa on vain yksi lehtisolmu, eli n6, ja sillä on vain yksi reuna; siksi oikean alipuun korkeus on 1. Vasemman alipuun ja oikean alipuun korkeuksien ero on 1. Koska saimme arvon 1, voimme sanoa, että yllä oleva puu on korkeustasapainotettu puu. Tämä korkeuksien välisen eron laskentaprosessi tulisi suorittaa jokaiselle solmulle, kuten n2, n3, n4, n5, n6 ja n7. Kun käsittelemme jokaisen solmun, huomaamme, että k:n arvo ei ole suurempi kuin 1, joten voimme sanoa, että yllä oleva puu on tasapainotettu binäärinen puu .
Yllä olevassa puussa n6, n4 ja n3 ovat lehtisolmuja, missä n6 on kauimpana juurisolmusta. Juurisolmun ja lehtisolmun välillä on kolme reunaa; Siksi yllä olevan puun korkeus on 3. Kun n1 pidetään juurisolmuna, niin vasen alipuu sisältää solmut n2, n4, n5 ja n6, kun taas alipuu sisältää solmun n3. Vasemmassa alipuussa n2 on juurisolmu ja n4 ja n6 ovat lehtisolmuja. Solmujen n4 ja n6 joukossa n6 on kauimpana juurisolmuksestaan ja n6:lla on kaksi reunaa; siksi vasemman alipuun korkeus on 2. Oikean alipuun vasemmalla ja oikealla puolella ei ole lapsia; siksi oikean alipuun korkeus on 0. Koska vasemman alipuun korkeus on 2 ja oikean alipuun korkeus on 0, niin vasemman alipuun ja oikean alipuun korkeusero on 2. Määritelmän mukaan ero vasemman alipuun ja oikean alipuun korkeuden välillä ei saa olla suurempi kuin 1. Tässä tapauksessa ero on 2, joka on suurempi kuin 1; siksi yllä oleva binääripuu on epätasapainoinen binäärihakupuu.
Miksi tarvitsemme tasapainoisen binääripuun?
Ymmärretään tasapainoisen binääripuun tarve esimerkin kautta.
Yllä oleva puu on binäärihakupuu, koska kaikki vasemmanpuoleiset alipuusolmut ovat pienempiä kuin sen pääsolmu ja kaikki oikeat alipuusolmut ovat suurempia kuin sen pääsolmu. Oletetaan, että haluamme löytää arvon 79 yllä olevasta puusta. Ensin verrataan solmun n1 arvoa 79:ään; koska arvo 79 ei ole yhtä suuri kuin 35 ja se on suurempi kuin 35, siirrymme solmuun n3, eli 48. Koska arvo 79 ei ole yhtä suuri kuin 48 ja 79 on suurempi kuin 48, siirrymme oikealle 48:n lapsi. Solmun 48 oikean lapsen arvo on 79, joka on yhtä suuri kuin haettava arvo. Elementin 79 etsimiseen vaadittava hyppyjen määrä on 2 ja minkä tahansa elementin etsimiseen vaadittavien hyppyjen enimmäismäärä on 2. Keskimääräinen tapaus elementin etsimiseen on O(logn).
Yllä oleva puu on myös binäärihakupuu, koska kaikki vasemmanpuoleiset alipuusolmut ovat pienempiä kuin sen pääsolmu ja kaikki oikeat alipuusolmut ovat suurempia kuin sen pääsolmu. Oletetaan, että haluamme löytää etsintäarvon 79 yllä olevasta puusta. Ensin verrataan arvoa 79 solmuun n4, eli 13. Koska arvo 79 on suurempi kuin 13, siirrymme solmun 13 oikeaan jälkeläiseen, eli n2 (21). Solmun n2 arvo on 21, joka on pienempi kuin 79, joten siirrytään jälleen solmun 21 oikealle puolelle. Solmun 21 oikean lapsen arvo on 29. Koska arvo 79 on suurempi kuin 29, siirrymme oikealle Solmun 29 lapsi. Solmun 29 oikean lapsen arvo on 35, joka on pienempi kuin 79, joten siirrymme solmun 35 oikeaan aliryhmään, eli 48. Arvo 79 on suurempi kuin 48, joten siirrymme oikeaan aliryhmään solmun 48 arvo. Oikean lapsisolmun 48 arvo on 79, joka on yhtä suuri kuin haettava arvo. Tässä tapauksessa elementin etsimiseen tarvittava hyppyjen määrä on 5. Tässä tapauksessa pahin tapaus on O(n).
Jos solmujen määrä kasvaa, puukaaviossa1 käytetty kaava on tehokkaampi kuin puukaaviossa2 käytetty kaava. Oletetaan, että molemmissa yllä olevissa puissa käytettävissä olevien solmujen määrä on 100 000. Puukaavion2 minkä tahansa elementin etsimiseen kuluva aika on 100 000 µs, kun taas elementin etsimiseen puukaaviossa kuluva aika on log(100 000), joka on 16,6 µs. Voimme havaita valtavan aikaeron kahden yllä olevan puun välillä. Tästä syystä päätämme, että tasapainobinääripuu tarjoaa haun nopeammin kuin lineaarinen puutietorakenne.