Skip to content

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 \geq 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
    • \(⌊x/\sqrt u⌋\) - \(high(x)\) - cluster of some value \(x\) stored in proto-vEB
    • \(x \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

img

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 \leq 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
\(\Theta(\lg u)\) minimum, maximum, insert
\(\Theta(\lg u \lg \lg u)\) successor, predecessor