nechodím na prednáškyADŠ prednáška 10: Set, map. Dolný odhad zložitosti pre triedenie porovnávaním.
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška uzatvára tému binárnych vyhľadávacích stromov ukážkou dátových štruktúr, ktoré sa nad nimi stavajú. Vyvažovaný strom umožňuje reprezentovať usporiadanú množinu (set) s operáciami vkladania, mazania, vyhľadávania a posúvania sa na nasledujúci či predchádzajúci prvok v logaritmickom čase. Usporiadané asociatívne pole (map, v Jave TreeMap) ukladá do vrcholov dvojice kľúč–hodnota, pričom sa porovnávajú len kľúče, a kľúče musia byť navzájom porovnávateľné. Multiset sa dá realizovať ako mapa, kde hodnota udáva násobnosť prvku. Výhodou usporiadanosti sú intervalové dotazy, napríklad hľadanie bytov v cenovom rozpätí, ktoré hešovacia tabuľka, spomenutá ako efektívnejšia a menej všeobecná alternatíva, nezvláda.
- - Set je usporiadaná množina nad vyvažovaným stromom; všetky základné operácie bežia v logaritmickom čase.
- - Map (C++) alebo TreeMap (Java) ukladá do vrcholov dvojice kľúč–hodnota a porovnáva sa podľa kľúča.
- - Kľúče musia byť navzájom porovnávateľné s tranzitívnym usporiadaním; vlastné objekty potrebujú definovaný operátor porovnania.
- - Set aj map v STL používajú tú istú implementáciu vyvažovaného stromu.
- - Multiset sa dá urobiť ako mapa, kde hodnota je násobnosť prvku a pri nulovej početnosti sa záznam maže.
- - Usporiadanosť umožňuje intervalové dotazy: nájsť prvý kľúč väčší alebo rovný a iterovať ďalej.
- - Hešovanie, ktoré príde neskôr, je efektívnejšie, no vyžaduje len rovnosť a hešovaciu hodnotu a intervalové dotazy nepodporuje.
Zhrnutie pripravené s pomocou AI z prepisu videa.
