06.2 Vyváženost BVS
$$
\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}}
$$
Vyváženost BVS
BVS nazveme dokonale vyvážený, pokud pro každý jeho vrchol $u$ platí:
- $||L(u)|-|R(u)||\le 1$
Dokonale vyvážený BVS o velikost $n$ má $1+\floor{\log{n}}$ hladin a operace Find, Min, Insert, Delete mají složitost $O(\log n)$
Pokud má BVS zůstat po Insertu a Deletu vyvážený, nemohou být nikdy Insert a Delete rychlé
- Buď rychlý Insert a pomalý Delete
- nebo rychlý Delete a pomalý insert
Pro tvorbu vyváženého BVS nejdříve setřídíme vstupní pole, pomocí binárního dělení vkládáme prostřední prvek