## Data Structures Homework Help on Range Queries

- 8th Jul, 2022
- 15:28 PM

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