# Tutorial

- allowed containers: `std::vector` in C++, `[]` in Python
- if we use C++, the datasets are 100× larger (to compensate for the slowness of Python)
- we want to store a subset $S\subseteq\mathcal U$
	- $|S|=n$
	- we allocate an array of size $m=\Theta(n)$
	- $M=\set{0,\dots,m-1}$
	- idea: store value $x\in S$ at the index $h(x)$
		- $h:\mathcal U\to M$
	- collisions may occur (s.t. $h(x)=h(y)$)
		- the simplest solution: linked list
		- if we consider $m=\Theta(n)$ and a hashing function which spreads elements uniformly, the length of the lists will be constant *on average*
- heap
- analysis of Dijkstra using heap
	- binary heap vs. $d$-regular heap
	- how to select optimal $d$
	- $O(m\log_d n+nd\log_d n)$
		- two terms, one increases with $d$, the other decreases with $d$ increasing
		- intuition: we need the two terms to be equal to get the minimal value
	- so we use $d=\max{\set{2,\lceil m/n\rceil}}$
	- does it help?
		- for dense graphs, it helps
		- by substitution, we get complexity $\frac{m\log n}{\log(m/n)}$
		- if $m\geq n^{1+\varepsilon}$, then this equals $\frac{m\log n}{\log n^\varepsilon}=\frac1\varepsilon m=O(m)$
- binary tree
- binary search tree
- single rotation – we rotate a non-root node $u$ with its parent $p$
	- $u$ becomes a parent of $p$
- idea: whenever we access an element, we move it to the root
	- frequently accessed elements end up close to the root (not so deep)
	- but simple rotations can make the tree very unbalanced
- splay trees
	- we apply zig (single) rotation only if the node is a child of the root
	- zig-zag are just two single rotations of x
	- trick: for zig-zig, we first rotate the parent and grandparent
	- find operation
		- find and splay
		- if you don't find, splay the last found element
			- otherwise, the enemy could ask us to find an absent element too many times
	- insert = insert (if not present) & splay!
	- delete = replace by the successor, delete the successor, splay the parent of the deleted successor
		- or we could (somehow) splay the tree first and then delete