Et balansert binært tre er også kjent som høydebalansert tre. Det er definert som binært tre når forskjellen mellom høyden på venstre undertre og høyre undertre ikke er mer enn m, hvor m vanligvis er lik 1. Høyden på et tre er antall kanter på den lengste banen mellom rotnoden og bladnoden.
Treet ovenfor er en binært søketre . Et binært søketre er et tre der hver node på venstre side har en lavere verdi enn sin overordnede node, og noden på høyre side har en høyere verdi enn sin overordnede node. I treet ovenfor er n1 en rotnode, og n4, n6, n7 er bladnodene. n7-noden er den lengste noden fra rotnoden. n4 og n6 inneholder 2 kanter og det finnes tre kanter mellom rotnoden og n7-noden. Siden n7 er lengst fra rotnoden; derfor er høyden på treet ovenfor 3.
Nå vil vi se om treet ovenfor er balansert eller ikke. Det venstre undertreet inneholder nodene n2, n4, n5 og n7, mens det høyre undertreet inneholder nodene n3 og n6. Det venstre undertreet har to bladnoder, dvs. n4 og n7. Det er bare én kant mellom noden n2 og n4 og to kanter mellom nodene n7 og n2; derfor er node n7 lengst unna rotnoden. Høyden på det venstre undertreet er 2. Det høyre undertreet inneholder kun én bladnode, dvs. n6, og har kun én kant; derfor er høyden på høyre undertre 1. Forskjellen mellom høydene på venstre undertre og høyre undertre er 1. Siden vi fikk verdien 1 så kan vi si at treet ovenfor er et høydebalansert tre. Denne prosessen med å beregne forskjellen mellom høydene bør utføres for hver node som n2, n3, n4, n5, n6 og n7. Når vi behandler hver node, vil vi finne at verdien av k ikke er mer enn 1, så vi kan si at treet ovenfor er en balansert binært tre .
I treet ovenfor er n6, n4 og n3 bladnodene, der n6 er den lengste noden fra rotnoden. Tre kanter eksisterer mellom rotnoden og bladnoden; derfor er høyden på treet ovenfor 3. Når vi betrakter n1 som rotnoden, inneholder det venstre undertreet nodene n2, n4, n5 og n6, mens undertreet inneholder noden n3. I det venstre undertreet er n2 en rotnode, og n4 og n6 er bladnoder. Blant n4 og n6 noder er n6 den fjerneste noden fra rotnoden, og n6 har to kanter; derfor er høyden på venstre undertre 2. Høyre undertre har et hvilket som helst barn på venstre og høyre side; derfor er høyden på høyre undertre 0. Siden høyden på venstre undertre er 2 og høyre undertre er 0, så er forskjellen mellom høyden på venstre undertre og høyre undertre 2. I følge definisjonen er forskjellen mellom høyden på venstre undertre og høyre undertre må ikke være større enn 1. I dette tilfellet blir forskjellen 2, som er større enn 1; derfor er det ovennevnte binære treet et ubalansert binært søketre.
Hvorfor trenger vi et balansert binært tre?
La oss forstå behovet for et balansert binært tre gjennom et eksempel.
Treet ovenfor er et binært søketre fordi alle de venstre undertrenodene er mindre enn dens overordnede node og alle de høyre undertreenodene er større enn dens overordnede noden. Anta at vi ønsker å finne verdien 79 i treet ovenfor. Først sammenligner vi verdien av node n1 med 79; siden verdien av 79 ikke er lik 35 og den er større enn 35 så flytter vi til noden n3, dvs. 48. Siden verdien 79 ikke er lik 48 og 79 er større enn 48, så flytter vi til høyre barn på 48. Verdien til det riktige barnet til node 48 er 79 som er lik verdien som skal søkes. Antall hopp som kreves for å søke i et element 79 er 2 og det maksimale antallet hopp som kreves for å søke i et element er 2. Gjennomsnittlig tilfelle for å søke i et element er O(logn).
java trimstreng
Treet ovenfor er også et binært søketre fordi alle de venstre undertrenodene er mindre enn dens overordnede node og alle de høyre undertrenodene er større enn dens overordnede noden. Anta at vi ønsker å finne funnet verdien 79 i treet ovenfor. Først sammenligner vi verdien 79 med en node n4, dvs. 13. Siden verdien 79 er større enn 13 så flytter vi til høyre underordnede av node 13, dvs. n2 (21). Verdien av noden n2 er 21 som er mindre enn 79, så vi flytter igjen til høyre for node 21. Verdien til høyre underordnet til node 21 er 29. Siden verdien 79 er større enn 29 så flytter vi til høyre barn til node 29. Verdien av høyre barn til node 29 er 35, som er mindre enn 79, så vi flytter til høyre barn til node 35, dvs. 48. Verdien 79 er større enn 48, så vi flytter til høyre barn av node 48. Verdien av høyre barnenode på 48 er 79 som er lik verdien som skal søkes. I dette tilfellet er antallet hopp som kreves for å søke i et element 5. I dette tilfellet er det verste tilfellet O(n).
Hvis antall noder øker, er formelen brukt i trediagrammet1 mer effektiv enn formelen brukt i trediagrammet2. Anta at antallet noder tilgjengelig i begge trærne ovenfor er 100 000. For å søke i et element i et trediagram2, er tiden det tar 100 000 µs, mens tiden det tar å søke i et element i et trediagram er log(100 000) som er lik 16,6 µs. Vi kan observere den enorme forskjellen i tid mellom de to overstående trærne. Derfor konkluderer vi med at balansebinærtreet gir søk raskere enn lineær tredatastruktur.