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.

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. Plan: MM: Tango trees.
12. 11. Plan: LO: Multi-splay trees.

Sources

Links

This page is maintained by Martin Mareš