Solution for Binary Search Tree with Range Minimum Queries

22nd Jan 2024
10:39 am
Admin

Java Assignment Question

For this assignment, we are to create insert-only Binary Search Tree. Each node will contain:
class Node
{
int key;
int data;
int mindata;
Node *left, *right, *parent;
};

The goal is to compare two methods for computing RMQs. And compare their times for different data sizes of 3000, 10000, and 30000. What is an RMQ ?

Java Assignment Solution

import java.io.File;
import java.util.Scanner;
import java.io.FileNotFoundException;

class Node {
int key;
int data;
int minData;
Node left, right, parent;

public Node(int Key, int Data) {
key = Key;
data = Data;
}
}

public class BST {
static void SetMinData(Node root) {
if (root != null) root.minData = root.data;
if (root.left != null) root.minData = Math.min(root.minData, root.left.minData);
if (root.right != null) root.minData = Math.min(root.minData, root.right.minData);
}

static Node insert(Node root, int key, int data) {
if (root == null) {
root = new Node(key, data);
root.minData = data;
return root;
}
if (key < root.key) {
root.left = insert(root.left, key, data);
}
else if (key > root.key) {
root.right = insert(root.right, key, data);
}
SetMinData(root);
//System.out.print(elapsed + ",\n");
return root;
}
static int min = 10000;
static Node root = null;

// Method 1
public static void insertNaive(int k1, int k2, Node root) {
if (root == null) return;
if (root.key >= k1) insertNaive(k1, k2, root.left);
if (root.key <= k2) insertNaive(k1, k2, root.right);
if ((root.key >=k1) && (root.key <= k2)) min = Math.min(min, root.data);

}

// Method 2
static int optimizedRMQ(int k1, int k2, Node root) {
while (!(k1 <= root.key && root.key <= k2))
if (k1 < root.key && k2 < root.key)
if (root.left != null) root = root.left;
else if (root.right != null) root = root.right;

int min = RMRight(k1, root.left);
int min2 = RMLeft(k2, root.right);
return Math.min(min, min2);
}

static int RMRight(int k1, Node root) {
int min = root.data;
if (k1 < root.key && root.right != null) {
min = Math.min(min, root.right.minData);
RMRight(k1, root.left);
}
else if (k1 > root.key && root.right != null) RMRight(k1, root.right);
else if (root.right != null) min = Math.min(min, root.right.minData);
return min;
}

static int RMLeft(int k2, Node root) {
int min = root.data;
if (k2 < root.key && root.right != null) {
min = Math.min(min, root.left.minData);
RMRight(k2, root.right);
}
else if (k2 > root.key && root.right != null) RMRight(k2, root.left);
else if (root.right != null) min = Math.min(min, root.left.minData);
return min;
}


public static void main(String[] args) throws FileNotFoundException {
File in = new File("inputFile.txt");
try (Scanner scan = new Scanner(in)) {
           int numInstructions = 0;
           if (scan.hasNextLine()) numInstructions = Integer.parseInt(scan.nextLine());
           String firstInstruction = scan.nextLine();
           String[] firstSplit = firstInstruction.split("\\s");
           root = insert(null, Integer.parseInt(firstSplit[1]), Integer.parseInt(firstSplit[2]));
           while (numInstructions >= 1 && scan.hasNextLine()) {
           String instructions = scan.nextLine();
           String[] split = instructions.split(" ");
           if (split[0].equals("IN")) BST.insert(BST.root, Integer.parseInt(split[1]), Integer.parseInt(split[2]));
           else if (split[0].equals("RMQ")) min = BST.optimizedRMQ(Integer.parseInt(split[1]), Integer.parseInt(split[2]), BST.root);
           numInstructions--;
           }
       } catch (NumberFormatException e) {
           // TODO Auto-generated catch block
           e.printStackTrace();
       }