Use the RBTree class to build a search tree using the given input file that consists of two fields: a UPC key and the corresponding description. Use the search tree created to find the description associated with a given set of UPC keys. The input file UPC-random.csv provides the key and corresponding descriptions in a comma separated file and the various search keys are provided in the file input.dat. First test the program by entering couple of keys manually and print the description. Once you are convinced the program is working correctly, test the program for the given search keys and determine the total time taken to complete the search. Below is my Java code and you can edit/ customise as needed. Please also share output screenshots.

package BinaryTrees;

public class RedBlackNode {

RedBlackNode left, right; int element; int color; public RedBlackNode(int theElement) { this( theElement, null, null ); } public RedBlackNode(int theElement, RedBlackNode lt, RedBlackNode rt) { left = lt; right = rt; element = theElement; color = 1; } }

class RBTree { private RedBlackNode current; private RedBlackNode parent; private RedBlackNode grand; private RedBlackNode great; private RedBlackNode header; private static RedBlackNode nullNode;

static { nullNode = new RedBlackNode(0); nullNode.left = nullNode; nullNode.right = nullNode; }

static final int BLACK = 1; static final int RED = 0;

/* Constructor */ public RBTree(int negInf) { header = new RedBlackNode(negInf); header.left = nullNode; header.right = nullNode; } public boolean isEmpty() { return header.right == nullNode; } public void makeEmpty() { header.right = nullNode; } public void insert(int item ) { current = parent = grand = header; nullNode.element = item; while (current.element != item) { great = grand; grand = parent; parent = current; current = item

if (current.left.color == RED && current.right.color == RED) handleReorient( item ); } if (current != nullNode) return; current = new RedBlackNode(item, nullNode, nullNode); if (item

current.color = RED; current.left.color = BLACK; current.right.color = BLACK;

if (parent.color == RED) {

grand.color = RED; if (item

header.right.color = BLACK; } private RedBlackNode rotate(int item, RedBlackNode parent) { if(item

private RedBlackNode rotateWithRightChild(RedBlackNode k1) { RedBlackNode k2 = k1.right; k1.right = k2.left; k2.left = k1; return k2; }

public int countNodes() { return countNodes(header.right); } private int countNodes(RedBlackNode r) { if (r == nullNode) return 0; else { int l = 1; l += countNodes(r.left); l += countNodes(r.right); return l; } } public boolean search(int val) { return search(header.right, val); } private boolean search(RedBlackNode r, int val) { boolean found = false; while ((r != nullNode) && !found) { int rval = r.element; if (val rval) r = r.right; else { found = true; break; } found = search(r, val); } return found; } public void inorder() { inorder(header.right); } private void inorder(RedBlackNode r) { if (r != nullNode) { inorder(r.left); char c = 'B'; if (r.color == 0) c = 'R'; System.out.print(r.element +""+c+" "); inorder(r.right); } } public void preorder() { preorder(header.right); } private void preorder(RedBlackNode r) { if (r != nullNode) { char c = 'B'; if (r.color == 0) c = 'R'; System.out.print(r.element +""+c+" "); preorder(r.left); preorder(r.right); } } public void postorder() { postorder(header.right); } private void postorder(RedBlackNode r) { if (r != nullNode) { postorder(r.left); postorder(r.right); char c = 'B'; if (r.color == 0) c = 'R'; System.out.print(r.element +""+c+" "); } } } //Driver

package BinaryTrees;

import java.util.Scanner;

public class RedBlackTreeDriver { public static void main(String[] args) { Scanner scan = new Scanner(System.in); RBTree rbt = new RBTree(Integer.MIN_VALUE); System.out.println("Red Black Tree Testing "); char ch; do { System.out.println(" Red Black Tree Operations "); System.out.println("1. insert "); System.out.println("2. search"); System.out.println("3. count nodes"); System.out.println("4. check empty"); System.out.println("5. clear tree");

int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter integer to insert"); rbt.insert( scan.nextInt() ); break; case 2 : System.out.println("Enter integer to search"); System.out.println("Search result : "+ rbt.search( scan.nextInt() )); break; case 3 : System.out.println("Nodes = "+ rbt.countNodes()); break; case 4 : System.out.println("Empty status = "+ rbt.isEmpty()); break; case 5 : System.out.println(" Cleared"); rbt.makeEmpty(); break; default : System.out.println("Wrong Entry, reenter "); break; } System.out.print(" Post order : "); rbt.postorder(); System.out.print(" Pre order : "); rbt.preorder(); System.out.print(" In order : "); rbt.inorder();

System.out.println(" Continue (y or n) "); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } } UPC-random.CSV sample screen shot

21120417608 10 oz 14200085101 48 oz 21000651504 16 oz 10300001508 50 lb 15400061919 12300275132 13131081732 One VHS Tape SG CELLO SPINACH 100Z S&S I/O CHRMS FAMILY FUN Parkay Squeezable Diamond inshell mixed nuts Western Family 4-pack of C cell batteries Best Value Men Lt Kings Return To OZ Widescreen Collector's Edition VHS Tape Tannoy Reveal 8D Tastykake Choc Pretzel Rods Milkbone Biscit Tartar Control Myst III - Exile (PC) from UBI SOFT ENTERTAINMENT PUR LEMON GOLD FILLING Oval Emotion Reach Out - CD Zagat Survey 2007 New York City Young Frankenstein SHPR FOOD CHOPPER KRAFT NY SHARP CHEDDAR PP LADY LEE BEEF BROTH IAM'S 3 OZ. C.F. Joseph And The Coat Of Many Colors Kroger Glucosamine&Chondroitin FW CLASSIC 7" STRAINER Individual Resume Maker Deluxe 2001 SKINLESS CHICKEN TENDERLOINS Thomas And Friends: Best Of Percy 0.05037411 0.11308556 0.68537997 0.6753737 0.13326981 0.75889672 0.50864656 0.53131274 0.82856474 0.3315569 0.96463522 0.73600305 0.92716368 0.52449118 0.66695527 0.72512651 0.5317131 o.810944 0.15005822 0.11507635 0.79533199 0.82684461 0.95149442 0.88726599 o.87037905 3 5 888879668 35 lbs 25600006016 .7oz 13130025348 18 oz 8888680291 10 12 1002770014 2 lb 416005415 20613068150 4'x 10" x1" 24543027089 DVI 22333725160 1 ct 13 21000003488 8 0Z 11170044589 14.5 OZ 19014296637 18111212496 DVD 11110371843 300ct 24131796045 1 ct 1852710628o 23700642851 3-50 LB 13131216899 DVD 20 21 21120417608 10 oz 14200085101 48 oz 21000651504 16 oz 10300001508 50 lb 15400061919 12300275132 13131081732 One VHS Tape SG CELLO SPINACH 100Z S&S I/O CHRMS FAMILY FUN Parkay Squeezable Diamond inshell mixed nuts Western Family 4-pack of C cell batteries Best Value Men Lt Kings Return To OZ Widescreen Collector's Edition VHS Tape Tannoy Reveal 8D Tastykake Choc Pretzel Rods Milkbone Biscit Tartar Control Myst III - Exile (PC) from UBI SOFT ENTERTAINMENT PUR LEMON GOLD FILLING Oval Emotion Reach Out - CD Zagat Survey 2007 New York City Young Frankenstein SHPR FOOD CHOPPER KRAFT NY SHARP CHEDDAR PP LADY LEE BEEF BROTH IAM'S 3 OZ. C.F. Joseph And The Coat Of Many Colors Kroger Glucosamine&Chondroitin FW CLASSIC 7" STRAINER Individual Resume Maker Deluxe 2001 SKINLESS CHICKEN TENDERLOINS Thomas And Friends: Best Of Percy 0.05037411 0.11308556 0.68537997 0.6753737 0.13326981 0.75889672 0.50864656 0.53131274 0.82856474 0.3315569 0.96463522 0.73600305 0.92716368 0.52449118 0.66695527 0.72512651 0.5317131 o.810944 0.15005822 0.11507635 0.79533199 0.82684461 0.95149442 0.88726599 o.87037905 3 5 888879668 35 lbs 25600006016 .7oz 13130025348 18 oz 8888680291 10 12 1002770014 2 lb 416005415 20613068150 4'x 10" x1" 24543027089 DVI 22333725160 1 ct 13 21000003488 8 0Z 11170044589 14.5 OZ 19014296637 18111212496 DVD 11110371843 300ct 24131796045 1 ct 1852710628o 23700642851 3-50 LB 13131216899 DVD 20 21