Binárny vyhľadávací strom
Binárny vyhľadávací strom je interaktívny pokus z aplikácie Dátové štruktúry, bezplatnej simulácie zo StudyFi Lab, ktorá beží priamo v prehliadači.
V každom uzle platí: vľavo sú menšie hodnoty, vpravo väčšie. Hľadanie aj vkladanie preto ide iba jednou cestou od koreňa a trvá O(h), kde h je výška stromu — pri vyváženom strome h ≈ log₂ n. Mazanie má tri prípady: list jednoducho zmizne, uzol s jedným potomkom nahradí jeho potomok a uzol s dvoma potomkami prevezme hodnotu in-order nasledovníka. Prechod in-order vypíše hodnoty zoradené; podobné stromy poháňajú databázové indexy.
Vyskúšaj: Zmaž koreň — má dvoch potomkov, takže uvidíš hľadanie nasledovníka. Potom skús „Vložiť zoradené hodnoty“: strom sa zvrhne na zoznam a výška narastie na n.
Časté otázky
Čo ukazuje pokus „Binárny vyhľadávací strom“?
V každom uzle platí: vľavo sú menšie hodnoty, vpravo väčšie. Hľadanie aj vkladanie preto ide iba jednou cestou od koreňa a trvá O(h), kde h je výška stromu — pri vyváženom strome h ≈ log₂ n. Mazanie má tri prípady: list jednoducho zmizne, uzol s jedným potomkom nahradí jeho potomok a uzol s dvoma potomkami prevezme hodnotu in-order nasledovníka. Prechod in-order vypíše hodnoty zoradené; podobné stromy poháňajú databázové indexy.
Ako si vyskúšať „Binárny vyhľadávací strom“?
Zmaž koreň — má dvoch potomkov, takže uvidíš hľadanie nasledovníka. Potom skús „Vložiť zoradené hodnoty“: strom sa zvrhne na zoznam a výška narastie na n.
Učíš sa na test?
Nahraj svoje poznámky a StudyFi z nich urobí kartičky, testy a podcasty.