Kartičky na Binární vyhledávací strom
Binární Vyhledávací Strom: Komplexní průvodce pro studenty
Klepni pro otočení · Swipni pro navigaci
Binární vyhledávací strom
29 kartiček
Kartička 1
Otázka: Co je to binární vyhledávací strom (BST) a k čemu slouží?
Odpověď: Binární vyhledávací strom je základní datová struktura pro efektivní ukládání a organizaci dat, která umožňuje rychlé vyhledávání, vkládání a mazání p
Kartička 2
Otázka: Jaká je klíčová vlastnost uspořádání hodnot v binárním vyhledávacím stromu?
Odpověď: Pro každý uzel U platí, že všechny hodnoty v levém podstromu U jsou menší než hodnota U, a všechny hodnoty v pravém podstromu U jsou větší než hodnota
Kartička 3
Otázka: Popište základní vlastnosti binárního stromu (obecně).
Odpověď: Binární strom je hierarchická datová struktura, kde každý uzel může mít nejvýše dva potomky (levý a pravý). Uzel bez potomků je list, uzel bez rodiče
Kartička 4
Otázka: Jak probíhá operace hledání prvku v binárním vyhledávacím stromu?
Odpověď: Hledání začíná u kořene. Porovnává se hledaná hodnota s hodnotou aktuálního uzlu. Pokud je menší, pokračuje se vlevo; pokud je větší, pokračuje se vpr
Kartička 5
Otázka: Jaký je postup pro vkládání nové hodnoty do binárního vyhledávacího stromu?
Odpověď: Vkládání začíná u kořene. Hodnota se porovnává s aktuálním uzlem. Pokud je menší, pokračuje se vlevo; pokud je větší, pokračuje se vpravo. Pokračuje s
Kartička 6
Otázka: Co se stane, pokud se při vkládání do BST narazí na již existující hodnotu (za předpokladu, že duplikáty nejsou povoleny)?
Odpověď: Hodnota se ignoruje, protože již ve stromu existuje.
Kartička 7
Otázka: Proč je mazání uzlu z BST nejsložitější operace?
Odpověď: Je třeba zachovat vlastnost BST, což vyžaduje řešení tří různých případů pro mazaný uzel.
Kartička 8
Otázka: Jak se maže uzel, který je listem, z BST?
Odpověď: Uzel se jednoduše odstraní a odkaz jeho rodiče se nastaví na null.
Kartička 9
Otázka: Jak se maže uzel z BST, který má jednoho potomka?
Odpověď: Uzel se nahradí jeho jediným potomkem. Rodič mazaného uzlu nyní odkazuje na tohoto potomka.
Kartička 10
Otázka: Jaké časové složitosti pro většinu operací dosahuje BST, pokud je strom vyvážený?
Odpověď: Logaritmickou časovou složitost.