Tutorial

• $|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

• 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)$

$u$ becomes a parent of $p$

• frequently accessed elements end up close to the root (not so deep)
• but simple rotations can make the tree very unbalanced

• 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