Skip to content

AVL Stromy

AVL Strom je výškově vyvážený [[Binární vyhledávací strom|binární vyhledávací strom]], který každému uzlu přiřazuje faktor vyváženosti $\(\Large\text{bal}(u) = h_L - h_R\)$

  • kde \(h_L\) výška levého podstromu,
  • a \(h_R\) je výška pravého podstromu

Pro všechny uzly \(u\) vyváženého stromu platí, že \(\text{bal}(u) \in \set{-1, 0, 1}\).

Rotace

[!tip] Určování vhodné rotace