06.1 Vyhledávací strom
$$
\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}}
$$
# Binární vyhledávací strom
- BVS je binární strom, v jehož každém vrcholu $v$ je uložen klíč $k(v)$ a pro jehož každý vrchol $v$ platí:
- Pokud $a \in L(v)$, pak $k(a) \lt k(v)$
- Pokud $b \in R(v)$, pak $k(b) \gt k(v)$
# BVSSHow(v)
- Výpis vzestupně uspořádaných klíčů nějakého BVS $T(v)$
- InOrder průchod
- Složitost: $O(|T(v)|)$
# BVSMin(v)
- Nalezení vrcholu s nejmenším klíčem
- V poli vrcholů vygenerovaných pomocí InOrder průchodu je to ten nejvíce vlevo
- Složitost: $O($hloubka stromu/počet hladin$)$
- Složitost $O(h(T(v)))$
# BVSPred(v, w)
- Klíč předchůdce prvku $w$ v $T(v)$ (v InOrder je to levý soused $k(w)$)
- Pokud má $w$ v $T(v)$ levý podstrom $L(w)$, pak je předchůdce $w$ jeho maximem
- Jinak je předchůdcem $w$ první předek, do kterého vstoupíme zprava při průchodu nahoru
# BVSSucc(v, w)
- Analogicky s BVSPred()
# BVSFind(v, x)
- $v$ - pointer na kořen
- $x$ - co hledáme
- Rekurzivní zanoření vlevo nebo vpravo a znovu BVSFInd()
- Složitost $O(h(T(v)))$
# BVSInsert(v, x)
- Něco jako BVSFind(), ale pokud prvek nenajdeme, vložíme ho na danou pozici
- Složitost $O(h(T(v)))$
# BVSDelete(v, x)
- Nejdříve BVSFind()
- List triviální
- Vrchol s jedním listem - vyměnit za list
- Vrchol s více potomky - vyměnit za maximu z levého stromu nebo minimum z pravého stromu
- Složitost $O(h(T(v)))$
# BVSBuild($x_{1}\dots x_{2}$) na dokonale vyvážený
- if n == 1
- return x_1
- v = $x \ceil{n/2}$
- L(v) = BVSBuild(x_1 … x n/2 -1)
- R(v) = BVSBuild(x n/2 +1 … x_n)