06.3 AVL stromy
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# AVL Stromy
- Skoro jako BVS, ale né úplně dokonale vyvážený (je hloubkově vyvážený)
- BVS je AVL stromem, pokud pro každý jeho vrchol platí:
- $||h(L(u))|-|h(R(u))||\le 1$
- AVL strom s $n$ vrcholy má složitost $\Theta(\log{n})$
- Hloubka stromu $n$ vrcholy má hloubku $\Theta(\log{n})$
# AVLInsert()
- U každého vrcholu ukládám informaci o hloubkách jeho podstromů (tzv. znaménko)
- $\delta(v) = h(r(v)) - (h(l(v)))$
- Jakmile narazíme na jiné znaménko, provádíme rotace
- Vložíme jako list se znaménkem 0
- Přepočítat hloubky na cestě z rodiče do kořene, případně řešit rotací
- Propagovat nahoru
# AVLDelete()
- Podobně jako AVLInsert()
- Místo informace o prohloubení propagujeme info o změlčení