3. This problem is concerned with the range queries on a binary search tree T wh

Question

3. This problem is concerned with the range queries on a binary search tree T whose keys are real numbers. Let h denote the height of T. The range query is a generalization of the normal search operation. The range of a range query on T is defined by a pair [x,x], where x and xr are real numbers and xi S xr. Note that xi and xr need not be the keys stored in T. (20 points) You are asked to design an algorithm to perform the following range queries on T. That is, given a range [xixr], design an O(h + k) time algorithm for the range-report(x, xr) operation on T: reporting all keys x in T such that x SxSxr, where k is the number of keys of T in the range [XI, Xr] (i.e., k is the size of the output of the query, and thus this is also an output-sensitive algorithm). Further, it is required that all keys in the range [x,xr] be reported in a sorted order.

Explanation / Answer

the algo works by traversing the tree starting from root. for each node being visited if node is in the given range print the node and then follow the same process for child nodes

getnodes is a function that takes 3 parameters first is root node and then last 2 parameters are range k1 and k2

start

getNodes (node, k1, k2)

if node is node is null just return

else if the node.data >=k1 and node.data <= k2

getnodes(node.left, k1,k2)

print node.data

getnodes(node.right, k1, k2)

else if node.data <k1

getnodes(node.right,k1,k2)

else getnodes(node.left, k1, k2)

end

below is the java code for the same

class Node {

int data;

Node left, right;

public Node(int item) {

data = item;

left = right = null;

}

}

class BST{

private Node root;

  

public static void main(String[] args) {

BST tree = new BST();

int k1=5;

int k2=45;

tree.root = new Node(10);

tree.root.left = new Node(5);

tree.root.right = new Node(55);

tree.root.left.left = new Node(1);

tree.root.right.left = new Node(30);

tree.root.right.right = new Node(100);

tree.getNodes(tree.root,k1, k2);

}

public BST() {

root = null;

}

void getNodes(Node node, int k1, int k2)

{

if(node == null) //if current node is null just return

return;

if(node.data>=k2 && node.data<=k2) {

// if current node is between the range call the getNodes() on left subtree then print

//print the current node value and call the getNodes() on right subtree

this.getNodes(node.left, k1, k2);

System.out.print(node.data+" ");

this.getNodes(node.right, k1, k2);

}

else if(node.data<k1)//if current node is less than k call getnodes() on right subtree

this.getNodes(node.right, k1, k2);

else //else call getnodes on left subtree

this.getNodes(node.left, k1, k2);

}

}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.