Záznam přednášky - Splay stromy
| Akce: | Krutá Smršť Přednášek 2017 (záznamy z akce) |
|---|---|
| Přednášející: | Martin Mareš |
| Motto: | Lepší než uklízení je organizovaný chaos. |
| Anotace: | Zapomeňte na pracné vyvažování vyhledávacích stromů. Místo toho zavedeme triviální pravidlo: pokaždé, když pracujeme s nějakým prvkem, vytáhneme ho do kořene stromu. Ukážeme, že toto pravidlo stačí na dosažení logaritmické složitosti, tedy aspoň amortizovaně. Také dokážeme, že Splay strom je nejhůře konstanta-krát horší než libovolný jiný strom, a možná i spousta dalších magických vlastností. |
| Ke stažení: | Video (MP4/H.264) a Audio (MP3/AAC) |