Et balanceret binært træ er også kendt som højdebalanceret træ. Det er defineret som binært træ, når forskellen mellem højden af venstre undertræ og højre undertræ ikke er mere end m, hvor m normalt er lig med 1. Højden af et træ er antallet af kanter på den længste vej mellem rodknude og bladknude.
Ovenstående træ er en binært søgetræ . Et binært søgetræ er et træ, hvor hver node på venstre side har en lavere værdi end dens overordnede node, og noden på højre side har en højere værdi end dens overordnede node. I ovenstående træ er n1 en rodknude, og n4, n6, n7 er bladknuderne. n7-knuden er den fjerneste knude fra rodknuden. n4 og n6 indeholder 2 kanter, og der findes tre kanter mellem rodknuden og n7-knuden. Da n7 er længst væk fra rodknuden; derfor er højden af ovenstående træ 3.
Nu vil vi se, om ovenstående træ er afbalanceret eller ej. Det venstre undertræ indeholder noderne n2, n4, n5 og n7, mens det højre undertræ indeholder noderne n3 og n6. Det venstre undertræ har to bladknuder, dvs. n4 og n7. Der er kun én kant mellem knudepunktet n2 og n4 og to kanter mellem knudepunkterne n7 og n2; derfor er node n7 længst væk fra rodknudepunktet. Højden af det venstre undertræ er 2. Det højre undertræ indeholder kun én bladknude, dvs. n6, og har kun én kant; derfor er højden af højre undertræ 1. Forskellen mellem højderne af venstre undertræ og højre undertræ er 1. Da vi fik værdien 1, så kan vi sige, at ovenstående træ er et højdebalanceret træ. Denne proces med at beregne forskellen mellem højderne skal udføres for hver knude som n2, n3, n4, n5, n6 og n7. Når vi behandler hver node, så vil vi opdage, at værdien af k ikke er mere end 1, så vi kan sige, at ovenstående træ er et balanceret binært træ .
I ovenstående træ er n6, n4 og n3 bladknuderne, hvor n6 er den fjerneste knude fra rodknuden. Der er tre kanter mellem rodknuden og bladknuden; derfor er højden af ovenstående træ 3. Når vi betragter n1 som rodknudepunktet, så indeholder det venstre undertræ noderne n2, n4, n5 og n6, mens undertræet indeholder knudepunktet n3. I venstre undertræ er n2 en rodknude, og n4 og n6 er bladknuder. Blandt n4 og n6 noder er n6 den fjerneste node fra sin rod node, og n6 har to kanter; derfor er højden af det venstre undertræ 2. Det højre undertræ har et hvilket som helst barn til venstre og højre; derfor er højden af højre undertræ 0. Da højden af venstre undertræ er 2 og højre undertræ er 0, så er forskellen mellem højden af venstre undertræ og højre undertræ 2. Ifølge definitionen er forskellen mellem højden af venstre undertræ og højre undertræ må ikke være større end 1. I dette tilfælde bliver forskellen 2, hvilket er større end 1; derfor er ovenstående binære træ et ubalanceret binært søgetræ.
Hvorfor har vi brug for et balanceret binært træ?
Lad os forstå behovet for et afbalanceret binært træ gennem et eksempel.
Ovenstående træ er et binært søgetræ, fordi alle de venstre undertræsknudepunkter er mindre end dens overordnede knude, og alle de højre undertræsknuder er større end dens overordnede knudepunkter. Antag, at vi ønsker at finde værdien 79 i ovenstående træ. Først sammenligner vi værdien af node n1 med 79; da værdien af 79 ikke er lig med 35 og den er større end 35, så flytter vi til noden n3, dvs. 48. Da værdien 79 ikke er lig med 48 og 79 er større end 48, så flytter vi til højre barn af 48. Værdien af det rigtige barn af node 48 er 79, hvilket er lig med den værdi, der skal søges i. Antallet af hop, der kræves for at søge et element 79, er 2, og det maksimale antal hop, der kræves for at søge et element, er 2. Den gennemsnitlige sag for at søge efter et element er O(logn).
byte array til streng java
Ovenstående træ er også et binært søgetræ, fordi alle de venstre undertræsknudepunkter er mindre end dens overordnede knude, og alle de højre undertræsknuder er større end dens overordnede knudepunkter. Antag, at vi ønsker at finde fundet værdien 79 i ovenstående træ. Først sammenligner vi værdien 79 med en node n4, dvs. 13. Da værdien 79 er større end 13, så flytter vi til højre underordnede af node 13, dvs. n2 (21). Værdien af noden n2 er 21, hvilket er mindre end 79, så vi flytter igen til højre for node 21. Værdien af højre underordnede af node 21 er 29. Da værdien 79 er større end 29, så flytter vi til højre barn af node 29. Værdien af højre barn af node 29 er 35, hvilket er mindre end 79, så vi flytter til højre barn af node 35, dvs. 48. Værdien 79 er større end 48, så vi flytter til det rigtige barn af node 48. Værdien af højre underordnede node på 48 er 79, hvilket er lig med den værdi, der skal søges i. I dette tilfælde er antallet af hop, der kræves for at søge et element, 5. I dette tilfælde er det værste tilfælde O(n).
Hvis antallet af noder stiger, er formlen i trædiagrammet1 mere effektiv end formlen i trædiagrammet2. Antag, at antallet af tilgængelige noder i begge ovenstående træer er 100.000. For at søge et hvilket som helst element i et trædiagram2, er den tid det tager 100.000 µs, mens den tid det tager at søge i et element i et trædiagram er log(100.000), hvilket er lig med 16,6 µs. Vi kan observere den enorme forskel i tid mellem ovenstående to træer. Derfor konkluderer vi, at det binære balancetræ giver søgning hurtigere end lineær trædatastruktur.