Selected Chapters in Data Structures
In the winter semester of 2026/2027, I'll be teaching 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.
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. | Rank-balanced binary trees. Weak AVL trees: definition, correspondence with AVL and RB trees, bottom-up balancing. |
| 15. 10. | Plan: Weak AVL trees: further analysis. |
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)
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