Binární vyhledávací strom
Binární vyhledávací strom je interaktivní pokus z aplikace Datové struktury, bezplatné simulace ze StudyFi Lab, která běží přímo v prohlížeči.
V každém uzlu platí: vlevo jsou menší hodnoty, vpravo větší. Hledání i vkládání proto jde jen jednou cestou od kořene a trvá O(h), kde h je výška stromu — u vyváženého stromu h ≈ log₂ n. Mazání má tři případy: list prostě zmizí, uzel s jedním potomkem nahradí jeho potomek a uzel se dvěma potomky převezme hodnotu in-order následníka. Průchod in-order vypíše hodnoty seřazené; podobné stromy pohánějí databázové indexy.
Vyzkoušej: Smaž kořen — má dva potomky, takže uvidíš hledání následníka. Pak zkus „Vložit seřazené hodnoty“: strom se zvrhne v seznam a výška vzroste na n.
Časté otázky
Co ukazuje pokus „Binární vyhledávací strom“?
V každém uzlu platí: vlevo jsou menší hodnoty, vpravo větší. Hledání i vkládání proto jde jen jednou cestou od kořene a trvá O(h), kde h je výška stromu — u vyváženého stromu h ≈ log₂ n. Mazání má tři případy: list prostě zmizí, uzel s jedním potomkem nahradí jeho potomek a uzel se dvěma potomky převezme hodnotu in-order následníka. Průchod in-order vypíše hodnoty seřazené; podobné stromy pohánějí databázové indexy.
Jak si vyzkoušet „Binární vyhledávací strom“?
Smaž kořen — má dva potomky, takže uvidíš hledání následníka. Pak zkus „Vložit seřazené hodnoty“: strom se zvrhne v seznam a výška vzroste na n.
Učíš se na test?
Nahraj svoje zápisky a StudyFi z nich udělá kartičky, testy a podcasty.