Ett balanserat binärt träd är också känt som höjdbalanserat träd. Det definieras som binärt träd när skillnaden mellan höjden på det vänstra underträdet och det högra underträdet inte är mer än m, där m vanligtvis är lika med 1. Höjden på ett träd är antalet kanter på den längsta vägen mellan rotnod och lövnoden.
Ovanstående träd är en binärt sökträd . Ett binärt sökträd är ett träd där varje nod på vänster sida har ett lägre värde än sin föräldernod, och noden på höger sida har ett högre värde än sin föräldernod. I ovanstående träd är n1 en rotnod och n4, n6, n7 är lövnoderna. n7-noden är den längst bort från rotnoden. n4 och n6 innehåller 2 kanter och det finns tre kanter mellan rotnoden och n7 noden. Eftersom n7 är längst bort från rotnoden; därför är höjden på ovanstående träd 3.
Nu kommer vi att se om ovanstående träd är balanserat eller inte. Det vänstra underträdet innehåller noderna n2, n4, n5 och n7, medan det högra underträdet innehåller noderna n3 och n6. Det vänstra underträdet har två lövnoder, dvs n4 och n7. Det finns bara en kant mellan noderna n2 och n4 och två kanter mellan noderna n7 och n2; därför är nod n7 längst bort från rotnoden. Höjden på det vänstra underträdet är 2. Det högra underträdet innehåller endast en lövnod, d.v.s. n6, och har bara en kant; därför är höjden på det högra underträdet 1. Skillnaden mellan höjderna på det vänstra underträdet och det högra underträdet är 1. Eftersom vi fick värdet 1 så kan vi säga att ovanstående träd är ett höjdbalanserat träd. Denna process för att beräkna skillnaden mellan höjderna bör utföras för varje nod som n2, n3, n4, n5, n6 och n7. När vi bearbetar varje nod kommer vi att finna att värdet på k inte är mer än 1, så vi kan säga att ovanstående träd är ett balanserat binärt träd .
I ovanstående träd är n6, n4 och n3 bladnoderna, där n6 är den längst bort från rotnoden. Tre kanter finns mellan rotnoden och lövnoden; därför är höjden på ovanstående träd 3. När vi betraktar n1 som rotnoden, innehåller det vänstra underträdet noderna n2, n4, n5 och n6, medan underträdet innehåller noden n3. I det vänstra underträdet är n2 en rotnod och n4 och n6 är lövnoder. Bland n4 och n6 noder är n6 den längst bort från sin rotnod, och n6 har två kanter; därför är höjden på det vänstra underträdet 2. Det högra underträdet har vilket barn som helst till vänster och höger; därför är höjden på det högra underträdet 0. Eftersom höjden på det vänstra underträdet är 2 och det högra underträdet är 0, så är skillnaden mellan höjden på det vänstra underträdet och det högra underträdet 2. Enligt definitionen är skillnaden mellan höjden på det vänstra underträdet och det högra underträdet får inte vara större än 1. I detta fall blir skillnaden 2, vilket är större än 1; därför är ovanstående binära träd ett obalanserat binärt sökträd.
Varför behöver vi ett balanserat binärt träd?
Låt oss förstå behovet av ett balanserat binärt träd genom ett exempel.
Ovanstående träd är ett binärt sökträd eftersom alla de vänstra underträdnoderna är mindre än dess föräldernod och alla de högra underträdnoderna är större än dess föräldernod. Anta att vi vill hitta värdet 79 i trädet ovan. Först jämför vi värdet på nod n1 med 79; eftersom värdet på 79 inte är lika med 35 och det är större än 35 så flyttar vi till noden n3, dvs 48. Eftersom värdet 79 inte är lika med 48 och 79 är större än 48 så flyttar vi till höger barn av 48. Värdet på rätt barn i nod 48 är 79 vilket är lika med värdet som ska sökas. Antalet hopp som krävs för att söka efter ett element 79 är 2 och det maximala antalet hopp som krävs för att söka efter ett element är 2. Det genomsnittliga fallet för att söka efter ett element är O(logn).
Ovanstående träd är också ett binärt sökträd eftersom alla de vänstra subträdnoderna är mindre än dess föräldernod och alla de högra subträdnoderna är större än dess föräldernod. Antag att vi vill hitta värdet 79 i trädet ovan. Först jämför vi värdet 79 med en nod n4, d.v.s. 13. Eftersom värdet 79 är större än 13 så går vi till höger underordnad av nod 13, dvs. n2 (21). Värdet på noden n2 är 21 vilket är mindre än 79, så vi flyttar återigen till höger om nod 21. Värdet på höger underordnat till nod 21 är 29. Eftersom värdet 79 är större än 29 så flyttar vi till höger barn till nod 29. Värdet på höger underordnat till nod 29 är 35 vilket är mindre än 79 så vi flyttar till höger barn till nod 35, dvs 48. Värdet 79 är större än 48, så vi flyttar till rätt barn av nod 48. Värdet för höger underordnad nod på 48 är 79 vilket är lika med värdet som ska sökas. I det här fallet är antalet hopp som krävs för att söka efter ett element 5. I det här fallet är det värsta fallet O(n).
Om antalet noder ökar är formeln som används i träddiagrammet1 mer effektiv än formeln som används i träddiagrammet2. Anta att antalet tillgängliga noder i båda ovanstående träd är 100 000. För att söka i ett element i ett träddiagram2 är tiden det tar 100 000 µs medan tiden det tar att söka efter ett element i ett träddiagram är log(100 000) vilket är lika med 16,6 µs. Vi kan observera den enorma skillnaden i tid mellan ovanstående två träd. Därför drar vi slutsatsen att det binära balansträdet ger sökning snabbare än linjär träddatastruktur.