Algoritmy a dátové štruktúry prednáška 07

Zhrnutie prednášky

Prednáška sa venuje binárnemu vyhľadávaniu v usporiadanom poli vrátane praktických detailov, ako je odovzdávanie parametrov referenciou v C++ namiesto hodnotou kvôli efektivite. Na konkrétnom príklade sa ukazuje, ako ľahko vzniknú chyby o jeden (nekonečný cyklus, chyba pri prázdnom poli), a ako sa im dá vyhnúť dôsledným formulovaním invariantu pomocou 'dobrých' a 'zlých' prvkov a dvoch ukazovateľov s hraničnými hodnotami low a high. Zavádza sa pojem polouzavretého intervalu ako spôsob reprezentácie rozsahov bez nutnosti riešiť špeciálny prípad prázdnej množiny, s príkladmi z Pythonu a C++ iterátorov. Druhá časť prednášky prevádza binárne vyhľadávanie na rozhodovací strom a z neho odvodzuje binárny vyhľadávací strom (BST), pričom sa definuje podmienka usporiadanosti (vľavo menšie, vpravo väčšie hodnoty) a ukazuje sa, že rovnaká množina čísel môže tvoriť viacero rôznych platných BST.

• Binárne vyhľadávanie v usporiadanom poli
• Odovzdávanie parametrov hodnotou vs. referenciou v C++
• Chyby o jeden a nekonečný cyklus pri nesprávnej implementácii
• Invariant s dobrými a zlými prvkami, ukazovatele low a high
• Polouzavreté intervaly a ich využitie pri reprezentácii rozsahov
• Binárny vyhľadávací strom (BST) ako rozhodovací strom vyhľadávania
• Podmienka usporiadanosti BST - ľavý podstrom menší, pravý väčší

Zhrnutie pripravené s pomocou AI z prepisu videa.