A kiegyensúlyozott bináris fát magassági kiegyensúlyozott fának is nevezik. Bináris faként definiálható, ha a bal oldali részfa és a jobb oldali részfa magassága közötti különbség nem nagyobb m-nél, ahol m általában egyenlő 1-gyel. Egy fa magassága az élek száma a leghosszabb út között gyökércsomópont és levélcsomópont.
A fenti fa a bináris keresőfa . A bináris keresési fa olyan fa, amelyben a bal oldali csomópontok értéke alacsonyabb, mint a szülőcsomópontja, a jobb oldali csomópont pedig magasabb, mint a szülőcsomópontja. A fenti fában n1 gyökércsomópont, n4, n6, n7 pedig levélcsomópont. Az n7 csomópont a legtávolabbi csomópont a gyökércsomóponttól. Az n4 és n6 két élt tartalmaz, és három él van a gyökércsomópont és az n7 csomópont között. Mivel az n7 van a legtávolabb a gyökércsomóponttól; ezért a fenti fa magassága 3.
Most meglátjuk, hogy a fenti fa kiegyensúlyozott-e vagy sem. A bal oldali részfa az n2, n4, n5 és n7 csomópontokat, míg a jobb oldali részfa az n3 és n6 csomópontokat tartalmazza. A bal oldali részfának két levélcsomópontja van, azaz n4 és n7. Csak egy él van az n2 és n4 csomópontok között, és két él az n7 és n2 csomópontok között; ezért az n7 csomópont van a legtávolabb a gyökércsomóponttól. A bal oldali részfa magassága 2. A jobb oldali részfa csak egy levélcsomópontot tartalmaz, azaz n6, és csak egy éle van; ezért a jobb oldali részfa magassága 1. A bal oldali részfa és a jobb oldali részfa magassága közötti különbség 1. Mivel az 1 értéket kaptuk, így azt mondhatjuk, hogy a fenti fa magasságkiegyenlített fa. A magasságok közötti különbség kiszámításának ezt a folyamatát minden egyes csomópontra, például n2, n3, n4, n5, n6 és n7 esetén el kell végezni. Az egyes csomópontok feldolgozásakor azt találjuk, hogy k értéke nem nagyobb 1-nél, tehát azt mondhatjuk, hogy a fenti fa egy kiegyensúlyozott bináris fa .
A fenti fában n6, n4 és n3 a levél csomópontjai, ahol n6 a gyökércsomóponttól legtávolabbi csomópont. Három él van a gyökércsomópont és a levélcsomópont között; ezért a fenti fa magassága 3. Ha n1-et tekintünk gyökércsomópontnak, akkor a bal oldali részfa tartalmazza az n2, n4, n5 és n6 csomópontokat, míg a részfa az n3 csomópontot. A bal oldali részfában n2 gyökércsomópont, n4 és n6 pedig levélcsomópont. Az n4 és n6 csomópontok közül az n6 a legtávolabbi csomópont a gyökércsomópontjától, és az n6-nak két éle van; ezért a bal oldali részfa magassága 2. A jobb oldali részfa bal és jobb oldalán van gyermek; ezért a jobb oldali részfa magassága 0. Mivel a bal oldali részfa magassága 2, a jobb oldali részfa magassága 0, így a bal oldali részfa és a jobb oldali részfa magassága közötti különbség 2. A definíció szerint a különbség a bal oldali részfa és a jobb oldali részfa magassága között nem lehet nagyobb 1-nél. Ebben az esetben a különbség 2, ami nagyobb, mint 1; ezért a fenti bináris fa egy kiegyensúlyozatlan bináris keresőfa.
Miért van szükségünk kiegyensúlyozott bináris fára?
Értsük meg egy kiegyensúlyozott bináris fa szükségességét egy példán keresztül.
A fenti fa egy bináris keresési fa, mivel az összes bal oldali részfa csomópontja kisebb, mint a szülőcsomópont, és a jobb oldali részfa csomópontjai nagyobbak a szülőcsomópontnál. Tegyük fel, hogy meg akarjuk találni a 79-es értéket a fenti fában. Először is összehasonlítjuk az n1 csomópont értékét 79-el; mivel a 79 értéke nem egyenlő 35-tel, és nagyobb, mint 35, így az n3 csomópontra lépünk, azaz a 48-ra. Mivel a 79 érték nem egyenlő 48-cal, a 79 pedig nagyobb, mint 48, ezért jobbra haladunk 48 gyermeke. A 48 csomópont jobb gyermekének értéke 79, amely megegyezik a keresendő értékkel. A 79 elem kereséséhez szükséges ugrások száma 2, és bármely elem kereséséhez szükséges ugrások maximális száma 2. Az elem keresésének átlagos esete O(logn).
A fenti fa egy bináris keresési fa is, mivel az összes bal oldali részfa csomópontja kisebb, mint a szülőcsomópont, és a jobb részfa összes csomópontja nagyobb, mint a szülőcsomópont. Tegyük fel, hogy meg akarjuk találni a 79-es értéket a fenti fában. Először a 79-es értéket hasonlítjuk össze egy n4, azaz 13-as csomóponttal. Mivel a 79-es érték nagyobb, mint 13, így a 13-as csomópont jobb gyermekére lépünk, azaz az n2-re (21). Az n2 csomópont értéke 21, ami kisebb, mint 79, ezért ismét a 21-es csomópont jobbjára lépünk. A 21-es csomópont jobb gyermekének értéke 29. Mivel a 79-es érték nagyobb, mint 29, így jobbra lépünk. a 29. csomópont gyermeke. A 29. csomópont jobb gyermekének értéke 35, ami kisebb, mint 79, így a 35. csomópont jobb gyermekéhez, azaz a 48-hoz lépünk. A 79. érték nagyobb, mint 48, tehát a megfelelő gyermekhez lépünk A 48-as jobb gyermekcsomópont értéke 79, amely megegyezik a keresendő értékkel. Ebben az esetben egy elem kereséséhez szükséges ugrások száma 5. Ebben az esetben a legrosszabb eset O(n).
Ha a csomópontok száma nő, akkor a fadiagramban1 használt képlet hatékonyabb, mint a fadiagramban2 használt képlet. Tegyük fel, hogy mindkét fenti fában elérhető csomópontok száma 100 000. A fadiagramban2 bármely elem megkereséséhez az idő 100 000 µs, míg a fadiagramban egy elem keresése log(100 000), ami 16,6 µs. Megfigyelhetjük a hatalmas időbeli különbséget két fenti fa között. Ezért arra a következtetésre jutottunk, hogy a mérleg bináris fa gyorsabb keresést biztosít, mint a lineáris fa adatstruktúra.