Simplified Red-Black Trees The task of this project is to implement in Java a re

Question

Simplified Red-Black Trees 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 sup 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 E (extends ComparablecE> E (extends ComparablecE> estaticw Node staticRED: boolean false -element: E -leftChild: Node right Child: Node parent: Node -color boolean static»-BLACK: boolean true ToOt: Node tinsert(element: E): boolean (throws NullPointerException) +contains(object: ComparablecE>: boolean +toString0: String 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 interface is located in the lava. lang package, so it is not necessary to impr t. 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, insertshould immediately throw a Nul1PointerException 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 rebalan 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)

Explanation / Answer

Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class Main {

   public static void main(String[] args) {
       // TODO Auto-generated method stub

       if(args[0] == null || args[1] == null) {
           System.out.println("Please give input/output file name");
           return ;
       }
      
       // The name of the file to open.
String ipfileName = args[0];
String opfileName = args[1];
String line;
try {
// FileReader reads text files in the default encoding.
FileReader ipfileReader =
new FileReader(ipfileName);
  
FileWriter opfileWriter =
new FileWriter(opfileName);

// Always wrap FileReader in BufferedReader.
BufferedReader ipbufferedReader =
new BufferedReader(ipfileReader);
  
BufferedWriter opbufferedWriter =
new BufferedWriter(opfileWriter);
  
line = ipbufferedReader.readLine();
  
if(line.equals("Integer")) {
   RedBlackTree<Integer> rbTree = new RedBlackTree<Integer>(Integer.MIN_VALUE);
  
   while((line = ipbufferedReader.readLine()) != null) {
   if(line.startsWith("Insert")) {
       opbufferedWriter.write(Boolean.toString((rbTree.insert(Integer.parseInt(line.split(":")[1])))));
   }else if(line.startsWith("Contains")) {
       opbufferedWriter.write(Boolean.toString((rbTree.contains(Integer.parseInt(line.split(":")[1])))));
   }else if(line.startsWith("PrintTree")) {
       opbufferedWriter.write(rbTree.toString());
   }
}
  
   }else if(line.equals("String")){
       RedBlackTree<String> rbTree = new RedBlackTree<String>(Integer.MIN_VALUE);
       while((line = ipbufferedReader.readLine()) != null) {
   if(line.startsWith("Insert")) {
       opbufferedWriter.write(Boolean.toString((rbTree.insert((line.split(":")[1])))));
   }else if(line.startsWith("Contains")) {
       opbufferedWriter.write(Boolean.toString((rbTree.contains((line.split(":")[1])))));
   }else if(line.startsWith("PrintTree")) {
       opbufferedWriter.write(rbTree.toString());
   }
}
   }
  
  

// Always close files.
ipbufferedReader.close();
opbufferedWriter.close();
}
catch(FileNotFoundException ex) {
ex.printStackTrace();
}
catch(IOException ex) {
ex.printStackTrace();
}
      
   }

}

RedBlackTree.java

public class RedBlackTree<E extends Comparable<E>> {

   private Node<E> current;
private Node<E> parent;
private Node<E> grand;
private Node<E> great;
private Node<E> header;
  
private static Node nullNode;
/* static initializer for nullNode */
static
{
nullNode = new Node(0);
nullNode.leftChild = nullNode;
nullNode.rightChild = nullNode;
}
/* Black - 1 RED - 0 */
static final boolean BLACK = true;
static final boolean RED = false;

public String preOrder = "";
  
/* Constructor */
  
public RedBlackTree(int negInf)
{
header = new Node(negInf);
header.leftChild = nullNode;
header.rightChild = nullNode;
}  

public boolean insert(E item ) throws NullPointerException
{
   boolean result = true;
  
   if(item == null) {
       throw new NullPointerException();
   }
  
current = parent = grand = header;
nullNode.element = item;
while (current.element != item)
{
great = grand;
grand = parent;
parent = current;
current = item.compareTo(current.element) < 0 ? current.leftChild : current.rightChild;
// Check if two red children and fix if so
if (current.leftChild.color == RED && current.rightChild.color == RED)
handleReorient( item );
}
// Insertion fails if already present
if (current != nullNode)
return false;
current = new Node(item, nullNode, nullNode);
// Attach to parent
if (item.compareTo(parent.element) < 0)
parent.leftChild = current;
else
parent.rightChild = current;
handleReorient( item );
  
return result;
}
  
public Node<E> getCurrent(){
   return current;
}

private void handleReorient(E item)
{
// Do the color flip
current.color = RED;
current.leftChild.color = BLACK;
current.rightChild.color = BLACK;

if (parent.color == RED)   
{
// Have to rotate
grand.color = RED;
if (item.compareTo(grand.element) < -1 != item.compareTo(parent.element) < -1)
parent = rotate( item, grand ); // Start dbl rotate
current = rotate(item, great );
current.color = BLACK;
}
// Make root black
header.rightChild.color = BLACK;
}
private Node rotate(E item, Node parent)
{

   if(item.compareTo((E) parent.element) < 0)
return parent.leftChild = item.compareTo((E) parent.leftChild.element) < 0 ? rotateWithleftChildChild(parent.leftChild) : rotateWithrightChildChild(parent.leftChild) ;
else
return parent.rightChild = item.compareTo((E) parent.rightChild.element) < 0 ? rotateWithleftChildChild(parent.rightChild) : rotateWithrightChildChild(parent.rightChild);
}
  
/* Rotate binary tree node with leftChild child */
private Node rotateWithleftChildChild(Node k2)
{
Node k1 = k2.leftChild;
k2.leftChild = k1.rightChild;
k1.rightChild = k2;
return k1;
}
/* Rotate binary tree node with rightChild child */
private Node rotateWithrightChildChild(Node k1)
{
Node k2 = k1.rightChild;
k1.rightChild = k2.leftChild;
k2.leftChild = k1;
return k2;
}
  
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public boolean contains(E x ) {
  
   if(x == null) {
       return false;
   }
  
   nullNode.element = x;
current = header.rightChild;

for( ; ; ) {
if( x.compareTo( current.element ) < 0 )
current = current.leftChild;
else if( x.compareTo( current.element ) > 0 )
current = current.rightChild;
else if( current != nullNode )
return true;
else
return false;
}
}
  
public void toStringUtil(Node t) {
   if( t != nullNode ) {
   if(t.color == RED) {
       preOrder.concat("*");
   }
   preOrder.concat(t.element + " ");
   toStringUtil( t.leftChild );
toStringUtil( t.rightChild );
}
}
  
@Override
public String toString() {
toStringUtil(header);
return preOrder;
}
  
}

Node.java

public class Node<E extends Comparable<E>>{
   E element ;
   Node leftChild;
   Node rightChild;
   Node parent;
   boolean color;
  
   Node(E element){
       this.element = element;
   }
  
   Node(E element,Node left, Node right){
       this.element = element;
       this.leftChild = left;
       this.rightChild = right;
   }
  
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.