Rekurzia v binárnom vyhľadávaní. Algoritmy na grafoch.

Zhrnutie prednášky

Prednáška sa po úvode k nadchádzajúcej téme grafov, ktoré študenti poznajú z diskrétnej matematiky, vracia k vyhľadávaniu a stromom a ukazuje rekurzívne riešenia namiesto doterajších cyklických. Najprv predstavuje rekurzívne binárne vyhľadávanie v usporiadanom poli reťazcov, ktoré polí interval pomocou ľavého a pravého indexu, hľadá stred a porovnáva ho s hľadaným slovom. Rekurzia končí nájdením prvku alebo prekrížením hraníc. Na príklade s menami (Jaro, Ada) je krok za krokom ukázaný postup. Následne sa rovnakým spôsobom rekurzívne rieši vkladanie do binárneho vyhľadávacieho stromu a vyhľadávanie v ňom, pričom ukazovateľ sa posúva doľava alebo doprava, kým nenarazí na NULL alebo zhodné slovo. Prednášajúci odporúča kurz MIT Introduction to Algorithms na štúdium časovej zložitosti.

• - Rekurzívne binárne vyhľadávanie polí interval, počíta stred ako (ľavý + pravý) / 2 a porovnáva ho s hľadaným reťazcom.
• - Rekurzia končí nájdením prvku (návrat 1) alebo keď ľavý index prekročí pravý (návrat 0).
• - Rekurzívne riešenie je elegantnejšie ako cyklus; cyklus možno transformovať na rekurziu a naopak.
• - Vkladanie do binárneho vyhľadávacieho stromu: ak je ukazovateľ NULL, vytvorí sa nový uzol, inak sa rekurzívne pokračuje vľavo alebo vpravo podľa slovníkového usporiadania.
• - Vyhľadávanie v strome funguje analogicky: NULL znamená, že slovo v strome nie je, zhoda znamená nájdenie.
• - Rekurzia nevyžaduje pomocné premenné ani pamätanie si cesty, pretože ukazovateľ nahrádza každé volanie funkcie.
• - Na časovú zložitosť algoritmov sa odporúča kurz MIT Introduction to Algorithms.

Zhrnutie pripravené s pomocou AI z prepisu videa.