nechodím na prednáškyAlgoritmy a dátové štruktúry prednáška 08
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 nadväzuje na binárny vyhľadávací strom a rozoberá, prečo náhodné poradie vkladania prvkov väčšinou vedie k logaritmickej hĺbke stromu, zatiaľ čo cielene zoradený vstup (napríklad abecedne rastúce mená používateľov) vytvorí patologicky hlboký strom. Podrobne sa vysvetľuje operácia mazania prvku z BST pre tri prípady - list, vrchol s jedným synom a vrchol s dvoma synmi, kde sa mazaný prvok nahrádza najmenším prvkom svojho pravého podstromu. Ďalej sa predstavuje in-order, pre-order a post-order prechod stromom s časovou zložitosťou O(n) bez ohľadu na tvar stromu, a využitie post-order prechodu pri vyhodnocovaní aritmetických výrazov cez reverznú poľskú notáciu. Na záver sa zavádza pojem iterátora s operáciami na nájdenie najbližšieho väčšieho a menšieho prvku a stručne sa predstavujú samovyvažujúce stromy (AVL stromy, červeno-čierne stromy) ako riešenie problému nevyváženého stromu s garantovanou logaritmickou hĺbkou.
- Náhodné vs. zoradené vkladanie a hĺbka binárneho vyhľadávacieho stromu
- Mazanie prvku z BST - list, jeden syn, dvaja synovia
- Nahradenie mazaného vrcholu najmenším prvkom pravého podstromu
- In-order, pre-order a post-order prechod stromom
- Reverzná poľská notácia a vyhodnocovanie výrazov pomocou post-order
- Iterátory nad BST - nájdenie najbližšieho väčšieho a menšieho prvku
- Amortizovaná zložitosť prechodu stromom pomocou iterátora
- Úvod do samovyvažujúcich stromov (AVL stromy, červeno-čierne stromy)
Zhrnutie pripravené s pomocou AI z prepisu videa.
