Een gebalanceerde binaire boom wordt ook wel een in hoogte gebalanceerde boom genoemd. Het wordt gedefinieerd als een binaire boom wanneer het verschil tussen de hoogte van de linker deelboom en de rechter deelboom niet groter is dan m, waarbij m gewoonlijk gelijk is aan 1. De hoogte van een boom is het aantal randen op het langste pad tussen de wortelknooppunt en het bladknooppunt.
De bovenstaande boom is een binaire zoekboom . Een binaire zoekboom is een boom waarin elk knooppunt aan de linkerkant een lagere waarde heeft dan het bovenliggende knooppunt, en het knooppunt aan de rechterkant een hogere waarde heeft dan het bovenliggende knooppunt. In de bovenstaande boom is n1 een wortelknooppunt, en n4, n6, n7 zijn de bladknooppunten. Het n7-knooppunt is het verste knooppunt van het hoofdknooppunt. De n4 en n6 bevatten twee randen en er zijn drie randen tussen het hoofdknooppunt en het n7-knooppunt. Omdat n7 het verst verwijderd is van het hoofdknooppunt; daarom is de hoogte van de bovenstaande boom 3.
Nu zullen we zien of de bovenstaande boom in balans is of niet. De linker deelboom bevat de knooppunten n2, n4, n5 en n7, terwijl de rechter deelboom de knooppunten n3 en n6 bevat. De linker subboom heeft twee bladknooppunten, namelijk n4 en n7. Er is slechts één rand tussen de knooppunten n2 en n4 en twee randen tussen de knooppunten n7 en n2; daarom bevindt knooppunt n7 zich het verst van het hoofdknooppunt. De hoogte van de linker deelboom is 2. De rechter deelboom bevat slechts één bladknooppunt, d.w.z. n6, en heeft slechts één rand; daarom is de hoogte van de rechter deelboom 1. Het verschil tussen de hoogten van de linker deelboom en de rechter deelboom is 1. Omdat we de waarde 1 hebben gekregen, kunnen we zeggen dat de bovenstaande boom een in hoogte gebalanceerde boom is. Dit proces van het berekenen van het verschil tussen de hoogten moet worden uitgevoerd voor elk knooppunt zoals n2, n3, n4, n5, n6 en n7. Wanneer we elk knooppunt verwerken, zullen we ontdekken dat de waarde van k niet meer dan 1 is, dus we kunnen zeggen dat de bovenstaande boom een gebalanceerde boom is. binaire boom .
In de bovenstaande boom zijn n6, n4 en n3 de bladknooppunten, waarbij n6 het verste knooppunt is vanaf het wortelknooppunt. Er zijn drie randen tussen het wortelknooppunt en het bladknooppunt; daarom is de hoogte van de bovenstaande boom 3. Als we n1 als het hoofdknooppunt beschouwen, bevat de linker subboom de knooppunten n2, n4, n5 en n6, terwijl de subboom het knooppunt n3 bevat. In de linker subboom is n2 een hoofdknooppunt en zijn n4 en n6 bladknooppunten. Van de n4- en n6-knooppunten is n6 het knooppunt dat het verst verwijderd is van het hoofdknooppunt, en heeft n6 twee randen; daarom is de hoogte van de linker deelboom 2. De rechter deelboom heeft links en rechts een kind; daarom is de hoogte van de rechter subboom 0. Omdat de hoogte van de linker subboom 2 is en de rechter subboom 0, is het verschil tussen de hoogte van de linker subboom en de rechter subboom 2. Volgens de definitie is het verschil tussen de hoogte van de linker subboom en de rechter subboom mag niet groter zijn dan 1. In dit geval wordt het verschil 2, wat groter is dan 1; daarom is de bovenstaande binaire boom een ongebalanceerde binaire zoekboom.
Waarom hebben we een gebalanceerde binaire boom nodig?
Laten we aan de hand van een voorbeeld de noodzaak van een gebalanceerde binaire boom begrijpen.
De bovenstaande boom is een binaire zoekboom omdat alle knooppunten van de linker subboom kleiner zijn dan het bovenliggende knooppunt en alle rechter subboomknooppunten groter zijn dan het bovenliggende knooppunt. Stel dat we de waarde 79 in de bovenstaande boom willen vinden. Eerst vergelijken we de waarde van knooppunt n1 met 79; omdat de waarde van 79 niet gelijk is aan 35 en groter is dan 35, gaan we naar knooppunt n3, d.w.z. 48. Omdat de waarde 79 niet gelijk is aan 48 en 79 groter is dan 48, gaan we naar rechts kind van 48. De waarde van het rechter kind van knooppunt 48 is 79, wat gelijk is aan de te zoeken waarde. Het aantal hops dat nodig is om een element 79 te doorzoeken is 2 en het maximale aantal hops dat nodig is om een element te doorzoeken is 2. Het gemiddelde geval om een element te doorzoeken is O(logn).
De bovenstaande boom is ook een binaire zoekboom omdat alle knooppunten van de linker subboom kleiner zijn dan het bovenliggende knooppunt en alle rechter subboomknooppunten groter zijn dan het bovenliggende knooppunt. Stel dat we de waarde 79 in de bovenstaande boom willen vinden. Eerst vergelijken we de waarde 79 met een knooppunt n4, d.w.z. 13. Omdat de waarde 79 groter is dan 13, gaan we naar het rechterkind van knooppunt 13, d.w.z. n2 (21). De waarde van knooppunt n2 is 21, wat kleiner is dan 79, dus we gaan opnieuw naar de rechterkant van knooppunt 21. De waarde van het rechterkind van knooppunt 21 is 29. Omdat de waarde 79 groter is dan 29, gaan we naar rechts kind van knooppunt 29. De waarde van het rechterkind van knooppunt 29 is 35, wat kleiner is dan 79, dus we gaan naar het rechterkind van knooppunt 35, dat wil zeggen 48. De waarde 79 is groter dan 48, dus we gaan naar het rechterkind van knooppunt 48. De waarde van het rechter kindknooppunt van 48 is 79, wat gelijk is aan de waarde die moet worden gezocht. In dit geval is het aantal hops dat nodig is om een element te zoeken 5. In dit geval is het ergste geval O(n).
Als het aantal knooppunten toeneemt, is de formule die in boomdiagram1 wordt gebruikt efficiënter dan de formule die in boomdiagram2 wordt gebruikt. Stel dat het aantal beschikbare knooppunten in beide bovenstaande bomen 100.000 is. Om een element in een boomdiagram2 te doorzoeken, is de benodigde tijd 100.000 µs, terwijl de tijd die nodig is om een element in een boomdiagram te zoeken log(100.000) is, wat gelijk is aan 16,6 µs. We kunnen het enorme tijdsverschil tussen bovenstaande twee bomen waarnemen. Daarom concluderen we dat de binaire balansboom sneller kan zoeken dan de lineaire boomdatastructuur.