Objective: Students will apply concepts of Java Generics and Red-Black Trees in this programming assignment. Assignment...

Transcribed Image Text:

Objective: Students will apply concepts of Java Generics and Red-Black Trees in this programming assignment. Assignment Description: In this class, we have learned a couple of advanced data structures related to trees. In this assignment, you will manage an address book of professors with the abstract data type (ADT) red-black tree data structure. You will create your own Red-Black Trees using Java Generics This programming assignment must be completed in the Java programming language. Any other language used will result in score of 0 on the assignment. For this assignment, you must follow these requirements. 1. You will create an ADT Red-Black Tree class called AddressBookTree with Java Generics (type T and type U). The attribute for the class must contain: a. root of Node b. You may create additional helper attributes that can assist with maintaining the red-black tree. 2. You will use two unique type variables T and U. T represents the name and U represents office. 3. You will create a Node class that will represent the nodes in a red-black tree using generics. The attributes needed for the class are a. Name of type T (Generics) b. Office of type U (Generics) c. Reference to parent node d. Reference to left child node e. Reference to right child node f. An int that represents color (0 for black and 1 for red) 4. The AddressBookTree class must have the following methods. Most of the methods have been provided to you in the pseudocode on the slides. a. Default constructor i. Set everything to default values. b. Insert i. Parameter takes two arguments: T name, U office c. Insert-Fix (applying rules for insertion) i. Parameter takes one argument: Node<T, U> d. Delete i. Parameter takes one argument: T name e. Delete-Fix (applying rules for deletion) i. Parameter takes one argument: Node<T, U> f. Rotations (both left and right) i. Parameter for both takes one argument: Node<T, U> g. RB-Transplant i. Parameter takes two arguments: Node<T, U> and Node<T, U> h. Display (inorder traversal) i. No arguments needed. Note: There is a space between the name and office. i. countBlack-method to count black nodes in tree i. Parameter takes Node to count from (the root) j. countRed-method to count red nodes in tree i. Parameter takes Node to count from (the root) k. You may also create additional helper methods as well. 5. Make all methods public and class attribute private. It's good practice! A runner file (Address BookTreeRunner.java) has been provided for you to show you how the methods are called along with 3 test cases based on maintaining the tree after certain operations. A text file is also provided for you that will help fill the tree in the initial run. The text file itself must be in the same directory as the runner file. What to submit: Submit a file called Address BookTree.java to webcourses. You are not required to submit the runner file as that will be provided for the graders to test your code. Please make sure the runner file provided works for your code. Any name changes may cause your program not to work when graded, which will result in a lower score on the assignment and would not be changed. Important Note for running Eustis: Many of you are probably using IDEs like Netbeans and Eclipse to build your Java Solutions. Please note that some of these IDEs will automatically place your Java file in some sort of package. Please make sure your Java file is not defined in some package as this can result package private errors. Any such error that occurs during the grading will not be fixed and points will be deducted as such in accordance with the respective categories in the rubric. Also, DO NOT create a main method in your solution file!! This will result in your code not running properly with the runner file which will result in points being deducted from the respective categories. Objective: Students will apply concepts of Java Generics and Red-Black Trees in this programming assignment. Assignment Description: In this class, we have learned a couple of advanced data structures related to trees. In this assignment, you will manage an address book of professors with the abstract data type (ADT) red-black tree data structure. You will create your own Red-Black Trees using Java Generics This programming assignment must be completed in the Java programming language. Any other language used will result in score of 0 on the assignment. For this assignment, you must follow these requirements. 1. You will create an ADT Red-Black Tree class called AddressBookTree with Java Generics (type T and type U). The attribute for the class must contain: a. root of Node b. You may create additional helper attributes that can assist with maintaining the red-black tree. 2. You will use two unique type variables T and U. T represents the name and U represents office. 3. You will create a Node class that will represent the nodes in a red-black tree using generics. The attributes needed for the class are a. Name of type T (Generics) b. Office of type U (Generics) c. Reference to parent node d. Reference to left child node e. Reference to right child node f. An int that represents color (0 for black and 1 for red) 4. The AddressBookTree class must have the following methods. Most of the methods have been provided to you in the pseudocode on the slides. a. Default constructor i. Set everything to default values. b. Insert i. Parameter takes two arguments: T name, U office c. Insert-Fix (applying rules for insertion) i. Parameter takes one argument: Node<T, U> d. Delete i. Parameter takes one argument: T name e. Delete-Fix (applying rules for deletion) i. Parameter takes one argument: Node<T, U> f. Rotations (both left and right) i. Parameter for both takes one argument: Node<T, U> g. RB-Transplant i. Parameter takes two arguments: Node<T, U> and Node<T, U> h. Display (inorder traversal) i. No arguments needed. Note: There is a space between the name and office. i. countBlack-method to count black nodes in tree i. Parameter takes Node to count from (the root) j. countRed-method to count red nodes in tree i. Parameter takes Node to count from (the root) k. You may also create additional helper methods as well. 5. Make all methods public and class attribute private. It's good practice! A runner file (Address BookTreeRunner.java) has been provided for you to show you how the methods are called along with 3 test cases based on maintaining the tree after certain operations. A text file is also provided for you that will help fill the tree in the initial run. The text file itself must be in the same directory as the runner file. What to submit: Submit a file called Address BookTree.java to webcourses. You are not required to submit the runner file as that will be provided for the graders to test your code. Please make sure the runner file provided works for your code. Any name changes may cause your program not to work when graded, which will result in a lower score on the assignment and would not be changed. Important Note for running Eustis: Many of you are probably using IDEs like Netbeans and Eclipse to build your Java Solutions. Please note that some of these IDEs will automatically place your Java file in some sort of package. Please make sure your Java file is not defined in some package as this can result package private errors. Any such error that occurs during the grading will not be fixed and points will be deducted as such in accordance with the respective categories in the rubric. Also, DO NOT create a main method in your solution file!! This will result in your code not running properly with the runner file which will result in points being deducted from the respective categories.

Answer rating: 100% (QA)

import javautilScanner Class Node class RedBlackNode RedBlackNode left right int element int color Constructor public RedBlackNodeint theElement this theElement null null Constructor public RedBlackNo... View the full answer