CSE603
ADVANCED PROBLEM SOLVING
Study Of Van Emde Boas Tree
with application to Dijkstra
Author: Roll Number:
Jatin Paliwal 2018202006
Yashdeep Saini 2018202020
1
Implementing Van Emde Boas Tree with application to Dijkstra
and comparison with respect to Red-Black Trees and AVL
I. Abstract
We present a study and implementation of Van Emde Boas tree, a data
structure based upon hierarchically decomposed tree which provides us
with worst case complexity of O(log(log n)) per instructions.
Utilization of latter was tested for Dijkstra algorithm and a
comparative study was done against Red-Black Trees and AVL.
II. Introduction
Consider the following operations given a dynamic set of elements on a
Universe u with range defined as {0, 1, ...u-1}:
insert(x) : Adds an item x to the set S.
isEmpty() : Returns true if S is empty, else false.
find(x) : Returns true if x is present in S, else false.
insert(x) : Inserts an item x to S.
delete(x) : Delete an item x from S.
max() : Returns maximum value from S.
min() : Returns minimum value from S.
successor(x) : Returns the smallest value in S which is greater than x.
predecessor(x) : Returns the largest value in S which is smaller than x.
We have different ways of performing these operations as following:
● Direct addressing
Direct addressing provides the simplest approach to storing a dynamic
set. Since we are concerned only with storing keys, we can simply store
them as a bit vector. To store a dynamic set of values from the universe
[0 - u-1] we will use u bits. A bit is set in vector in corresponding
location of the value otherwise off. The entry A[x] holds a 1 if the
value x is in the dynamic set, and it holds a 0 otherwise. Although we
can perform each of the INSERT , DELETE, and MEMBER operations in O(1)
time with a bit vector, the remaining operations MINIMUM, MAXIMUM,
SUCCESSOR, and PREDECESSOR — each takes O(u) time in the worst case
because we might have to scan through all the elements in the array.
● Superimposing a binary tree structure
2
Figure-1 Binary tree superimposed over Bit Vector
We can short-cut long scans in the bit vector by superimposing a binary
tree of bits on top of it. The entries of the bit vector form the leaves
of the binary tree, and each internal node contains a 1 if and only if
any leaf in its subtree contains a 1. In other words, the bit stored in
an internal node is the logical OR of its two children. The operations
that took O(u) worst-case time with an simple bit vector now use the
tree structure:
MIN
● To find the minimum value in the set, start at the root and head
down toward the leaves, always taking the leftmost node containing
a 1.
MAX
● To find the maximum value in the set, start at the root and head
down toward the leaves, always taking the rightmost node containing
a 1.
3
SUCCESSOR
● To find the successor of x, start at the leaf indexed by x, and
head up toward the root until we enter a node from the left and
this node has a 1 in its right child Z. Then head down through node
Z, always taking the leftmost node containing a 1.
PREDECESSOR
● To find the predecessor of x, start at the leaf indexed by x, and
head up toward the root until we enter a node from the right and
this node has a 1 in its left child Z. Then head down through node
Z, always taking the rightmost node containing a 1. In figure-1 we
have shown a traversal with the Vector[15]-A-B-C-D-E-F-G-Vector[7].
We also change the INSERT and DELETE operations appropriately. When
inserting a value, we store a 1 in each node on the simple path from the
appropriate leaf up to the root. When deleting a value, we go from the
appropriate leaf up to the root, recomputing the bit in each internal
node on the path as the logical OR of its two children. Since the height
of the tree is lg u and each of the above operations makes at most one
pass up the tree and at most one pass down, each operation takes O(lg u)
time in the worst case.
● Superimposing a tree of constant height
Figure-2 Constant height tree with summary vectors
4
k
Let us assume that the size of the universe is u = 22 for some integer
k, so that √u is an integer. Instead of superimposing a binary tree on
top of the bit vector, we superimpose a tree of degree u. The height of
the resulting tree is always 2. As before, each its sub-internal node
stores the logical-or of the bits within tree, so that the √u internal
nodes at depth 1 summarize each group of √u values. We can think of
these nodes as an array, where summary[0.. √u − 1 ] contains a 1 if and
√u − 1 ] contains a 1. We call this
only if the subarray A[i √u ..(i+1) √u
-bit subarray of A the ith cluster. For a given value of x, the bit A[x]
appears in cluster number f loor(x/√y ) . Now INSERT becomes an O(1) time
operation: to insert x, set both A[x] and summary[ f loor(x/√y ) ] array to 1.
We can use the summary array to perform each of the operations MINIMUM,
MAXIMUM, SUCCESSOR, PREDECESSOR, and DELETE in O( √u ) time:
➔ To find the minimum value, find the leftmost entry in summary that
contains a 1.
➔ To find the successor of x, first search to the right within its
cluster. If we find a 1, that position gives the result. Otherwise,
let i = f loor(x/√y ) and search to the right within the summary array
from index i. The first position that holds a 1 gives the index of
a cluster. Search within that cluster for the leftmost 1. That
position holds the successor.
➔ To delete the value x, let i = f loor(x/√y ) . Set A[x] to 0 and then set
summary[i] to the logical-or of the bits in the ith cluster.
In each of the above operations, we search through at most two clusters
of √u bits plus the summary array, and so each operation takes O(√u)
time.
● Proto van Emde Boas Tree
Now we modify the idea of superimposing a tree of degree √u on top of
a bit vector. Previously, we used a summary structure of size √u , with
each entry pointing to another structure of size √u . Now, we make the
structure recursive, shrinking the universe size by the square root at
each level of recursion. Starting with a universe of size u, we make
structures holding √u = u1/2 items, which themselves hold structures of
u1/4 items, which hold structures of u1/8 items, and so on, down to a base
size of 2.
5
Some Utility Functions for proto van Emde Boas Tree:
high(x) = f loor(x/√u)
low(X) = x mod √u
index(x, y) = x√u + y
So for the universe {0, 1, 2, . . . , u − 1 } we define a proto van Emde Boas
structure, or proto-vEB structure, which we denote as proto-vEB(u),
recursively as follows. Each proto-vEB(u) structure contains an
attribute u giving its universe size. In addition, it contains the
following:
k
● If u = 22 , then it is the base size, and it contains an array
A[0...1] of two bits.
k
● Otherwise, u = 22 for some integer k ≥ 1, so that u ≥ 4. In
addition to the universe size u, the data structure proto-vEB(u)
contains the following attributes.
1. a pointer named summary to a proto-vEB( √u ) structure and
2. an array cluster[0.. √u − 1 ] of √u pointers, each to a
proto-vEB(u)structure.
The element x, where 0 ≤ x < u, is recursively stored in the cluster
numbered high(x) as element low(x) within that cluster.
In the two-level structure of the previous section, each node stores a
summary array of size √u , in which each entry contains a bit. From the
index of each entry, we can compute the starting index of the subarray
of size √u that the bit summarizes. In the proto-vEB structure, we use
explicit pointers rather than index calculations. The array summary
contains the summary bits recursively in a proto-vEB structure, and the
array cluster contains √u pointers.
The below given figure shows a fully expanded proto-vEB(16) structure
representing the set {2, 3, 4, 5, 7, 14, 15}. If the value i is in the
proto-vEB structure pointed to by summary, then the ith cluster contains
some value in the set being represented. As in the tree of constant
height, cluster[i] represents the values i √u through (i+1) √u − 1 which
form the ith cluster.
At the base level, the elements of the actual dynamic sets are stored in
some of the proto-vEB(2) structures, and the remaining proto-vEB(2)
structures store summary bits. Beneath each of the non-summary base
structures, the figure indicates which bits it stores. For example, the
proto-vEB(2) structure labeled “elements 6,7” stores bit 6 (0, since
element 6 is not in the set) in its A[0] and bit 7 (1, since element 7
is in the set) in its A[1].
6
Figure-3 van Emde Boas tree for a set of range 16.
Like the clusters, each summary is just a dynamic set with universe size
u, and so we represent each summary as a proto-vEB(2) structure. The
four summary bits for the main proto-vEB(16) structure are in the
leftmost proto-vEB(4) structure, and they ultimately appear in two
proto-vEB(2) structures. For example, the proto-vEB(2) structure labeled
“clusters 2,3” has A[0] = 0, indicating that cluster 2 of the
proto-vEB(16) structure (containing elements 8, 9, 10, 11) is all 0,
and A[1] = 1, telling us that cluster 3 (containing elements 12,13,14,
15) has at least one 1. Each proto-vEB(4) structure points to its own
summary, which is itself stored as a proto-vEB(2) structure. For
example, look at the proto-vEB(2) structure just to the left of the one
labeled “elements 0,1.” Because it’s A[0] is 0, it tells us that the
7
“elements 0,1” structure is all 0, and because its A[1] is 1, we know
that the “elements 2,3” structure contains at least one 1.
● van Emde Boas Tree
The proto-vEB structure of the previous section is close to what we need
to achieve O(lg(lg u)) running times.It falls short because we have to
recurse too many times in most of the operations.
So Some important utility functions are:
high(x) = f loor(x/ ↓ √u)
low(X) = x mod ↓ √u
index(x, y) = x ↓ √u + y
The van Emde Boas tree, or vEB tree, modifies the proto-vEB structure.
We denote a vEB tree with a universe size of u as v EB(u) and, unless u
equals the base size of 2, the attribute summary points to a v EB( ↓ √u )
tree and the array cluster[0.. ↑ √u − 1 ] points to ↑ √u v EB( ↓ √u ) trees. A
vEB tree contains two attributes not found in a proto-vEB structure:
● min stores the minimum element in the vEB tree, and
● max stores the maximum element in the vEB tree.
Furthermore, the element stored in min does not appear in any of the
recursive v EB( ↓ √u ) trees that the cluster array points to. The
elements stored in a vEB(u) tree V , therefore, are V.min plus all the
elements recursively stored in the v EB( ↓ √u ) trees pointed to by
V.cluster[0.. ↑ √u − 1 ]. When a vEB tree contains two or more elements, we
treat min and max differently: the element stored in min does not appear
in any of the clusters, but the element stored in max does.
Since the base size is 2, a vEB(2) tree does not need the array A that
the corresponding proto- vEB(2) structure has. Instead, we can determine
its elements from its min and max attributes. In a vEB tree with no
elements, regardless of its universe size u, both min and max are NIL.
8
The min and max attributes will turn out to be key to reducing the
number of recursive calls within the operations on vEB trees. These
attributes will help us in four ways:
● The MINIMUM and MAXIMUM operations do not even need to recurse, for
they can just return the values of min or max.
Figure-4 vEB Tree single node structure
● The SUCCESSOR operation can avoid making a recursive call to
determine whether the successor of a value x lies within high.x/.
That is because x’s successor lies within its cluster if and only
if x is strictly less than the max attribute of its cluster. A
symmetric argument holds for P R E D E C E S S O R and min.
● We can tell whether a vEB tree has no elements, exactly one
element, or at least two elements in constant time from its min and
max values. This ability will help in the INSERT and DELETE
operations. If min and max are both NIL, then the vEB tree has no
elements. If min and max are non-NIL but are equal to each other,
then the vEB tree has exactly one element. Otherwise, both min and
max are non-NIL but are unequal, and the vEB tree has two or more
elements.
● If we know that a vEB tree is empty, we can insert an element in to
it by updating only its min and max attributes. Hence, we can
insert into an empty vEB tree in constant time. Similarly, if we
know that a vEB tree has only one element, we can delete that
element in constant time by updating only min and max. These
properties will allow us to cut short the chain of recursive calls.
9
Even if the universe size u is an odd power of 2, the difference in the
sizes of the summary vEB tree and the clusters will not turn out to
affect the asymptotic running times of the vEB-tree operations. The
recursive procedures that implement the vEB-tree operations will all
have running times characterized by the recurrence.
T (u) ≤ T (↓ √U ) + O(1)
Operations on van Emde Boas Tree:
vEB-Tree-MIN(V)
return V.min
vEB-Tree-MAX(v)
return V.max
vEB-Tree-SUCCESSOR(V, x)
if V.u == 2
if x == 0 and V:max == 1
return 1
else return NIL
elseif V:min != NIL and x < V:min
return V:min
else max-low = vEB-Tree-MAX([V.cluster(high(x)])
if max-low != NIL and low(x) < max-low
offset = vEB-Tree-SUCCESSOR(V.cluster[high(x)], low(x))
return index(high(x),offset)
else succ-cluster = vEB-Tree-SUCCESSOR(V.summary(high(x))
if succ-cluster == NIL
return NIL
else offset = vEB-Tree-MIN(V.cluster[succ-cluster])
return index(succ-cluster,offset)
vEB-EMPTY-TREE-INSERT(V,x)
V.min = x
V.max = x
10
vEB-TREE-INSERT(V,x)
if V.min == NIL
vEB-EMPTY-TREE-INSERT(V,x)
else if x < V.min
exchange x with V.min
if V.u > 2
if vEB-Tree-MIN(V.cluster(high.x)) == NIL
vEB-TREE-INSERT(V.summary,high(x))
vEB-EMPTY-TREE-INSERT(V,cluster[high(x)],low(x))
else VEB-TREE-INSERT(V.cluster[high.x],low(x))
if x > V:max
V:max=x
Complexities obtained with augmented Bit Arrays as superimposed binary
trees called van Emde Boas
Figure-5 Complexities comparison
11
Dijkstra's Algorithm to find the Shortest Path
Dijkstra’s algorithm solves the single-source shortest-paths problem on
a weighted, directed/undirected graph G = (V,E) for the case in which
all edge weights are nonnegative.
There will also be no cycles as a cycle would define more than one path
from the selected vertex to at least one other vertex. For a graph,
● V is a set of vertices
● E is a set of edges
● G = (V,E) graph defines a set.
Dijkstra's algorithm keeps two sets of vertices:
S = the set of vertices whose shortest paths from the source have
already been determined and
V - S = remaining vertices
eeded are:
Other data structures n
d = array of shortest path to each vertex
pi = array of predecessors for each vertex.
The basic mode of operation is:
1. Initialise d and pi,
2. Set S to empty,
3. While there are still vertices in V-S,
a. Sort the vertices in V-S according to the current best
estimate of their distance from the source,
b. Add u, the closest vertex in V-S, to S,
c. Relax all the vertices still in V-S connected to u
Relaxation:
The relaxation process updates the costs of all the vertices, v,
connected to a vertex, u, if we could improve the best estimate of the
shortest path to v by including (u,v) in the path to v.
The relaxation procedure proceeds as follows:
initialise_single_source( Graph g, Node s )
for each vertex v in Vertices( g )
g.d[v] := infinity
g.pi[v] := nil
g.d[s] := 0;
12
This sets up the graph so that each node has no predecessor (pi[v] =
nil) and the estimates of the cost (distance) of each node from the
source (d[v]) are infinite, except for the source node itself (d[s] =
0).
The relaxation procedure checks whether the current best estimate of the
shortest distance to v (d[v]) can be improved by going through u (i.e.
by making u the predecessor of v):
relax( Node u, Node v, double w[][] )
if d[v] > d[u] + w[u,v] then
d[v] := d[u] + w[u,v]
pi[v] := u
The algorithm itself is now:
shortest_paths( Graph g, Node s )
initialise_single_source( g, s )
S := { 0 } /* Make S empty */
Q := Vertices( g ) /* Put the vertices in a PQ */
while not Empty(Q)
u := Extract-MIN( Q );
AddNode( S, u ); /* Add u to S */
for each vertex v in Adjacent( u )
relax( u, v, w )
III. Analysis of Dijkstra’s Algorithm:
It maintains the min-priority queue Q by calling three priority-queue
operations:
● INSERT
● EXTRACT-MIN
● DECREASEKEY
The algorithm calls both INSERT and EXTRACT-MIN once per vertex. As each
vertex u ∈ V is added to set S exactly once, each edge in the adjacency
u ] is examined in the for loop of lines 8-9 exactly once
list Adj[
during the course of the algorithm. Since the total number of edges in
all the adjacency lists is jEj, this for loop iterates a total of |E|
times, and thus the algorithm calls DECREASE-KEY at most |E| times
overall. The running time of Dijkstra’s algorithm depends on how we
implement the min-priority queue.
13
● Implementation of Dijkstra Using Van Emde Boas Tree
To gain improvements we implement the min-priority queue using vEB tree.
As we know vEB tree provides the find minimum operation in O(1) time and
we can find the successor in O(lg(lg U)) time so we replace the
extract-min and decrease-key operations with findMinimum and get-
successor operation of vEB tree.
Instead of searching for the minimum element in the priority queue and
removing it we instead get the minimum element in the vEB tree and get
its successor in lesser time.
The advantages of vEB tree is that for input graphs where we have the
weights in such an order that we span most of the values in the range
{0,1,2...u-1} vEB tree gives the best running time.
The VEB tree method is bad though for sparse graphs where we do not
cover most of the values in the range {0,1,2,...n-1} as the overhead to
manage the time and space of the tree is too much as compared to a
priority queue.
To implement a priority queue we used
● RED BLACK TREE
● AVL TREE
By using a balanced height tree data structure we limit the range of the
here N is the number of
values of all the tree operations to O(log N) w
elements in the tree.
The AVL tree supports all the operations such as insert, delete,
Extract-Min in O(logN) time.
The Red Black tree is an even more sophisticated data structure which
also supports these operation in O(logN) time but the advantage of Red
Black Tree is that that it supports the rotation of tree on dis
balancing in O(1) time as compared to AVL Tree which does the same in
O(logN) rotate operations in worst case.
14
Figure-6 Red Black Tree vs vEB Tree
15
Figure-7 AVL Tree vs vEB Tree
IV. GITHUB REPOSITORY
https://github.com/paliwal-jatin/APS_project
V. References
● NPTEL
“https://www.youtube.com/watch?v=_KgllZVMshg”
● Stanford CS166 course materials
“http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/14/Slide
s14.pdf”
● Wikipedia
“https://en.wikipedia.org/wiki/Van_Emde_Boas_tree”
● GeeksforGeeks
“https://www.geeksforgeeks.org/proto-van-emde-boas-trees-set-1-background-introduct
ion/”
● Introduction to Algorithms 3rd Edition Thomas H. Cormen
