Question

Using Java,

Load the data provided below as text file using binary tree algorithm.

Create two methods, remove, and search, of a binary search tree.

The search method shall allow a search by salary. It should display the matched salary and the associated name. Otherwise return not found message.

The delete method shall delete the object that matched the search criteria, search by name.

Name	Salary
Betty	44000
Bob	48000
Dilbert	98000
Joseph	22300
Nathan	90000
Sally	91000
Sam	87000
Susan	8900
Veronica	150000

Answer 1

Note - To search by both name and salary, 2 different Binary trees will be created to correspond for the required search key.

All further explanation is in the code comments. Hope this helps!

Code:

import java.util.*;
import java.io.*;

// class to store individual employees
class Employee
{
public String name;
public int salary;
  
// constructors
Employee(String name, int salary)
{
this.name = name;
this.salary = salary;
}
Employee(Employee employee)
{
this.name = employee.name;
this.salary = employee.salary;
}
}

// class to store BST for employees
class Tree
{
public Employee val;
public Tree right, left;
// constructor
Tree(Employee val)
{
this.val = new Employee(val);
this.right = null;
this.left = null;
}
}

// Main class
public class Main
{
// add data to tree where data is stored by name
public static Tree addData1(Tree root, Employee employee)
{
// end of tre
if(root == null)
{
root = new Tree(employee);
}
// add to right of tree if greater
else if(root.val.name.compareTo(employee.name)<0)
{
root.right = addData1(root.right, employee);
}
else // else left of tree
{
root.left = addData1(root.left, employee);
}
return root;
}
  
// add data to tree where data is stored by salary
public static Tree addData2(Tree root, Employee employee)
{
// end of tree
if(root == null)
{
root = new Tree(employee);
}
// add to right of tree if greater salary
else if(root.val.salary < employee.salary)
{
root.right = addData2(root.right, employee);
}
else // else left of tree
{
root.left = addData2(root.left, employee);
}
return root;
}
  
// get the minimum value of tree -> leftmost leaf
public static Employee minValue(Tree root)
{
Employee minv = root.val;
while (root.left != null)
{
minv = root.left.val;
root = root.left;
}
return minv;
}
  
// overloaded function
// search by salary
public static void search(Tree root, int salary)
{
// reached end of tree, but salary not found
if(root == null)
{
System.out.println("Salary: " + salary + " not found");
return;
}
if(root.val.salary == salary)
{
System.out.println("Name: " + root.val.name + ", Salary: " + root.val.salary);
}
else if(root.val.salary < salary)
{
search(root.right, salary);
}
else
{
search(root.left, salary);
}
}
  
// overloaded function
// search by name
public static Employee search(Tree root, String name)
{
// reached end of tree, but name not found
if(root == null)
{
System.out.println("Name: " + name + " not found");
return null;
}
if(root.val.name.equals(name))
{
System.out.println("Removing node - " + root.val.name + ", " + root.val.salary);
// return the nodeToBeDeleted
return root.val;
}
else if(root.val.name.compareTo(name) < 0)
{
return search(root.right, name);
}
else
{
return search(root.left, name);
}
}
  
// remove data from tree where search is by name
public static Tree remove(Tree root, String name)
{
if(root == null)
return root;
  
if(root.val.name.equals(name))
{
if (root.left == null)
root = root.right;
else if (root.right == null)
root = root.left;
else
{
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.val = minValue(root.right);
  
// Delete the inorder successor
root.right = remove(root.right, root.val.name);
}
}
else if(root.val.name.compareTo(name) < 0)
{
root.right = remove(root.right, name);
}
else
{
root.left = remove(root.left, name);
}
return root;
}
  
// remove data from tree where search is by salary
public static Tree remove(Tree root, int salary)
{
if(root == null)
return root;
  
if(root.val.salary == salary)
{
if (root.left == null)
root = root.right;
else if (root.right == null)
root = root.left;
else
{
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.val = minValue(root.right);
  
// Delete the inorder successor
root.right = remove(root.right, root.val.salary);
}
}
else if(root.val.salary < salary)
{
root.right = remove(root.right, salary);
}
else
{
root.left = remove(root.left, salary);
}
return root;
}
  
   public static void main(String[] args) {
  
   // try to open file
   try {
  
   // input stream
       Scanner sc = new Scanner(new File("input.txt"));
       String name;
       int salary;
       Tree rootbyName = null, rootbySalary = null;
       Employee tmp;
      
       // read data from file
       while (sc.hasNext()) {
       name = sc.next();
       salary = sc.nextInt();
       // add to the 2 trees
       rootbyName = addData1(rootbyName, new Employee(name, salary));
       rootbySalary = addData2(rootbySalary, new Employee(name, salary));
       }
       // close stream
       sc.close();
      
       // sample run ------------------------------------------------------
       // search for salary = 87000
       search(rootbySalary, 87000);
       // delete the Employee with name Sam
       tmp = search(rootbyName, "Sam");
       if(tmp!=null)
       {
       // Delete from both trees
       rootbyName = remove(rootbyName, tmp.name);
       rootbySalary = remove(rootbySalary, tmp.salary);
       }
       // again search for salary = 87000
       search(rootbySalary, 87000);
      
   } catch (IOException e) {
   System.out.println("Unable to open file");
   }
   }
}

Sample run:

Name: Sam, Salary: 87000 Removing node - Sam, 87000 Salary: 87000 not found

Code screenshots:

i import java.util.*; 2 import java.io.*; 4 5 6 - // class to store individual employees class Employee { public String name; public int salary; // constructors Employee(String name, int salary) this.name = name; this.salary = salary; Employee(Employee employee) this.name = employee.name; this.salary = employee.salary; 21 } 22 23 // class to store BST for employees 24 class Tree 25 - { public Employee val; public Tree right, left; // constructor Tree (Employee val) this.val = new Employee (val); this.right = null; this.left = null; 35 } 36 37 // Main class 38 public class Main 39- { 40 // add data to tree where data is stored by name public static Tree addDatal(Tree root, Employee employee) 42- // end of tre ant

if(root == null) root = new Tree (employee); // add to right of tree if greater else if(root.val.name.compareTo(employee.name)<), root.right = addDatal(root.right, employee); else // else Left of tree root.left = addDatal(root.left, employee); return root; // add data to tree where data is stored by salary public static Tree addData2(Tree root, Employee employee) // end of tree if(root == null) root = new Tree (employee); // add to right of tree if greater salary else if(root.val.salary < employee.salary) root.right = addData(root.right, employee); else // else Left of tree root.left = addData(root.left, employee); return root; Il get the minimum value of tree -> Leftmost Leaf public static Employee minValue (Tree root) Employee minv = root.val; while (root.left != null) minv = root.left.val;

root = root.left; return minv; // overloaded function // search by salary public static void search(Tree root, int salary) // reached end of tree, but salary not found if(root == null) System.out.println("Salary: " + salary + " not found"); return; if(root.val.salary == salary) System.out.println("Name: " + root.val.name + ", Salary: " + root.val.salary); else if(root.val.salary < salary) search(root.right, salary); else search(root.left, salary); 98 99 100 101 102 103 104 105 106 107 108 109 110 111 - 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 // overloaded function // search by name public static Employee search (Tree root, String name) // reached end of tree, but name not found if(root == null) System.out.println("Name: " + name + " not found"); return null; if(root.val.name.equals(name)) System.out.println("Removing node - " + root.val.name + ", " + root.val.salary); // return the nodeToBeDeleted

return root.val; 130 131 132 133 134 else if(root.val.name.compareTo(name) < 0) return search(root.right, name); else return search(root.left, name); } // remove data from tree where search is by name public static Tree remove(Tree root, String name) if(root == null) return root; if(root.val.name.equals(name)) 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 if (root.left == null) root = root.right; else if (root.right == null) root = root.left; else // node with two children: Get the inorder successor (smallest // in the right subtree) root.val = minValue(root.right); // Delete the inorder successor root.right = remove(root.right, root.val.name); else if(root.val.name.compareTo(name) < 0) root.right = remove(root.right, name); else root.left = remove(root.left, name); 171 172 return root;

173 174 175 176 // remove data from tree where search is by salary public static Tree remove(Tree root, int salary) 177 178 179 180 if(root == null) return root; 181 if(root.val.salary == salary) 182 183 184 185 186 187 if (root.left == null) root = root.right; else if (root.right == null) root = root.left; else 189 190 191 Il node with two children: Get the inorder successor (smallest // in the right subtree) root.val = minValue(root.right); // Delete the inorder successor root.right = remove(root.right, root.val.salary); 193 194 195 196 197 198 199 200 201 else if(root.val.salary <salary) root.right = remove(root.right, salary); else 202 root.left = remove(root.left, salary); return root; public static void main(String[] args) { 203 204 205 206 207 208 209 210 211 212 213 214 215 Il try to open file try { // input stream Scanner sc = new Scanner(new File("input.txt")); String name;

216 217 218 219 int salary; Tree rootbyName = null, rootbySalary = null; Employee tmp; 220 221 NNNNNNN // read data from file while (sc.hasNext() { name = sc.next(); salary = sc.nextInt(); // add to the 2 trees rootbyName = addDatal(rootbyName, new Employee (name, salary)); rootbySalary = addData2 (rootbySalary, new Employee (name, salary // close stream sc.close(); 233 234 // sample run -- // search for salary = 87000 search(rootbySalary, 87000); // delete the Employee with name Sam tmp = search(rootbyName, "Sam"); if(tmp!=null) 236 237 238 239 240 241 // Delete from both trees rootbyName = remove(rootbyName, tmp.name); rootbySalary = remove(rootbySalary, tmp.salary); 242 243 // again search for salary = 87000 search(rootbySalary, 87000); 244 245 246 } catch (IOException e) { System.out.println("Unable to open file"); 247 248 249 250