Van Emde Boas tree

A van Emde Boas tree (), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with -bit integer keys. It performs all operations in time, or equivalently in time, where is the maximum number of elements that can be stored in the tree. The is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree data-structures is often measured. The vEB tree has good space efficiency when it contains many elements, as discussed below. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.
Supported operations.
A vEB supports the operations of an "ordered associative array", which includes the usual associative array operations along with two more "order" operations, "FindNext" and "FindPrevious":
A vEB tree also supports the operations "Minimum" and "Maximum", which return the minimum and maximum element stored in the tree respectively. These both run in time, since the minimum and maximum element are stored as attributes in each tree.
How it works.
 For the sake of simplicity, let for some integer "k". Define . A vEB tree over the universe } has a root node that stores an array of length . is a pointer to a vEB tree that is responsible for the values }. Additionally, "T" stores two values and as well as an auxiliary vEB tree .
Data is stored in a vEB tree as follows: The smallest value currently in the tree is stored in and largest value is stored in . Note that is not stored anywhere else in the vEB tree, while is. If "T" is empty then we use the convention that and . Any other value "x" is stored in the subtree where . The auxiliary tree keeps track of which children are non-empty, so contains the value "j" if and only if is non-empty.
FindNext.
The operation that searches for the successor of an element "x" in a vEB tree proceeds as follows: If then the search is complete, and the answer is . If then the next element does not exist, return M. Otherwise, let . If then the value being searched for is contained in so the search proceeds recursively in . Otherwise, we search for the value "i" in . This gives us the index "j" of the first subtree that contains an element larger than "x". The algorithm then returns . The element found on the children level needs to be composed with the high bits to form a complete next element.
 function FindNext(T, x)
 if x < T.min then
 return T.min
 if x ≥ T.max then "// no next element"
 return M
 i = floor(x/)
 lo = x mod 
 if lo < T.children[i].max then
 return ( i) + FindNext(T.children[i], lo)
 j = FindNext(T.aux, i)
 return ( j) + T.children[j].min
 end
Note that, in any case, the algorithm performs work and then possibly recurses on a subtree over a universe of size (an bit universe). This gives a recurrence for the running time of , which resolves to .
Insert.
The call that inserts a value into a vEB tree operates as follows:
In code:
 function Insert(T, x)
 if T.min > T.max then "// T is empty"
 T.min = T.max = x;
 return
 if x < T.min then
 swap(x, T.min)
 if x > T.max then
 T.max = x
 i = floor(x / )
 lo = x mod 
 Insert(T.children[i], lo)
 if T.children[i].min == T.children[i].max then
 Insert(T.aux, i)
 end
The key to the efficiency of this procedure is that inserting an element into an empty vEB tree takes time. So, even though the algorithm sometimes makes two recursive calls, this only occurs when the first recursive call was into an empty subtree. This gives the same running time recurrence of as before.
Delete.
Deletion from vEB trees is the trickiest of the operations. The call that deletes a value "x" from a vEB tree T operates as follows:
In code:
 function Delete(T, x)
 if T.min == T.max == x then
 T.min = M
 T.max = −1
 return
 if x == T.min then
 hi = T.aux.min * 
 j = T.aux.min
 T.min = x = hi + T.children[j].min
 i = floor(x / )
 lo = x mod 
 Delete(T.children[i], lo)
 if T.children[i] is empty then
 Delete(T.aux, i)
 if x == T.max then
 if T.aux is empty then
 T.max = T.min
 else
 hi = T.aux.max * 
 j = T.aux.max
 T.max = hi + T.children[j].max
 end
Again, the efficiency of this procedure hinges on the fact that deleting from a vEB tree that contains only one element takes only constant time. In particular, the second Delete call only executes if "x" was the only element in prior to the deletion.
Python implementation.
from math import ceil, log2
van Emde Boas Tree is a data structure which gives O(log(log(u))
query time for operations like 
insert, search, delete, successor and predecessor
VEB class contains attribute
min, max, u, w, cluster and summary
initially min=max=NULL
u = size of universe (the range of total possible entries)
w = word length (number of bits in u)
w = log2(u)
cluster is an array of VEB structures of size of sqrt(u)
summary is a VEB of size sqrt(u)
when the size of VEB structure reaches we don't store clusters and summary vector
min and max are enough to store this structure.
class VEB:
 """Index of x can be determined as the
 cluster number and the position inside the cluster
 for example lets consider 11
 in binary it is written as 1011
 so first half parts of the binary strinig give cluster number
 and 2nd half gives the postiton inside cluster
 cluster number= int(10)= 2
 position inside cluster= int(11)=3
 so 11 is in 2nd cluster at 3rd position
 where counting starts from 0th position
 0,1,2,3|4,5,6,7|8,9,10,11|12,13,14,15
 here we use 'c' to denote cluster number
 and 'i' to denote index inside the cluster
 so x can be represented as <c,i>
 where x = c * sqrt(u) + i
 def high(self, x):
 # high(x)=x//int(sqrt(u))
 return x » (self.w // 2)
 def low(self, x):
 # low(x)= x%int(sqrt(u))
 return x & (1 « (self.w // 2)) - 1
 def index(self, i, j):
 # return i*int(sqrt(self.u))+j
 return i « (self.w // 2) | j
 def __init__(self, u):
 This have been implemented using hash table
 to reduce the space complexity from O(U) to O(n*log(log(u))
 because u can be very large. for example if word size = 64 bits
 u= 2^64 = 16 million TB which can't be stored practically on ram.
 where as n*log*log*u can be O(3n) which can be easily stored.
 I have a different code for array implementation too.
 self.w = ceil(log2(u))
 # self.u = 2 ** self.w
 self.min = self.max = None
 if self.w >= 1: # when u==2^w=2 min and max are enough so we stop recursion
 self.summary = None
 def member(self, x):
 """Function to check if x is present in tree or not."""
 if x == self.min or x == self.max:
 return True
 elif self.w == 1:
 return False
 else:
 c = self.high(x)
 i = self.low(x)
 if c in self.cluster:
 return self.cluster[c].member(i)
 else:
 return False
 def insert(self, x):
 if self.min is None:
 self.min = x
 self.max = x
 return
 else:
 if x < self.min:
 x, self.min = self.min, x
 c = self.high(x)
 i = self.low(x)
 if self.w > 1:
 if c not in self.cluster:
 self.cluster[c] = VEB(2 ** (self.w // 2))
 if self.cluster[c].min is None:
 if self.summary is None:
 self.summary = VEB(2 ** (self.w // 2))
 self.summary.insert(c)
 if c not in self.cluster:
 self.cluster[c] = VEB(2 ** (self.w // 2))
 self.cluster[c].insert(i)
 if x > self.max:
 self.max = x
 def successor(self, x):
 if self.w == 1:
 if x == 0 and self.max == 1:
 return 1
 else:
 return None
 elif self.min is not None and x < self.min:
 return self.min
 else:
 c = self.high(x)
 i = self.low(x)
 if c in self.cluster:
 maxlow = self.cluster[c].max
 else:
 maxlow = None
 if maxlow is not None and i < maxlow:
 offset = self.cluster[c].successor(i)
 return self.index(c, offset)
 else:
 if self.summary is not None:
 succ_cluster = self.summary.successor(self.high(x))
 else:
 succ_cluster = None
 if succ_cluster is None:
 return None
 else:
 offset = self.cluster[succ_cluster].min
 return self.index(succ_cluster, offset)
 def predecessor(self, x):
 if self.w == 1:
 if x == 1 and self.min == 0:
 return 0
 else:
 return None
 elif self.max is not None and x > self.max:
 return self.max
 else:
 c = self.high(x)
 i = self.low(x)
 if c in self.cluster:
 min_low = self.cluster[c].min
 else:
 min_low = None
 if min_low is not None and i > min_low:
 offset = self.cluster[c].predecessor(i)
 return self.index(c, offset)
 else:
 if self.summary is not None:
 prev_cluster = self.summary.predecessor(c)
 else:
 prev_cluster = None
 if prev_cluster is None:
 if self.min is not None and x > self.min:
 return self.min
 else:
 return None
 else:
 offset = self.cluster[prev_cluster].max
 return self.index(prev_cluster, offset)
 def delete(self, x):
 if self.min is None:
 return
 if x < self.min or x > self.max:
 return
 if self.min == self.max:
 self.min = self.max = None
 elif self.w == 1:
 if x == 0:
 self.min = 1
 else:
 self.min = 0
 self.max = self.min
 else:
 c = self.high(x)
 i = self.low(x)
 if x == self.min:
 if self.summary:
 first_cluster = self.summary.min
 else:
 first_cluster = None
 if first_cluster:
 x = self.index(first_cluster, self.cluster[first_cluster].min)
 self.min = x
 if c in self.cluster:
 self.cluster[c].delete(i)
 if self.cluster[c].min is None:
 self.summary.delete(c)
 if x == self.max:
 summary_max = self.summary.max
 if summary_max is None:
 self.max = self.min
 else:
 self.max = self.index(summary_max, self.cluster[summary_max].max)
 elif x == self.max:
 self.max = self.index(c, self.cluster[c].max)
Discussion.
The assumption that is an integer is unnecessary. The operations formula_1 and formula_2 can be replaced by taking only higher-order and the lower-order bits of , respectively. On any existing machine, this is more efficient than division or remainder computations.
The implementation described above uses pointers and occupies a total space of . This can be seen as follows. The recurrence is formula_3.
Resolving that would lead to formula_4.
One can, fortunately, also show that by induction.
In practical implementations, especially on machines with "shift-by-k" and "find first zero" instructions, performance can further be improved by switching to a bit array once equal to the word size (or a small multiple thereof) is reached. Since all operations on a single word are constant time, this does not affect the asymptotic performance, but it does avoid the majority of the pointer storage and several pointer dereferences, achieving a significant practical savings in time and space with this trick.
An obvious optimization of vEB trees is to discard empty subtrees. This makes vEB trees quite compact when they contain many elements, because no subtrees are created until something needs to be added to them. Initially, each element added creates about new trees containing about pointers all together. As the tree grows, more and more subtrees are reused, especially the larger ones. In a full tree of elements, only space is used. Moreover, unlike a binary search tree, most of this space is being used to store data: even for billions of elements, the pointers in a full vEB tree number in the thousands.
However, for small trees the overhead associated with vEB trees is enormous: on the order of formula_5. This is one reason why they are not popular in practice. One way of addressing this limitation is to use only a fixed number of bits per level, which results in a trie. Alternatively, each table may be replaced by a hash table, reducing the space to (where is the number of elements stored in the data structure) at the expense of making the data structure randomized. Other structures, including y-fast tries and x-fast tries have been proposed that have comparable update and query times and also use randomized hash tables to reduce the space to or .