Data Structures Homework Help on Range Queries

1.

Building a Min heap in O(n) time: Since it is observed that the running time of the
Heapify algorithm depends on the height of the tree h and also height of most
sub-trees is small. So it is considered as O(h) and at height ‘h’ at most n/2^
h+1

nodes are there. So making the time as summation of O(h)* n/2

h+1 where h runs
from 0 to log(n). After analysis it is learned that the time becomes O(n).
Since k minimum elements are required, applying exact min k times will gives k
minimum elements in increasing order.
Sincy extract min takes O(log n) time and performs it for k times. So it takes
k(log n) time.
To build heap it is O(n ) and k min elements it is O(k log n) which makes the total
time as O(n+k log n).

2.
a. RangeCount(k1, k2) : Rank(k2,r) - Rank(k1,r) + 1, where rank is the height of the
node from the root. It takes O(log n) time.
b. Let r be the root node and key is the value in any node,

RangeReport_new(k1,k2,r) {
if(k1 < r.key) and (k2 > r.key) {
RangeReport_new(k1,k2,r->left);
print(r);
RangeReport_new(k1,k2,r->right);
}
else if(k1 < r.key) and (k2 < r.key) {
RangeReport_new(k1,k2,r->left);
}
else if(k1>r.key) and (k2 > r.key) {
RangeReport_new(k1,k2,r->right);
}
else if (k1=r){
print(r);
RangeReport_new(k1,k2,r->right);
}
else if (k2=r){
RangeReport_new(k1,k2,r->left);
print(r);
}
}

The above solution won't check subtree where no nodes satisfying will be found.
It will traverse the part of the tree which falls between two paths p1 and p2 :where p1=
root to k1 and p2= root to k2. Within this part every edge is traversed at most once in

upward motion and once in downward motion. For traversing p1 and p2, it takes at most
O(log n) because both the paths are O( log n)

c. Keep a field called mindata in each node x, which stores the minimum data
value in the subtree of x.

SetMindata(r){
if (r != null ) r->mindata = r->data
if (r->left != null)
r->mindata = min(r->mindata, r->left->mindata);
if (r->right != null)
r->mindata = min(r->mindata, r->right->mindata);
}
Modify rotate as:
Node * Rrotate(Node * x) {
y=x->left;
y->parent = x->parent;
x->parent= y;
x->left = y->right;
y->right = x;
SetMindata(x);
SetMindata ;
return ;
}
Modify insert as:
insert(Node * x, Node *k) {
if (x != null) {
x=k;
x->Mindata = x->data;
}
else if (x->key key){
x->Mindata = min(x->Mindata, k->data);
insert(x->right, k);
}
else{
x->Mindata = min(x->Mindata, k->data);
insert(x->left, k);
}
}

Thus consistently min value is maintained. Now we can report rangemin by
modifying range report procedure:
Global variable Min;

RangeMin (k1,k2,r){
x=r;
while (! (k1 <= x->key <= k2) ) {
if (k1 and k2 are less than x) x=x->left;
else ( x=x->right);
} //now we are at a node x from where k1 and k2 fall in different subtrees
Min= x->data;
RangeMinRight(k1,x->left);
RangeMinLeft(k2,x->right);
}
RangeMinRight(k1,r) {
if (k1 < r) {
Min = min(Min, r->data, r->right->Mindata);
RangeMinRight(k1,r->left);
}
else if (k1 > r)
RangeMinRight(k1,r->right);
else
Min= min(Min, r->data, r->right->Mindata);

}
RangeMinLeft(k2,r)
{
if (k2 < r) {
Min = min(Min, r->data, r->left->Mindata);
RangeMinLeft(k2,r->right);
}
else if (k2 > r)
RangeMinLeft(k2,r->left);
else
Min= min(Min, r->data, r->left->Mindata);

}

First we find the lowest common ancestor, x of k1 and k2 and consider two paths
from x to k1 and x to k2.
Traverse x to k1 using RangeMinRight function and and take min of every
subtree value falling on right. In the same way from x to k2 using the
RangeMinLeft function and taking min of every subtree value falling to right.

3.
a. Start with an empty queue Q
b. Push root into into Q using Insert_last
c. While Q is not empty:
i. Pop the element from Q using delete first and print its data
ii. Add its left and right child to Q if exists
Continue above until loop ends i.e Q becomes empty