Definujte binární strom. Definujte binární vyhledávací strom a popište v něm operace nalezení prvku, následníka a předchůdce a jejich časové složitosti.
Binární strom
- Zakořeněný acyklický souvislý graf, kde každý vrchol má nanejvýš dva potomky
Sousedy vrcholu v označujeme:
- předchůdce = p(v)
- levý potomek = l(v)
- pravý potomek = p(v)
Binární vyhledávací strom (BST)
uspořádaný binární strom, kde pro potomky každého vrcholu v platí:
- pokud libovolný vrchol l naleží levému podstromu vrcholu v ⇒ k(l) < k(v)
- pokud libivolný vrchol p naleží pravému podstromu vrcholu v ⇒ k(p) > k(v)