Binární strom je vyvážený, pokud je výška stromu O(Log n), kde n je počet uzlů. Strom AVL si například zachovává výšku O(Log n) tím, že se ujistí, že rozdíl mezi výškami levého a pravého podstromu je maximálně 1. Červeno-černé stromy si udržují výšku O(Log n) tím, že zajistí, aby číslo Počet černých uzlů na každé cestě od kořene k listu je stejný a že zde nejsou žádné sousední červené uzly. Stromy vyváženého binárního vyhledávání jsou z hlediska výkonu dobré, protože poskytují čas O(log n) pro vyhledávání, vkládání a mazání.

Vyvážený binární strom je binární strom, který splňuje 3 podmínky:

• Výška levého a pravého stromu pro žádný uzel se neliší o více než 1.
• Levý podstrom tohoto uzlu je také vyvážený.
• Pravý podstrom tohoto uzlu je také vyvážený.

Jeden uzel je vždy vyvážený. Bývá také označován jako výškově vyvážený binární strom.

Příklad :

Vyvážený a nevyvážený binární strom

Je to typ binárního stromu, ve kterém je rozdíl mezi výškou levého a pravého podstromu pro každý uzel buď 0 nebo 1. Na obrázku výše je kořenový uzel s hodnotou 0 nevyvážený s hloubkou 2 jednotek .

Aplikace vyváženého binárního stromu:

• AVL stromy
• Červený černý strom
• Vyvážený binární vyhledávací strom

Výhody vyváženého binárního stromu:

• Nedestruktivní aktualizace jsou podporovány vyváženým binárním stromem se stejnou asymptotickou účinností.
• Dotazy na rozsah a iterace ve správném pořadí jsou proveditelné díky vyváženému binárnímu stromu.