van Emde Boas Trees

1. Predecessor search/ordered sets

• predecessor: return the nearest left neighbor
• successor: return the nearest right neighbor

2.Naive: O ( ∣ U ∣ ) O(|U|) O(∣U∣) space

• predecessor/successor: if x ∈ S x\in S x∈S then it’s O ( 1 ) O(1) O(1);
• insert: worst case: O ∣ U ∣ O|U| O∣U∣; compare with all elements; lucky case smaller than the min or bigger than the max.

3. Twolevel: O ( ∣ U ∣ ) O(|U|) O(∣U∣) space

• predecessor/successor: worst case: loop over the cluster of one summary, and the length of the cluster is half of the length of the original number, which is w / 2 w/2 w/2. And since for each position in the binary there could be 1 / 0 1/0 1/0, then there would be 2 [ w / 2 ] 2^{[w/2]} 2[w/2] different elements in one cluster. Thus, the time: O ( ∣ U ∣ ) O(\sqrt{|U|}) O(∣U∣ ​).
• insert: loop over the summary and loop over one of the whole cluster.

4. Recursive: O ( ∣ U ∣ ) O(|U|) O(∣U∣) space

• Stop: when the length of the elements is 1 1 1;
• Theorem: the recursion depth of the universe U = [ 2 w ] U=[2^w] U=[2w] is [ log ⁡ 2 w ] = O ( l o g l o g ∣ U ∣ ) [\log_2w]=O(loglog|U|) [log2​w]=O(loglog∣U∣);
• Proof (intuitive): each recursion in binary we half the length of elements, and the recursion would stop when the length is 1 1 1, then we can know there are [ log ⁡ 2 w ] [\log_2w] [log2​w] recursions in O ( log ⁡ log ⁡ ∣ U ∣ ) O(\log\log |U|) O(loglog∣U∣)

Time in operations

• member: go through the recursion depth to check;
• predecessor/successor: go through the recursion depth;
• insert/delete: operation on both summary and cluster, then it would be double the depth of the recursion depth.

5. vEB: worst case O ( log ⁡ log ⁡ ∣ U ∣ ) O(\log\log|U|) O(loglog∣U∣) time, O ( ∣ U ∣ ) O(|U|) O(∣U∣) space

• How to improve the time:

  Idea: Exclude min( S S S) and/or max( S S S) from the set of keys stored in summary and clusters.

• line 10 to line 13: enter the next depth

6. RS-vEB: expected O(loglog|U|) time, O(nloglog|U|)

• Use a hash table to store clusters.

  

• Time: Since the depth of the veb tree is O ( log ⁡ log ⁡ ∣ U ∣ ) O(\log\log|U|) O(loglog∣U∣), and in hash table the time for updates is O ( 1 ) O(1) O(1);

• Space: each time we insert a new element, the space cost would be O ( log ⁡ log ⁡ ∣ U ∣ ) O(\log\log|U|) O(loglog∣U∣) in worst case, thus the total space would be the number of elements times the depth.

7. R 2 S R^2S R2S-vEB: expected O(loglog|U|) time, O(n) space