van Emde Boas Trees

1. Predecessor search/ordered sets

predecessor: return the nearest left neighborsuccessor: return the nearest right neighbor

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

predecessor/successor: if x∈Sx\in Sx∈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/2w/2w/2. And since for each position in the binary there could be 1/01/01/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 111;Theorem:the recursion depth of the universe U=[2w]U=[2^w]U=[2w] is [log⁡2w]=O(loglog∣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 111, then we can know there are [log⁡2w][\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(SSS) and/or max(SSS) 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. R2SR^2SR2S-vEB: expected O(loglog|U|) time, O(n) space