I need java code of binary search tree time complexity. I have two input files.
ID: 3597847 • Letter: I
Question
I need java code of binary search tree time complexity. I have two input files.
Sample: few items I giving.
File1:
21,,Mixed Seasonal
93,,the edition
123,,toshibha dvd player
2144209103,VHS,Tintorera - Tiger Shark
This file having 3 fields first key, second description and third data. From this file you have it should read the field1 key. (separed by commas)
File2:
21 Mixed Seasonal
93 the edition
123 toshibha dvd player
161 Dillons/Kroger Employee Coupon ($1.25 credit)
178 Outdoor Bag
1090 VAR Rountech Asset 1
1205 1gal GIANT NATURAL MOUNTAIN SPRING
From this file it has search the key field from file1 (21, 93 ....etc) and print key and description and data( and also total time taken to search)
Please explain with input and output sceen shot and also use more comments to understand. Thanks in advance. The formal question also giving down.
Implement Search (T data) to search for a node having value of key = data in a Binary Search Tree.
Use the Binary Search Tree to build a search tree using the given input file1 that consists of three fields: a key, the corresponding description, and data. Use the search tree created to find the description associated with a given set of keys. The input file file2 provides the key and corresponding descriptions and data in a comma separated file and the various search keys are provided in the file input1. test the program for the given search keys and determine the total time taken to complete the search.
I am asking my times because the code is not compliling which i got. I need code for binary search tree and time taken to complete the search.
Explanation / Answer
The java code is:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
/*
Class to represent a node of a tree
*/
class BinarySearchTree {
long key;
String data;
BinarySearchTree left;
BinarySearchTree right;
public BinarySearchTree(long key, String data) {
this.key = key;
this.data = data;
this.left = null;
this.right = null;
}
}
/*
Runner Class with main
*/
public class BinarySearchTreeTimeCom {
public static ArrayList<Long> keyArr = new ArrayList<>();
public static BinarySearchTree root = null;
/*
Function to insert node in Binary search tree
*/
public static void insertInTree(BinarySearchTree t1) {
if(root == null) {
root = t1;
return;
}
BinarySearchTree temp = root, prev = null;
while(temp != null) {
if(temp.key > t1.key) {
prev = temp;
temp = temp.left;
} else if(temp.key < t1.key) {
prev= temp;
temp = temp.right;
}
}
if(temp == null) {
if(t1.key < prev.key) {
prev.left = t1;
} else {
prev.right = t1;
}
} else {
System.out.println("Could not insert in thr tree");
}
}
/*
Function to search for a key in binary search tree.
Time complexity = binary search tree time complexity = O(logn) and worst case being O(n)
*/
public static void searchInTree (long key) {
if (root == null) {
System.out.println(key + ": Tree is empty");
}
BinarySearchTree temp = root;
while(temp != null) {
if(temp.key == key) {
System.out.println(key + ": " + temp.data);
break;
} else if (temp.key > key) {
temp = temp.left;
} else {
temp = temp.right;
}
}
if (temp == null) {
System.out.println(key + ": Data not found for this key");
}
}
public static void main(String[] args) {
try {
//Read the contents of the first file
File file1 = new File("D:/Personal/Chegg/test.txt");
FileReader fileReader = new FileReader(file1);
BufferedReader bufferedReader = new BufferedReader(fileReader);
String line;
while ((line = bufferedReader.readLine()) != null) {
//store the keys into a arraylist
String[] tokens = line.split(",",2);
keyArr.add(Long.parseLong(tokens[0]));
}
fileReader.close();
/*System.out.println("Contents of file:");
System.out.println(keyArr.toString());*/
} catch (IOException e) {
e.printStackTrace();
}
try {
//Read the contents of the second file which has to be searched according to keys of first file
File file1 = new File("D:/Personal/Chegg/test2.txt");
FileReader fileReader = new FileReader(file1);
BufferedReader bufferedReader = new BufferedReader(fileReader);
String line;
while ((line = bufferedReader.readLine()) != null) {
//Store the key and data corresponding to it in the tree
String[] tokens = line.split(" ",2);
BinarySearchTree n1 = new BinarySearchTree(Long.parseLong(tokens[0]), tokens[1]);
insertInTree(n1);
}
fileReader.close();
} catch (IOException e) {
e.printStackTrace();
}
//for each element in the keys array search the tree for corresponding data and print
System.out.println("Data contents from second file corresponding to keys in first file:");
for (long key: keyArr) {
searchInTree(key);
}
}
}