Proto van Emde Boas

Summarized notes on Introduction to Algorithms, Chapter 20

Structure

• universe size is $2^{2^k}$
• when $u=2$ it contains an array of 2 bits
• when $u\ge 4$, it contains
  • pointer named summary to proto-vEB($\sqrt{u}$) structure
  • an array named cluster of $\sqrt{u}$ pointers, each to proto-vEB($\sqrt{u}$) structure
• $x$ is recursively stored in the structure
  • $\lfloor x/\sqrt{u}\rfloor$ - $high(x)$ - cluster of some value $x$ stored in proto-vEB
  • $x\mathrm{mod}\sqrt{u}$ - $low(x)$ - position of $x$ within its cluster
  • $u$ used by these functions will be the universe size of the data structure in which the function is called, which changes as we descend into the recursive structure
  • $index(high(x),low(x))$ - exact location of $x$ within proto-vEB

Operations

• Min/max takes one argument, proto-vEB structure $V$
• Other operations take two arguments: $x$ and proto-vEB structure $V$
• Range of $x$ is $0\le x<V.u$
• issue: too many recursive calls

Member

• 1 recursive call: recurse until $u=2$, then return $V.A[x]$

Min/max

• 2 recursive calls:
  • one to find cluster with min/max value
  • one to find offset of min/max value within its cluster

Successor/predecessor

• 3 recursive calls in worst case:
  • two recursive calls to self
  • call to minimum

Insert

• 2 recursive calls:
  • 1 to perform actual insert
  • 1 to update summary bit

Delete

• no implementation given but
  • recursively perform actual delete
  • recursively check each cluster for members and update summary

Operation complexity

Running time
$O(\lg \lg u)$	member
$\mathrm{\Theta }(\lg u)$	minimum, maximum, insert
$\mathrm{\Theta }(\lg u\lg \lg u)$	successor, predecessor