Skip to content

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 \(\geq\) 2 elements, max value will be in a cluster
  • Modified functions for accessing \(x\)
    • \(⌊x/\sqrt[\downarrow] u⌋\) - \(high(x)\)
    • \(x \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, \(\geq\) 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

img

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