Ett binärt träd är balanserat om trädets höjd är O(Log n) där n är antalet noder. Till exempel bibehåller AVL-trädet O(Log n)-höjden genom att se till att skillnaden mellan höjderna på vänster och höger underträd är högst 1. Röd-svarta träd bibehåller O(Log n)-höjden genom att se till att antalet av svarta noder på varje rot-till-blad-bana är densamma och att det inte finns några intilliggande röda noder. Balanced Binary Search-träd är prestandamässigt bra eftersom de ger O(log n) tid för sökning, infoga och radering.
Ett balanserat binärt träd är ett binärt träd som följer de tre villkoren:
- Höjden på vänster och höger träd för någon nod skiljer sig inte med mer än 1.
- Det vänstra underträdet för den noden är också balanserat.
- Det högra underträdet för den noden är också balanserat.
En enda nod är alltid balanserad. Det kallas också för ett höjdbalanserat binärt träd.
Exempel :
Balanserat och obalanserat binärt träd
Det är en typ av binärt träd där skillnaden mellan höjden på det vänstra och det högra underträdet för varje nod är antingen 0 eller 1. I figuren ovan är rotnoden med värdet 0 obalanserad med ett djup på 2 enheter .
Tillämpning av Balanced Binary Tree:
- AVL-träd
- Röd svart träd
- Balanserat binärt sökträd
Fördelar med Balanced Binary Tree:
- Icke-destruktiva uppdateringar stöds av ett balanserat binärt träd med samma asymptotiska effektivitet.
- Områdesfrågor och iteration i rätt sekvens görs möjliga av det balanserade binära trädet.