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

Links

This page is maintained by Martin Mareš