Java Assignment Solution - Binary Search Tree with Range Minimum Queries (RMQs)

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();
        }
       

        System.out.print(min + "\n"); 
    }
}

 

Explaination

Here are some estimation on random datas

 

For 1000 :

1. Method 1 take 2 sec
2. Method 2 takes 1 sec

For 2000:

1. Method 1 take 3 sec
2. Method 2 takes 1 sec

For 3000 :

3. Method 1 take 4 sec
4. Method 2 takes 2 sec

For 10000:

3. Method 1 take 7 sec
4. Method 2 takes 3 sec

For 30000 :

5. Method 1 take 13 sec
6. Method 2 takes 6 sec

Using the data of 3000, 10000, 30000, we get the following graph.