CE3345-Project 4 Simplified Red-Black Trees Solved

The task of this project is to implement in Java a red-black tree data structure.  However, the tree will be simplified – you only need to support insertion, not deletion.

Specification
The project must implement the following specification exactly, including all identifier names, method signatures, the presence or absence of exceptional behavior, etc.  That being said, anything not clearly indicated by the UML diagram(s) or explicitly stated in the description is left up to your discretion.  You may also add private helper methods or additional fields as necessary.

Structure


Note that a box with a dashed border over the top right of a class entity denotes a generic type parameter.  In this case, the red-black tree class has a generic type named E that extends Comparable<E – you may choose whether or not to make Node generic as well.  The Comparable<T interface is located in the java.lang package, so it is not necessary to import it.  Finally, for this project you should locate your code in the default package.

Behavior
insert should insert the given element into the tree at the correct position, and then rebalance the tree if necessary.  The correct position is defined by the properties of a binary search tree, and the rebalancing procedure should enforce the properties of a red-black tree.  Regarding input validation, insert should immediately throw a NullPointerException with a descriptive message if the given element is null.  Alternatively, if the given element is a duplicate of an element already in the tree, then insert should not insert the given element.  The return value should indicate whether the given element was inserted into the tree or not.

Two elements are considered duplicates iff (if and only if) they compare equal to each other using the compareTo method.  Likewise, the ordering of any two elements for the purposes of insertion and rebalancing is given by the same method.

contains should return whether the tree contains any element that compares equal to the given object using the compareTo method of the object.  This means that you should always do object.compareTo(element) but never do element.compareTo(object). 

However, if the given object is null, then contains should not throw an exception but rather should return false.

toString should override the eponymous method of Object and return a string representing the pre-order traversal of this tree.  The returned string should be the ordered concatenation of invoking the toString method of each element in the traversal, where every two adjacent elements should be separated by a single space character (“ ”).  If an element is located in a red node, then it should be preceded by a single asterisk character (“*”) in the output string.  Otherwise, an element located in a black node should not be preceded by an asterisk.  An example of the output is as follows (assuming that the elements are of type Integer):

30 2 *5 47 *60

It is entirely optional, but it may make your life easier to use a StringJoiner and/or to implement Node#toString() as well.

The color field of the node class should be assigned and evaluated using the RED and BLACK constants of the enclosing tree class.  This means that you should always do color = BLACK or if(color == RED) but never do color = true or if(!color).

 

Main Class
Along with the RedBlackTree class include another class that has a main function. You can name this class anything just clearly indicate the name in Readme File. This class will take two command line arguments. The first argument will be the input file name and second will be output file name. The input file will be given to the program and the output file will be generated by the program. This main class will create an instance of RedBlackTree and do the operations specified in the input file.

To understand the format of input and output files please see the following examples.  Example 1

Integer

Insert:98

Insert:-68

Insert:55

Insert:45

PrintTree

Contains:45

Insert:84

Insert:32

Insert:132

Insert:45

PrintTree Insert hih  

{The first line indicates the object that needs to be inserted into the Tree. It can only accept two objects String or Integer In this example we insert Integer objects. }

The corresponding correct output file should be

True

True

True

True

55 -68 *45 98

True

True

True

True

False

55 32 *-68 *45 98 *84 *132

Error in Line: Insert

Error in Line: hih

  

Example 2

String

Insert:Ana

Insert:Owen

Insert:Pete

Insert:Leo

PrintTree

Contains:Owen

Insert:Nick      

Insert:Maya

Insert:Leo

PrintTree

 

The corresponding correct output file should be

 

True

True

True

True

Owen Ana *Leo Pete

True

True

True

False

Owen *Leo Ana Nick *Maya Pete

For all other objects ( other than String and Integer),  just declare can’t work with the object in your output file and quit. 

 

Example 2 Students

 

 

The corresponding correct output file should be

 

Only works for objects Integers and Strings 

Remember your RedBlackTree class itself should be generic and should allow any object that is Comparable. We will be testing your RedBlackTree class separately using unit testing modules.