Binárny strom je vyvážený, ak je výška stromu O(Log n), kde n je počet uzlov. Napríklad strom AVL si udržiava výšku O(Log n) tým, že sa uistí, že rozdiel medzi výškami ľavého a pravého podstromu je najviac 1. Červeno-čierne stromy si udržia výšku O(Log n) tým, že sa uistí, že číslo Počet čiernych uzlov na každej ceste od koreňa k listu je rovnaký a že neexistujú žiadne susediace červené uzly. Stromy vyváženého binárneho vyhľadávania sú z hľadiska výkonu dobré, pretože poskytujú čas O(log n) na vyhľadávanie, vkladanie a mazanie.
git príkazy pre push
Vyvážený binárny strom je binárny strom, ktorý spĺňa 3 podmienky:
- Výška ľavého a pravého stromu pre žiadny uzol sa nelíši o viac ako 1.
- Ľavý podstrom tohto uzla je tiež vyvážený.
- Pravý podstrom tohto uzla je tiež vyvážený.
Jeden uzol je vždy vyvážený. Označuje sa aj ako výškovo vyvážený binárny strom.
Príklad :
Vyvážený a nevyvážený binárny strom
Je to typ binárneho stromu, v ktorom je rozdiel medzi výškou ľavého a pravého podstromu pre každý uzol buď 0 alebo 1. Na obrázku vyššie je koreňový uzol s hodnotou 0 nevyvážený s hĺbkou 2 jednotky. .
Aplikácia vyváženého binárneho stromu:
- AVL stromy
- Červený čierny strom
- Vyvážený binárny vyhľadávací strom
Výhody vyváženého binárneho stromu:
- Nedeštruktívne aktualizácie sú podporované vyváženým binárnym stromom s rovnakou asymptotickou účinnosťou.
- Dopyty na rozsah a iteráciu v správnom poradí umožňuje vyvážený binárny strom.