Selected Chapters in Data Structures
In the winter semester of 2026/2027, I teach a course on advanced data structures [NTIN110]. The goal is to look a little further than what we cover in the introductory master's course Data Structures 1+2. You can take this course multiple times; we cover something different every year. We will have some guest speakers.
This year, we are honored to have Petr Chmel and Lukáš Ondráček as guest speakers.
The lecture is held on Thursdays from 10:40 in room S322.
If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
| date | topic |
|---|---|
| 6. 10. | MM: Binary search trees: a look at the whole landscape. Encoding (2,3) and (2,4)-trees by binary search trees. Different versions of red-black trees. Insertion to left-leaning RB trees. |
| 8. 10. | MM: Rank-balanced binary trees. Weak AVL trees: definition, correspondence with AVL and RB trees, bottom-up balancing. |
| 15. 10. | MM: Weak AVL trees: amortized analysis of bottom-up balancing, bounding height using the number of insertions, top-down balancing: safe nodes. |
| 22. 10. | MM: Weak AVL trees: top-down balancing with resets, #rebalances decreases exponentially with rank. Treaps: definition, uniqueness, operations via Join and Split. |
| 29. 10. | MM: Randomized search trees: expected depth of a node, expected height of the tree. Skip lists: two implementations, expected time per search, expected height. |
| 5. 11. | MM: Tango trees. |
| 12. 11. | MM: Proof of Lemma A.3 from previous lecture. LO: Multi-splay trees. |
| 19. 11. | PC: Competitiveness of Splay trees: basic concepts, restricted optimal tree, ternary view, heavy paths, lazy intervals. |
| 26. 11. | No lecture today. We have the Open House Day. |
| 3. 12. | Plan: Competitiveness of Splay trees continued. |
Sources
- Binary search trees:
- Sedgewick: Left-Leaning Red-Black Trees
- Haupler, Sen, Tarjan: Rank-balanced trees
- Hand-out for balancing operations on WAVL trees (Xournal++ source)
- Randomized data structures:
- Aragon, Seidel: Randomized Search Trees
- Mareš: Průvodce labyrintem algoritmů, chapter 11.6 (in Czech)
- Pugh: Skip Lists: A Probabilistic Alternative to Balanced Trees
- Jun: An Analysis of Skip Lists
- Dynamic optimality of binary search trees:
- Demaine et al: Dynamic Optimality – Almost – Tango trees
- Wang: Multi-splay trees
- Chmel et al.: Splay trees are almost dynamically optimal
Links
- VKDS 2025: pokročilé hešování (tabelace, lineární přidávání s 5-nezávislostí, partition hashing, iceberg hashing)
- VKDS 2024: persistentní struktury, úsporné struktury
- VKDS 2023: cache-oblivious třídění + datové struktury, zlomkové kaskádování
- VKDS 2022: Q-haldy, Fusion trees, exponenciální stromy, redukce univerza na polynomiální, Marked ancestor a dolní odhad na něj
- VKDS 2021: streaming algoritmy, analýza kukaččího hešování
- VKDS 2020: celočíselné struktury, randomizované stromy, zlomkové kaskádování, lock/wait-free struktury
- PDS 2019: rankové vyvážené stromy, kompetitivní dynamické stromy, cache-oblivious struktury, p/q-fast trie