Van Emde Boas Tree

Summarized notes on Introduction to Algorithms, Chapter 20

Core idea: reduce number of recursive calls to get $O(\lg \lg u)$ running times

Structure

• $u$ size is $2^k$
• summary vEB($\sqrt[\uparrow ]{u}$) structure
• cluster of $\sqrt[\uparrow ]{u}$ pointers, each to proto-vEB($\sqrt[\downarrow ]{u}$) structure
• attribute for minimum and max value
  • minimum value does not appear in any cluster
  • when vEB contains $\ge$ 2 elements, max value will be in a cluster
• Modified functions for accessing $x$
  • $\lfloor x/\sqrt[\downarrow ]{u}\rfloor$ - $high(x)$
  • $x\mathrm{mod}\sqrt[\downarrow ]{u}$ - $low(x)$

benefits of min/max attributes

• min/max operations do not need recursion
• predecessor/successor does not need recursion to determine min/max
• insert and delete benefit because min/max indicate number of values (0, 1, $\ge$ 2)
• when vEB is empty, insert will be into min and max attributes in constant time
• delete of last element is constant time

creating vEB

• creating vEB tree depends on $u$ and is linear time and requires $O(u)$ space
  • DO use when number of expected operations is high
  • DO NOT use when number of expected operations is low

Operations

Member

• 1 recursive call to find $x$: also check in min/max attributes on each iteration

Min/max

• both can be read from attributes in constant time

Successor/predecessor

• min/max attributes indicate if value is in the same cluster or not
• 1 recursion only: either within same cluster - or - on summaries
• predecessor is symmetric with 1 additional case: when predecessor does not exist in a cluster because it is stored in min attribute

Insert

• during insertion cluster is either empty or not empty
  • when cluster is non-empty, summary does not need to be updated
  • when cluster is empty set min/max attributes only and recurse to update summaries
• if $x$ is min, update min attribute and perform insert on the previous min value
• if value is max, lastly update max attribute

Delete

• when only 1 element exists in $V$, set min/max attributes to $null$
• for $u=2$ update min/max attributes only
• otherwise:
  • when deleting min, choose value from cluster to become new min, and delete new min from cluster
  • if tree becomes empty, update summary
  • if all clusters become empty then only $V.min$ is left → set $V.min=V.max$
  • otherwise set max to the maximum element in the highest-numbered cluster.
  • if cluster remains non empty after deleting $x$, summary is unaffected; max attribute may need to change

Operation complexity

Running time
$O(1)$	minimum, maximum
$O(\lg \lg u)$	member, insert, delete, successor, predecessor
$O(u)$	creating empty structure