Cvičení z Datových struktur I

V zimním semestru 2017/2018 cvičím Datové struktury I [NTIN066] ke své přednášce. Cvičení se koná v lichých týdnech od 10:40 v S8.

Pravidla udělování zápočtů a zadání domácích úkolů najdete na webu přednášky.

datum co jsme dělali
5. 10. Konstrukce dokonale vyvážených BVS ze setřiděného pole či posloupnosti (stačí O(log n) pomocné paměti, ale jde to i s konstantní). Jak zadaný BVS dokonale vyvážit. Očekavaná průměrná hloubka vrcholu v BVS vzniklém Inserty v náhodném pořadí je O(log n); souvislost se složitostí QuickSortu. Trik: reprezentace levého/pravého syna + otce pomocí dvou ukazatelů. Jiný trik: reprezentace AVL stromů, které stačí 1 bit vyvažovací informace na vrchol.
19. 10. Splay stromy: Experimenty se splayováním na levé cestě – (a) Splay(1), (b) střídavě Splay(1) a Splay(n), (c) Splay(1) … Splay(n). Naivní versus poctivé splayování. Nastavování vah: Static Finger Theorem, Working Set Theorem. Hypotéza: Provedeme-li na libovolném stromu postupně Splay(1) … Splay(n), vznikne cesta.
Stránku spravuje Martin Mareš